"CLRS", "DPV" and "KT" columns show readings in the respective texts. Schedule may be subject to change!


 Date Topic CLRS    DPV KT    Due
1. 01/15 Intro & Admin. Karatsuba/Strassen.   2.1,2.5    
2. 01/17 Asymptotic analysis, solving recurrences 1-4 0, 2.1-2.2 2.1-2.2,5.2  
3. 01/22 Probabilistic analysis, Randomized Quicksort 5,7 p.29 13.3,13.12    Mini 1 due
4. 01/24 Linear-time Selection (randomized and deterministic) 9 2.3-2.4 13.5  
5. 01/29 Sorting/searching lower bounds 8.1   2.4 Hwk 1 due
6. 01/31 Tight upper/lower bounds II        
7. 02/5 Amortized Analysis 17     Mini 2 due
7.5 02/6 A randomized search tree        
8. 02/7 Search trees: B-trees, treaps 12,18      
9. 02/12 Radix sort, tries 8     Hwk 2 pres
10. 02/14 Hashing: universal & perfect hashing 11 1.5 13.6  
11. 02/19 Dynamic Programming + QUIZ 15 6 6.1-6.7 Mini 3 due
12. 02/21 Graph Algorithms I 22,23 3,4.1-4.3, 5.1 3  
13. 02/26 Graph Algorithms II 21   4.4,6.8-6.10
14. 02/28 Midterm Review        
15. 03/4 MIDTERM        
16. 03/6 Graph Algorithms III 24,25 4.4-4.7 4.5-4.6 Hwk 3 due
17. 03/18 Graph Algorithms IV
18. 03/20 Network Flows and Matchings I 26 7.1 7
19. 03/25 Network Flows and Matchings II       Week of Hw 4
presentations
20. 03/27 Linear Programming 29 7.4, 7.6 11.6
21. 4/1 NP-Completeness I 34 8 8.1-8.3 Mini 4
22. 04/3 NP-Completeness II     8.4-8.10
23. 04/8 NP-Completeness III HW 5 due
24. 04/10 Approximation Algorithms + QUIZ 35 9.2 11
25. 04/15 On-line algorithms        
26. 04/22 Number-theoretic algs I 31 1.1-1.4   Week of HW 6
presentations
27. 04/24 Number-theoretic algs II      
28. 04/29 Number-theoretic algs III (FFT) 30 2.6 5.6 Mini 5
29. 05/1 Fair division, envy-free cake-cutting