CS 466/666, Fall 2022

Advanced Algorithms

(link to CS466/666, Spring 2022)

Welcome to cs466! This web page is mostly a repository of (fairly static) information. For announcements, see piazza. For lecture materials and assignments, see LEARN.

Meeting Time/Place: Tue & Thu 8:30-9:50, MC2038

Instructor: Therese Biedl (DC2341, x34721, biedl "at" uwaterloo.ca), office hrs: Tue 10-11, DC2341, or email me to make an appointment.

TAs: Mohammad Hossein Ebtehej (mhebtehaj "at" uwaterloo.ca), office hrs: Wed 12:30-1:30, DC2305 (this may change in the future)
Robert Wang (r585wang "at" uwaterloo.ca), office hrs: Mon 3-4pm, DC3139

Course Work:

Official cs466 outline and Official cs666 outline
Assignments are due at 5pm (Waterloo local time) and should be submitted as a PDF in crowdmark
- A1 (due Mon, Sep 26)
- A2 (due Mon, Oct 17)
- A3 (due Fri, Nov 4)
- A4 (due Fri, Nov 18)
- A5 (due Fri, Dec 2)
The midterm is on Monday, Oct 24, 7-8:50pm, in STC0010. The final will be 2.5 hours long and scheduled by UW.
Projects (for CS666 students only): Due dates are Oct 7, 5pm and Dec 5, 5pm. More info on project

References:

There is no required textbook for this course. The following references are useful (those not available electronically will be placed on reserve in the DC library for 3 hour loan).

[CLRS] Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (numerous editions with varying chapter numbers; the numbers below are from the 3rd ed., call number QA76.6.C662)
Good as a review of CS341 material, frequently does not go deep enough into CS466 material.
[MU] M. Mitzenmacher and E. Upfal, Probability and Computing, Cambridge University Press, 2005 (QA274 .M574 2005)
[V] Vazirani, Approximation Algorithms, Springer-Verlag, 2001 (QA76.9.A43 V39)
Various books and papers that are used only once are listed below

For all references listed as `electronically': If you get a `no permission' you may need to log on via the UW library and/or make a link to a licensed resource to get access.

Lecture Topics:

The following gives a list of topics, as well as some reference that roughly covers the material. This list may still change during the term.

Intro (Lecture 1)
Exact algorithms. (Lectures 1-3)
- Branching: Section 2.1 and 2.2 of book by Fomin and Kratsch, Exact exponential algorithms, Springer, 2010. (Available electronically)
- FPT-algorithms and W[1]-hardness: pages 1-7, Section 2.2.1, Section 13.3 of book by Cygan, Fomin, Kowalik et al. Parameterized algorithms, Springer, 2015. (Available electronically)
- LP and ILP: [CLRS] Chapter 29 intro (stop at 29.1) and parts of Section 35.4
Approximation algorithms. (Lectures 4-9)
- Ad-hoc approaches: [V] Section 2.1, 1.1.1, 3.2
- Randomized rounding: [V] Chapter 16, 26 (exclude 26.5), (new!) 14.2 (we did dominating set rather than set cover)
- (new!) Polynomial-time approximation schemes: [V] Section 8.1, 8.2
- Hardness of approximation: [V] Chapter 29 (exclude 29.4 onwards).
  (new!) For some reductions, see also Theorem 9.37 of book by Demaine et al. https://hardness.mit.edu/ (version of 9/21/22).
Special cases (Lecture 10-11)
- 2-SAT: Paper by Aspvall, Plass, Tarjan, https://doi.org/10.1016/0020-0190(79)90002-4
- (new!) Planar graphs: Notes in PDF.
- Independent set in hex-grid graphs: Notes in PDF. (new!)
More randomized algorithms (Lecture 13-17)
- Minimum spanning trees: Section 10.3 (ignore 10.3.3) of book by Motwani and Raghavan, Randomized Algorithms, Cambridge University Press, 1995 (QA274.M68)
  and paper by Chan https://doi.org/10.1016/S0020-0190(98)00129-X.
- Linear programming: Paper by Seidel, https://doi.org/10.1007/BF02574699.
- Monte Carlo algorithms: [MU] Section 1.1, 1.2
- Random walks: [MU] Section 7.1.1 and 7.1.2
- Lower bounds for selection: Section 4 of paper by Blum et al., https://doi.org/10.1016/S0022-0000(73)80033-9
- Randomized Selection: [MU] Section 3.5
Various algorithm scenarios (Lecture 18-24)
- Dynamic algorithms---maintenance of min-degree vertex: Notes in PDF.
  Detour: Amortized analysis: Notes in PDF.
- Incremental algorithms---maintenance of connected components: [CLRS] Chapter 21
- Online algorithms---The bus pass (ski rental) problem: Page 593 of book by Goodrich and Tamassia Algorithm Design an Applications, Wiley, 2015 (QA76.9.A43 G668 2015)
- Online algorithms---The lost-cow problem: Paper by Baeza-Yates et al. https://doi.org/10.1006/inco.1993.1054 and paper by Kao et al. https://doi.org/10.1006/inco.1996.0092
- Online decision algorithms---The hiring problem: [CLRS] Section 5.4.4
- Streaming algorithms---Sorting and Selection: Paper by Munro and Paterson https://doi.org/10.1016/0304-3975(80)90061-4
- (new!) Spectral graph theory: Course notes by Lap Chi Lau https://cs.uwaterloo.ca/~lapchi/cs860/notes.html (Chapter 3 and parts of Chapter 4)
- Sublinear algorithms---Testing distinctness: Course notes by Beame https://courses.cs.washington.edu/courses/cse522/14sp/lectures/lect01.pdf
- Imprecise input: Convex Hull intro: [CLRS] Section 33.3; Imprecise Convex Hull: Section 4.1 of paper by Löffler and van Kreveld https://doi.org/10.1007/s00453-008-9174-2
Course review (Lecture 24)