15-451 Fall 2011 Schedule

Date Topic Reading (CLRS)   Due
1. 08/30: Intro & Admin. Karatsuba/Strassen.  
2. 09/01: Asymptotic analysis, solving recurrences1-4 
3. 09/06: Probabilistic analysis, Randomized Quicksort5,7Mini 1 due
4. 09/08: Linear-time Selection (randomized and deterministic)9 
5. 09/13: Sorting/searching lower bounds8.1Hwk 1 due
6. 09/15: Tight upper/lower bounds II  
7. 09/20: Radix sort, tries+ QUIZ 8 Mini 2 due
8. 09/22: Amortized Analysis 17 
9. 09/27: Search trees: B-trees, treaps12,18Hwk2 pres
10. 09/29: Special Lecture TBD  
11. 10/04: Hashing: universal and perfect hashing11Mini 3 due
12. 10/06: Dynamic Programming 15 
13. 10/11: Graph Algorithms I22,23Hwk 3 due
14. 10/13: Graph Algorithms II21 
15. 10/18: MIDTERM  
16. 10/20: Graph Algorithms III24,25 
17. 10/25: Network Flows and Matchings I26Hwk 4 pres
18. 10/27: Network Flows and Matchings II  
19. 11/01: Linear Programming I29Mini 4 due
20. 11/03: Linear Programming II  
21. 11/08: NP-Completeness I34Hwk 5 due
22. 11/10: NP-Completeness II  
23. 11/15: Approximation Algorithms35 
24. 11/17: On-line algorithms+ QUIZ 
25. 11/22: Number-theoretic algs I31Hwk 6 pres
26. 11/29: Number-theoretic algs II  
27. 12/01: Fast Fourier Transform30Mini 5 due
28. 12/06: Game Theory  
29. 12/08: Machine Learning Hwk 7 due