CPSC 420+500 Advanced Algorithm Design and Analysis 2018 W2
- Instructor:
- Hu Fu
hufu@cs.ubc.ca
ICCS X539, 827-4222
- Teaching Assistants:
-
Jack Spalding-Jamieson
email: s4x0b@ugrad.cs.ubc.ca
-
Da Wei (David) Zheng
email: zhengdw@cs.ubc.ca
-
Yihan Zhou
email: yihan95@cs.ubc.ca
- Office hours before the final exam:
-
April 8, Monday, 3-4pm (Hu, ICICS X539)
-
April 9, Tuesday, 10:30-11:30am (Yihan, ICCSX 141)
-
April 10, Wednesday, 3-4pm (Hu, ICICS X539)
-
April 11, Thursday, 3-4pm (Jack, X141)
-
April 16, Tuesday, 10:30-11:30am (Yihan, ICCSX 141)
-
April 22, Monday, 1-2pm (David, ICCSX 141)
-
April 22, Monday, 3-4pm (Hu, ICCSX 141)
-
April 23, Tuesday, 1-2pm (David, ICCSX 141)
-
April 23, Tuesday, 2-3pm (Jack, X141)
-
April 23, Tuesday, 3-4pm (Hu, ICICS X539)
-
- Piazza:
-
We will be using Piazza for class discussions. Find our class page at:
piazza.com/ubc.ca/winterterm22018/cpsc420500
- Lectures:
- MWF 13:00 - 14:00 DMP 110
- Syllabus:
-
We will largely follow the second half of the textbook by Kleinberg and Tardos, starting with network flows and NP-completeness, and then approximation algorithms and randomized algorithms, among other topics selected from the last chapters of the book.
- 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%) + Midterm (30%) + Final (40%). Both the midterm and the final are open book. The required textbook and any other written notes (but no other printed notes) are allowed.
Expect curving to happen --- one has to be challenged to become an independent algorithm designer. There will be updates on this throughout the semester.
- Mid-term date:
- Feb 13, Wednesday, in class (open book)
- Homework Policies:
-
- We will have written assignments roughly every two weeks. You may form groups of up to three people for each assignment, although a group of two is encouraged. Each group needs to turn in only one solution.
- No late solutions will be accepted.
- 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.
-
For assignments and exams, unless stated otherwise, for all questions that ask to design an algorithm, you need to provide justification for, (that is, 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 and their solutions will be posted on Gradescope. You should turn in your solutions there as well. Please make sure that you submit as a group on Gradescope, and the submission has all your group members.
-
Some problems in the assignments are more challenging than the others. 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:
-
-
Jan 2: Introduction. Slides
-
Jan 4, 7: Proof writing; review of greedy and dynamic programming via shortest paths.
- Reading: Chapter 4.4, 6.8; Optional reading: Chapter 6.9-10, 2.5.
-
Slides
-
Scribes (The Dijkstra proof was rescribed for clarity.)
-
Jan 9, 11, 14: Flow networks basics, Ford-Fulkerson Algorithm
- Jan 16, 18: Bipartite matchings
- Reading: Chapter 7.5
- Slides
-
Scribe (Proof that flows correspond to matchings is completed; added illustration of the proof for Hall's theorem)
- Jan 18, 21, 23: Edge-disjointed paths. Circulations.
- Jan 23, 25: Image segmentation, project selection.
- Reading: Chapter 7.10-11; optional: Chapter 7.12
-
Slides
-
Scribe
- Jan 25, 28, 30: NP-completeness basics, Independent Set, Vertex Cover
- Reading: Chapter 8.1-4; the discussion in Chapter 8.4 on Circuit Satisfiability is optional
-
Slides
-
Scribe
-
(Added on Jan 29) Optional reading: lecture notes by Bobby Kleinberg on Edmonds-Karp algorithm
- Feb 1, 4: Set cover; Hamiltonian path/cycle; Traveling salesman problem
-
Reading: Chapter 8.5
-
Slides (Exercises added on Feb 11)
-
Scribe
- Feb 6, 8: 3-dimensional matching; 3-coloring; Subset sum; Knapsack problem
- Reading: Chapter 8.6, 8.8, 8.10
- Optional reading: Chapter 8.7, 8.9
-
Scribe (Completed the counting of clean-up nodes)
-
Scribe for Subset sum (with page 2 as a more organized redo)
- Feb 11: Review --- see slides for Feb 11 for the list of exercises we discussed.
-
Scribe (Warning: disorganized)
- Feb 13: Midterm Exam; Feb 15: going over the exam
- Feb 25: Small Vertex Cover
- Feb 27: (Max Weight) Independent Set on the Tree
- Reading: Chapter 10.2
- Slides: see Feb 25.
- Scribes
- March 1, 4: Dilworth's theorem; Coloring circular arcs
- March 6, 8: Approximation algorithms: load balancing
- Reading: Chapter 11.1
- (Very) optional reading: Survey article by Tim Roughgarden on algorithm analysis beyond the worse case framework.
-
Slides
-
Scribes
-
Scribes on March 8.
- March 11, 13: Center selection
- March 15, 18: Set cover
- March 18, 20: FPTAS for Knapsack
- March 22, 25: Randomized algorithms: contention resolution
- Reading: Chapter 13.1
- Optional reading: Chapter 13.12 (Strongly recommended if your probability theory needs a brush-up)
-
Slides
- March 27: Karger's algorithm for min cut
- March 29, April 1: Random variables and their expectations
- April 1, 3: Quicksort
- Reading: Chapter 13.5 (the part on Median finding is optional but highly recommended; the analysis is simpler than Quicksort and is a good preparation)
-
Slides
- April 3: MAX 3-SAT
- Reading: Chapter 13.4 (the part on "further analysis" is optional; this is a spelt out version of the Markov inequality)
-
Slides
- April 11: Review session