Prof. Russell Impagliazzo

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

Russell's Office Hours: Tuesday, Thursday, 1-2, or by appointment.

Course Handouts

1. First assignment, Due Tues. May 7
2. First assignment, Answer Key
3. Second assignment, Due Thurs. May 24
4. Second assignment, Answer Key
5. Final exam, due Friday June 14

1. Lecture notes on plentiful pigeon type arguments
2. Lecture notes on randomized algorithms from number theory
3. Lecture notes on randomized alpha-beta tree evaluation.
4. Lecture notes on ``achieve-the-average'' algorithms for MAX-SAT
5. Lecture notes on Karger and Stein's exact randomized min cut algorithm

Research papers for subjects not covered in the texts

1. David Karger's sparsification algorithm paper for min cut.
2. Borodin, Nielsen, and Rackoff's paper on ``What are the limits of greedy algorithms for scheduling?''