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: Friday, 1-3, 4248 CSE. Class TTh, 2-3:29, WLH 2113

Announcements:

1. Class Description
2. Homework 1: approximation algorithms
3. Homework 1 answer key
4. Homework 2: randomized algorithms
5. Final Exam

1. Approximation techniques: the reduction method From 2006 (Postscript)
2. Approximation techniques: the sacrifice precision method, part 1, This year (pdf)
3. Approximation techniques : Sacrifice precision part 2, combine bounds part 1 This year, pdf
4. Approximation techniques: the combine bounds method and the transformation method This year, pdf
5. The combine bounds method From 2006 (Postscript)
6. The transformation method from 2006 (Pdf)
7. Randomized algorithms: if any, then many. (Polynomial identity testing), This year, pdf
8. Randomized algorithm if any then many, primality testing From 2006, pdf
9. Randomized algorithm for achieving the average From 2006 (ps)
10. Randomized algorithm: averages in game tree evaluation from 2006 (pdf)
11. Randomized algorithms: sampling in Streaming Algorithms This year, pdf
12. Randomized algorithms: algorithmic proof of Lovasz Local Lemma This year, pdf
13. The ellipsoid algorithm