CSE 203, Recent developments in algorithms Winter 2004

Prof. Russell Impagliazzo

Office: 4111 Applied Physics and Mathematics Building (APM)
Phone: (858) 534-1332; Fax: (858) 534-7029;
Email: russell@cs.ucsd.edu

Office Hours: Tu, 4-5, Wed, 3-5

Announcements:

1. Class Description (Postscript)
2. First lecture: The reduction method (Postscript)
3. First Homework, due Feb. 4. Revised version! Thanks to all who pointed out typos, etc. (Postscript)
4. Second Homework, due March 10. REVISED VERSION. Thanks to all who pointed out mistakes.
5. Second Homework, Answer Key
6. Final Exam !
7. Lectures 2-3: The sacrifice precision method (Postscript)
8. Lectures 4-5: The combine bounds method (Postscript)
9. Lecture 6: The transFORMation method (Postscript)
10. Lecture 7: The layering method (Postscript)

Note: For probabilistic algorithms, I'm cutting and pasting together notes from previous classes that covered substantially the same material.

11. Plentiful pigeons part 1
12. Plentiful pigeons part 2
13. Plentiful pigeons part 3
14. Averaging arguments
15. Game tree evaluation: where randomization provably helps