CSE 203, Recent developments in algorithms Spring, 2006

Prof. Russell Impagliazzo

Office: 4248 CSE Building (EBU 3b)
Phone: (858) 534-1332; Fax: (858) 534-7029;
Email: russell@cs.ucsd.edu

Office Hours: Wed, 2-4, Room TBA. Perhaps additional office hours will be added if there's high demand.

Announcements:

1. Class Description (Postscript)
2. Homework 1 (Postscript)
3. Homework 1 answer key (Postscript)
4. Homework 2 (Postscript)
5. Final Exam, due June 16(Postscript)
6. First lecture: The reduction method (Postscript)
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)
11. Scribe notes from Sanjoy's first lecture (pdf)
12. Scribe notes from Sanjoy's second lecture

Note: For probabilistic algorithms, I'm cutting and pasting together notes from previous classes that covered substantially the same material. However, I am also planning to update these with versions for this year.

13. Old version: diophantine equations
14. This year's version: testing straight-line programs (generalizes diophantine equations)
15. Old version: using algebraic counting arguments and number theory for modular square roots
16. This years version: using algebraic counting arguments and number theory for primality testing
17. This year: game tree evaluation: where randomization provably helps
Note: the following have not been carefully edited yet, and may be revised
18. Vadim's presentation on distance preserving dimension reduction
19. A paper on dimension reduction
20. Karger's randomized Min Cut algorithm (Note: In PDF format)
21. Karger's graph sparsification method
22. Kyrill's class on stream algorithms