Tentative Calendar
| Week | Topic | Problem
Sets |
Handouts |
Reading |
| Sep 6 | Administrivia; Algorithms & their complexity The Selection problem: Randomized linear-time algorithm |
POW-1 | 9.1-9.2 |
|
| Sep 13 |
Deterministic divide-and-conquer algorithm for selection Strassen's algorithm for matrix multiplication Introduction to graphs & graph algorithms; MST: Structural properties; Kruskal's algorithm; |
PS1 out |
POW-2,3 | 9.3, 4.2, 22.1-22.3, 23 |
| Sep 20 |
MST: Prim's and Borouvka's algorithms; Priority queues Randomized linear-time algorithm of Karger-Klein-Tarjan MST verification and least common ancestor calculations |
1 due; 2 out | 23, 6.1-6.3, 6.5 Karger-Klein-Tarjan King, Eisner, Hagerup Bender, Farach-Colton |
|
| Sep 27 |
Greedy algorithms: Huffman encoding Matriods and greedy methods Dynamic programming: Longest Common Subsequence; Application to shortest paths |
PS2
out |
POW 4-5 |
16.1-4, 15.3-15.4 24.1, 25.1 |
| Oct 4 |
Single-source and all-pairs shortest paths Network flows: Maxflow-mincut theorem |
2 due; 3 out |
24.3, 25.2, 26.1 | |
| Oct 11 |
No class on Monday, Columbus Day Network Flows: Ford-Fulkerson and Edmonds-Karp algorithms |
PS3 out |
26.2 | |
| Oct 18 |
Network Flows, contd Linear programming Formulating problems as linear programs |
Notes
on LP |
29.1-29.2, 29.4 |
|
| Oct 25 | Linear programming: Geometry and Duality Linear programming: The simplex algorithm |
3 due; PS4 out |
POW 6-7 |
29.3, 11 |
| Nov 1 |
Complete Simplex and Farkas Lemma NP-completeness: P, NP, polynomial-time reductions |
Farkas
Lemma Proof 34 |
||
| Nov 8 |
Approximation Algorithms Set cover, randomization and linear programming |
4 due Midterm out |
Approx Algs |
35 |
| Nov 15 | Random walk algorithm for
undirected connectivity Markov chains |
Midterm due | POW
8-10 |
|
| Nov 22 |
Fast Fourier Transform No class on Thanksgiving Eve Nov 24 |
PS5 out |
||
| Nov 29 |
Splay Trees Games and Solution Concepts |
POW
11-14 |
Sleator-Tarjan Sleator's notes |
|
| Dec 6 |
Nash equilibria, Zero-sum
games Market algorithms Mechanism design |
5 due | AGT
book, chapters 1,9 |
|
| Dec 15 |
Final Exam, due Dec 16 |
Note: All handouts are in PDF.