Princeton University Computer Science Dept.

Computer Science 594 Advanced Topics in Algorithms: Algorithms & Complexity Sanjeev Arora Assignments/Handouts

Spring 1999

Directory
General Information  | Assignments/Handouts

Handouts:

1. Some lecture notes of mine on complexity theory. (From McGill workshop on complexity theory, 1996.)
2. Dan Spielman's lecture notes (MIT link).
3. Some old lecture notes of mine on decision trees.

My lecture notes from this term (very rough!):

• Diagonalization
• Karp-Lipton-Sipser theorem
• Hastad Switching Lemma.
  

Homeworks:

• HW1 (Due Feb 17)
• HW2  (Due March 8)
• HW3 (Due March 29)
  

The last third of the course is devoted to student presentations.