No.  Date  Topics  Readings  Homework 
1  01/10 M  Introduction, Algorithm, Complexity, Various Equalities, Graphs, Recursion Tree, Master Theorem, AkraBazzi Theorem, Divide and Conquer (Strassen, Binary Multiplication), Dynamic Programming, Breadth First Search, Topological Sort, Minimum Spanning Trees, Shortest Paths  [Kozen 1] [CLR 1, 2, 3, 4, 5.4]  Homework 0 (PS) Solution (PS) 
2  01/12 W  Hints, Depth First Search, Strongly Connected Components  [Kozen 2, 4, 5] [CLR 23, 24, 25]  
3  01/14 F  More strongly connected components, minimum spanning forest  [Kozen 4] [CLR 23, 24]  
4  01/17 M  (Martin Luther King Day) NO CLASS   
5  01/19 W  UnionFind, Analysis  [Kozen 10,11] [CLR 22]  Homework 0 Due. Homework 1 (PS) Solution (PS) 
6  01/21 F  Heaps, Binomial Heaps, Amortized Analysis of Binomial Heaps  [Kozen 8] [CLR 20]  
7  01/24 M  Fibonacci Heaps  [Kozen 9] [CLR 21]  
8  01/26 W  More Fibonacci Heaps  [Kozen 9] [CLR 21]  
9  01/28 F  Treaps (Random Search Trees)  [Kozen 13] [M&R 8.2]  Homework 1 Due. Homework 2 (PS) Q1 picture Solution 
10  01/31 M  More Treaps  [Kozen 13]  
11  02/02 W  Splay Trees  [Kozen 12] Sleator's note  
12  02/04 F  Splay Trees Proof  [Kozen 12]  Practice Midterm Solution 
13  02/07 M  No class   
14  02/09 W  Midterm 1  Part 1   
15  02/11 F  Midterm 1  Part 2   
16  02/14 M  Planar Graphs, 5coloring   
17  02/16 W  Planarity Testing  [Kozen 14]  
18  02/18 F  Planar Separator Theorem 1  [Kozen 15]  
19  02/21 M  Subhash Khot's Talk (Attendence not required)   
20  02/23 W  Planar Separator Theorem 2  [Kozen 15]  Homework 3 (PS) Solution 
21  02/25 F  Planar Separators  [Kozen 15]  
22  02/28 M  NPCompleteness 1 (Introduction)  [Kozen 21, 22, 23, 24] [CLR 36]  
23  03/02 W  NPCompleteness 2 (Random NP Problems)  [Kozen 21, 22, 23, 24] [CLR 36]  
24  03/04 F  MidSemester Break; No Class   
 03/07 M   (Spring Break)   
 03/09 W   (Spring Break)   
 03/11 F   (Spring Break)   
25  03/14 M  NPCompleteness 3 (NP, coNP, NPhard, Independent Set)  [Kozen 21, 22, 23, 24] [CLR 36]  
26  03/16 W  NPCompleteness 4 (Independent Set and Cook's Theorem)  [Kozen 21, 22, 23, 24] [CLR 36]  
27  03/18 F  NPCompleteness 5 (Cook's Theorem)  [Kozen 21, 22, 23, 24] [CLR 36]  
28  03/21 M  NPCompleteness 6 (Hamiltonian Cycle to SAT)  [Kozen 21, 22, 23, 24] [CLR 36]  
29  03/23 W  Guest Lecturer: Anupam Gupta on Approximation Algorithms  [CLR 37]  Homework 4 (PS) Solution (PS)

30  03/25 F  Randomized 2SAT   
31  03/28 M  Polynomial identity checking  [Kozen 40] [M&R 7.2]  
32  03/30 W  Polynomial identity checking  [Kozen 40] [M&R 7.2]  
33  04/01 F  Midterm 2   
34  04/04 M  Matching  [Kozen 19, 20] [M&R 7.3]  
35  04/06 W  RP, Randomized Algorithms  Test of Associativity   
36  04/08 F  RP, Randomized Algorithms   
37  04/11 M  Random Walks  1, 2, and 3 dimensions  [M&R 6]  
38  04/13 W  String and Set Equality   
39  04/15 F  No class (Spring Carnival)   Homework 5 (PS) Solution 
40  04/18 M  Random Walks on General Graph  [M&R 6]  
41  04/20 W  How to Write a Proof   
42  04/22 F  The probabilistic method  MaxCut; Randomized and Deterministic 1/2Approximation Algorithms for MaxCut  [M&R 5.1]  
43  04/25 M  Final Review by Chris and Virginia   
45  04/27 W  Free Cake: Cake Cutting   
44  04/29 F  "Sunny" Day, No Class   
46  05/05 Thursday  Final Exam. 8:30a.m. to 11:30a.m. DH 2302   