UW Logo

CS 466/666, Fall 2011

Advanced Algorithms

(link to CS466/666 home page)

References:

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

[CLRS] Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (2nd ed.), MIT Press, 2001 (QA76.6.C662)
  [I've used the 1st edition during preparation, so the chapter numbers might be a bit off. ]
[BCKO] de Berg, Cheong, van Kreveld, Overmars. Computational Geometry: algorithms and applications. (3rd ed.), Springer, 2008. (QA448.D38C65 1997). Also available electronically if you're on a UW computer.
[MU] M. Mitzenmacher and E. Upfal, Probability and Computing, Cambridge University Press, 2005 (QA274 .M574 2005)
[MR] Motwani and Raghavan, Randomized Algorithms, Cambridge University Press, 1995 (QA274.M68)
[P] Papadimitirou, Computational Complexity, Addison-Wesley, 1994 (QA267.7.P36 1994)
[V] Vazirani, Approximation Algorithms, Springer-Verlag, 2001 (QA76.9.A43 V39)

Many topics are presented directly from the original papers; references to electronic editions will be given below.

For a few topics, I will be writing lecture notes. This is very much work in progress, and no promises are made when these notes will be ready.

Lecture Topics:

The lectures are organized around problems instead of techniques, to motivate things better. We usually devote more than a lecture to each problem and then explore different ideas to devise an efficient algorithm. Along the way, we will indeed encounter new design techniques and variations on the analysis model (themes like amortization, randomization, approximation, online computation, etc., as promised in the handbook description), but the main emphasis is how to think about problems...

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.