Tentative Calendar
Week  Topic  Problem
Sets 
Handouts 
Reading 
Sep 6  Administrivia; Algorithms & their complexity The Selection problem: Randomized lineartime algorithm 
POW1  9.19.2 

Sep 13 
Deterministic divideandconquer algorithm for selection Strassen's algorithm for matrix multiplication Introduction to graphs & graph algorithms; MST: Structural properties; Kruskal's algorithm; 
PS1 out 
POW2,3  9.3, 4.2, 22.122.3, 23 
Sep 20 
MST: Prim's and Borouvka's algorithms; Priority queues Randomized lineartime algorithm of KargerKleinTarjan MST verification and least common ancestor calculations 
1 due; 2 out  23, 6.16.3, 6.5 KargerKleinTarjan King, Eisner, Hagerup Bender, FarachColton 

Sep 27 
Greedy algorithms: Huffman encoding Matriods and greedy methods Dynamic programming: Longest Common Subsequence; Application to shortest paths 
PS2
out 
POW 45 
16.14, 15.315.4 24.1, 25.1 
Oct 4 
Singlesource and allpairs shortest paths Network flows: Maxflowmincut theorem 
2 due; 3 out 
24.3, 25.2, 26.1  
Oct 11 
No class on Monday, Columbus Day Network Flows: FordFulkerson and EdmondsKarp algorithms 
PS3 out 
26.2  
Oct 18 
Network Flows, contd Linear programming Formulating problems as linear programs 
Notes
on LP 
29.129.2, 29.4 

Oct 25  Linear programming: Geometry and Duality Linear programming: The simplex algorithm 
3 due; PS4 out 
POW 67 
29.3, 11 
Nov 1 
Complete Simplex and Farkas Lemma NPcompleteness: P, NP, polynomialtime 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
810 

Nov 22 
Fast Fourier Transform No class on Thanksgiving Eve Nov 24 
PS5 out 

Nov 29 
Splay Trees Games and Solution Concepts 
POW
1114 
SleatorTarjan Sleator's notes 

Dec 6 
Nash equilibria, Zerosum
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.