CS 466/666, Fall 2022

Advanced Algorithms

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; the 2nd ed. has 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 the reference that I followed or would recommend for further reading. This list may change much throughout 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)
- Direct approaches: [V] Section 2.1, 1.1.1, 3.2
- Randomized rounding: [V] Chapter 16, 26 (exclude 26.5)
- Hardness of approximation: [V] Chapter 29 (exclude 29.4 onwards)
Special cases (Lecture 10-11)
- 2-SAT: Paper by Aspvall, Plass, Tarjan, https://doi.org/10.1016/0020-0190(79)90002-4
- Ind. set and Maximum cut: notes to be posted
More randomized algorithms (Lecture 13-17)
- Linear programming: Paper by Seidel, https://doi.org/10.1007/BF02574699.
- Minimum spanning trees: Section 10.3 (ignore 10.3.3) of book by Motwani and Raghavan, Randomized Algorithms, Cambridge University Press, 1995 (QA274.M68)
  Also paper by Chan https://doi.org/10.1016/S0020-0190(98)00129-X.
- Monte Carlo algorithms: [MU] Section 1.1,1.2,3.5
- Lower bounds for selection: Section 4 of paper by Blum et al., https://doi.org/10.1016/S0022-0000(73)80033-9
- Random walks: [MU] Section 7.1.1 and 7.1.2
Restricted input (Lecture 18-23)
- Dynamic maintenance of min-degree vertex: notes to be posted
- Incremental maintenance of connected components: [CLRS] Chapter 21
- Online algorithms
- Streaming algorithms
- Sublinear algorithms
- Imprecise input: Section 4.1 of paper by Löffler and van Kreveld https://doi.org/10.1007/s00453-008-9174-2
Course review (Lecture 24)