[CLRS] Cormen, Leiserson, Rivest, and Stein,
Introduction to Algorithms (3rd ed.), MIT Press,
2001 (QA76.6.C662)
[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)
Borodin and El-Yaniv, Online Computation and Competitive
Analysis, Cambridge University Press, 1998 (QA76.9.A43 B67) [BE]
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.
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.
Increasing a binomial counter. The three methods of amortized analysis. Chapter 17 [CLRS], 3rd Ed.
Set intersection. Demaine et al.
Data Streams.
One sided error: majority algorithm
Generalization to 1/m most frequent elements
Two sided error 1/sqrt(nm)
Demaine et al.