CPSC 420 Advanced Algorithm Design and Analysis 2019 W1
- Instructor:
- Hu Fu
hufu@cs.ubc.ca
ICCS X539, 827-4222
Office Hour: Tuesday 3:30-4:30pm
- Teaching Assistants:
-
-
Iliad Ramezani
email: iliadram@cs.ubc.ca
Office hours: Wednesday 1-2pm. X239.
-
Abner Turkieltaub
email: abner7@cs.ubc.ca
Office hours: Wednesday 3-4pm, X237.
-
Liam Vanderpoel
email: liam1tvu@students.cs.ubc.ca
Office hours: Monday 1-2pm, X239.
- Office hours during the exam period
-
Iliad: Dec 6, 4pm in ICCS X239
Hu: Dec 9, 1-2pm in ICCS 238
Abner: Dec 10, 5pm in ICCS X239
Hu: Dec 11, 1-2pm in ICCS 238
- Piazza:
-
We will be using Piazza for class discussions. Find our class page at:
https://piazza.com/class/jzmzvgv5iox1ge
- Lectures:
- MWF 14:00 - 15:00. Location: DMP 110
- Syllabus:
-
We will cover selected materials from the second half of the textbook Algorithm Design by Kleinberg and Tardos, starting with network flows and NP-completeness, followed by approximation algorithms and randomized algorithms.
CPSC 420 requires CPSC 320 as a pre-requisite. We only quickly review some basic graph algorithms, namely, BFS/DFS and shortest paths algorithms. Familiarity with basic probability theory will be very helpful for the chapter on randomized algorithms, but we will quickly go through the basics.
- Texts:
-
Required textbook: Jon Kleinberg and Eva Tardos. Algorithm Design, Addison-Wesley, 2005. The same textbook as required by CPSC 320. Required readings are assigned from the textbook.
Supplementary readings are occasionally provided here. Optional readings will be marked as such.
- Course Work:
-
Grades are determined by Problem sets/written assignments (30%) + Two Midterms (40%) + Final (30%). All exams are open book. If you performance in the final exam is better than either midterm, we will use the final exam score to replace the lower midterm.
We will do our best to adjust to the right level of difficulty, but curving may happen. One needs to be challenged outside one's comfort zone (though maybe not too much) to become an independent algorithm designer, and in the process the class's average can be lower than what many are used to. The grades will be adjusted when this happens. There will be updates on this throughout the semester.
- Midterm dates:
- October 10, Thursday, 7:30-9pm, DMP 310
- November 5, Tuesday, 7:30-9pm, DMP 310
- Mid-term policies:
-
- Students with reasonable time conflict for the midterms are offered a make up test, generally held the morning after the scheduled exam. For students who can make neither the midterm nor the make up due to reasonable conflicts, the final exam's grade, possbily adjusted according to the class distribution, will be used in place of the midterm.
- Conflicts due to work, family, health, religion, etc. are considered reasonable, and can be discussed case by case. As an example, if you have purchased a ticket for a concert on the night of the exam date: if the ticket was purchased before the exam dates are announced, this is considered a reasonable conflict, and if it was purchased after the announcement, this is considered unreasonable.
- Homework Policies:
-
- We will have written assignments roughly every two weeks. You may form groups of up to three people for each assignment. Each group needs to turn in only one solution.
- No late solutions will be accepted. We generally post solutions very soon after the due times.
- Typesetting solutions using LaTex is encouraged. If, by the end of the semester, the majority of your assignments are typeset with LaTeX, your lowest assignment mark will be dropped from the calculation of your course grade.
Here is a LaTeX template for your reference.
- Homework contributions to the final grade is capped at 30%, but exams contributions are not. In other words, if you solve bonus questions in exams and have grades more than 100% for that exam, the extra part is counted toward the other exams or the homework.
-
This class is proof based. Therefore, for all assignments and exams, unless stated otherwise, if a question asks you to design an algorithm, you need to prove the correctness of your algorithm. When the question asks for a certain running time (e.g. polynomial time, or O(n^2)), you should analyze the running time of your algorithm.
-
Assignments are posted on Gradescope. You should turn in your solutions there as well. The entry code for the course is 9ZJ5RJ. Please make sure that you submit as a group on Gradescope, and the submission has all your group members. If you have trouble using Gradescope, please contact the course staff.
- The source code of the problems and the solutions are posted on the Resource tab of the Piazza.
-
Some problems in the assignments are more challenging than the others. The bonus questions are usually considered more challenging. You are encouraged to discuss problems among yourselves, on Piazza, and/or come to office hours. You should start thinking about the problems early and not wait till the last day or two. Allow yourself time to think and to seek help.
-
If you do work with someone outside your group or use some outside source, you must acknowledge them in your write-up.
- Schedule:
-
-
Sep 4: Introduction. Review of basic graph algorithms: BFS.
-
Sep 6: DFS. Dijkstra's algorithm.
-
Dijkstra slides
-
Reading: Chapter 4.4.
-
Optional reading: Chapter 2.5, if you'd like a brush up on the implementation of a priority queue. We will not use this again in this course.
-
Sep 9: Finish Dijkstra's algorithm.
-
Sep 11: Bellman-Ford algorithm.
-
Sep 13: Flow networks, residual graph, Ford-Fulkerson Algorithm.
-
Sep 16, 18: Correctness of Ford-Fulkerson. Max Flow Min Cut Theorem.
-
Sept 20: Bipartite Matchings.
-
Sept 23: Hall's Theorem. Edge-disjoint paths
- Sept 25: Disjoint-path covers.
- Sept 27: Image segmentation
-
Slides
-
Reading: Chapter 7.10 of Kleinberg and Tardos
- Sept 30: Project selection
- Oct 2: Baseball Elimination
-
Slides
-
Reading: Chapter 7.12
-
Optional reading: These Lecture Notes by Bobby Kleinberg on Edmonds-Karp algorithm, a strongly polynomial-time algorithm for max flow.
- Oct 4: Polynomial-time Reduction.
- Oct 7, 9: NP completeness
-
Slides
-
Reading: Chapter 8.2, 8.3, 8.4; the section in Chapter 8.4 titled "Circuit Satisfiability: A first NP-complete problem" is optional
- Oct 11: NP completeness of Independent Set.
- Oct 16, 18: Hamiltonian cycles and Hamiltonian paths
- Oct 21: Eulerian tours and Eulerian circuits. Traveling salesman problem.
- Reading: Page 14 of these notes.
- Alternatively, you may read these Lecture notes by Christos Papadimitriou and Umesh Vazirani, the section on Eulerian paths and tours. But note that their definition of Eulerian tour is our definition of Eulerian cycle.
- Oct 23: 3-dimensional matching.
- Oct 25: Graph coloring. Exercises in class.
- Optional reading: Chapter 8.7
- Oct 28: Subset Sum.
- Oct 30: Finishing Subset Sum. Knapsack.
- Nov 1: Introduction to approximation algorithms.
- Nov 4: Practice problems for NP-completeness.
- Nov 6,8: Approximation algorithms for load balancing.
- Nov 13, 16: Center Selection.
- Nov 18, 20: FPTAS for Knapsack. Review of basic probability theory if time allows.
-
Reading: Chapter 11.8
-
Slides
-
Reading: Chapter 13.12 (optional depending on how much probability theory you know/remember. You may skip the section on infinite sample spaces.)
- Nov 22: Contention resolution
- Nov 25: Karger's min cut algorithm and conditional probabilities
- Nov 27, 29: Random variables and their expectations; randomized algorithm for MAX 3-SAT
- Reading: Chapter 13.3, 13.4 ("Further Analysis" in 13.4 is optional)
-
Slides