| Week 1 | Sep. 26 | Why exponential algorithms? |
| Sep. 28 | Constraint satisfaction problems | |
| Week 2 | Oct. 3 | Problem transformation and NP-completeness |
| Oct. 5 | Other standard NP-complete problems: maximum independent set and traveling salesman problem | |
| Week 3 | Oct. 9 | Homework 1 due |
| Oct. 10 | Generate and test | |
| Oct. 12 | Randomized and derandomized generate and test | |
| Week 4 | Oct. 17 | Backtracking: simple 2n 3-coloring algorithm; listing all maximal independent sets |
| Oct. 19 | Solving recurrences; enumeration of cases (proof by exhaustion) | |
| Week 5 | Oct. 23 | Homework 2 due |
| Oct. 24 | Simple randomized (3,2)-CSP algorithm and its derandomization | |
| Oct. 26 | Feder and Motwani's randomized (k,2)-CSP algorithm | |
| Week 6 | Oct. 31 | TSP: dynamic programming, comparison to branch and bound / polyhedral combinatorics approach |
| Nov. 2 | Dynamic programming for graph coloring | |
| Week 7 | Nov. 7 | Mixing dynamic programming with backtracking |
| Nov. 9 | Pathwidth and faster dynamic programming for special graph classes | |
| Week 8 | Nov. 13 | Homework 3 due |
| Nov. 14 | No class (away at FOCS 2000) | |
| Nov. 16 | Pathwidth and treewidth of planar graphs | |
| Week 9 | Nov. 21 | Schöning's random-restart hill-climbing k-SAT algorithm |
| Nov. 23 | No class (thanksgiving) | |
| Week 10 | Nov. 28 | Quantum computation and quantum circuits |
| Nov. 30 | Grover's algorithm for quantum generate-and-test | |
| Finals Week |
Dec. 8 | Homework 4 due |