Prof. Russell Impagliazzo

Office: 4248 Computer Science and Engineering Building
Phone: (858) 534-1332; Fax: (858) 534-7029;
Email: russell@cs.ucsd.edu

Russell's Office Hours: Monday 12-1 Monday 5-6, Thursday 11-12. If not crowded, 4248; or 4262 if it gets crowded.

TA: Eric Christiansen

Eric's Office Hours: Tuesday,Wed, Thursday, 4:30-5:30, in 4144

Announcements: Russell's 12-1 office hours tomorrow (Monday Feb 24) are cancelled due to the TCC invited talk. Russell will have office hours 5-6 as usual.

1. Class Description
2. Homework 1, Background Material, due January 14.
3. Homework 1, Answer Key
4. Homework 2, Path search, re-using algorithms, data structures. due January 28
5. Homework 2, Answer Key
6. Homework 3, Greedy algorithms Due Feb. 11
7. Homework 3, Answer Key
8. Homework 4, Divide-and-conquer, backtracking, dp part 1 Due Feb. 27 (Note change)
9. Homework 4, Answer Key
10. Homework 5, Dynamic programming, flows Due March 13
11. Homework 5, Answer Key
12. Final Exam (Revised)
13. Project idea list. This is from 2012, when the project description was somewhat different, but many of these are still suitable.

1. Greedy Algorithms Summary Sheet
2. Backtracking Summary Sheet(pdf)
3. Dynamic Programming Algorithms Summary Sheet
4. Notes on graph search from 101
5. Lecture Notes on rank selection (pdf)
6. Lecture Notes on data structures for Dijkstra's algorithm and amortized analysis (pdf)
7. Notes on using dynamic programming for approximation