Day  Date  Inst  Topics Covered  Notes and Readings 

Mon  Aug 25  (A)  Lecture 1: Introduction, Median Finding  [Ch 9/Ch 2.4] 
Tue  Aug 26  Recitation 1  BigOh and recurrences  [Ch 3,4/Ch 0,2.2]  HW 1 out  
Wed  Aug 27  (A)  Lecture 2: Concrete Models and Lower Bounds  [Ch 8.1/Ch 2.3] 
Mon  Sep 1  Labor Day Holiday!  
Tue  Sep 2  Recitation 2  Lower/upper bounds  HW 1 due (solution)  HW 2 out   
Wed  Sep 3  (D)  Lecture 3: Amortization Notes 1 Notes 2  [Ch 17] 
Mon  Sep 8  (D)  Lecture 4: Splay Trees (extra notes)  
Tue  Sep 9  Recitation 3  Splay trees, amortized analysis  HW 2 due (solution)   
Wed  Sep 10  (D)  Lecture 5: Hashing: Universal and Perfect Notes  [Ch 11/Ch 1.5] 
Thur  Sep 11  HW 3 out  
Mon  Sep 15  (D)  Lecture 6: Hashing, Fingerprinting, etc. Notes  
Tue  Sep 16  Recitation 4  Hashing and Basic Probability  
Wed  Sep 17  (A)  Lecture 7: UnionFind and MSTs  
Thur  Sep 18  HW 3 due (solution)  HW 4 (oral) out  
Mon  Sep 22  (A)  Lecture 8: Dynamic Programming I  [Ch 15, 24.1, 25.125.2/Ch 6] 
Tue  Sep 23  Recitation 5  Dynamic Programming  
Wed  Sep 24  (A)  Lecture 9: Dynamic Programming II  
Mon  Sep 29  (D)  Lecture 10: Network Flows I  [Ch 26/7.27.3] 
Tue  Sep 30  Recitation 6  Max Flow  (HW4 solution)  
Wed  Oct 1  (D)  Lecture 11: [Network Flows II] [Dinic's Algorithm]  
Thur  Oct 2  HW 5 out  
Mon  Oct 6  (D)  Lecture 12: NonBipartite Matchings and Blossoms preliminary notes  
Tue  Oct 7  Recitation 7  Midterm Review  
Wed  Oct 8  (A)  Lecture 13: Linear Programming 0: Game Theory and Zerosum Games  
Thur  Oct 9  HW 5 due (sols)  
Mon  Oct 13  Inclass Midterm  
Tue  Oct 14  Recitation 8  Zerosum Games  
Wed  Oct 15  (A)  Lecture 14: Linear Programming I: basics  
Thur  Oct 16  HW 6 (oral) out  
Mon  Oct 20  (A)  Lecture 15: Linear Programming II: Duality  
Tue  Oct 21  Recitation 9  Linear Programming  
Wed  Oct 22  (A)  Lecture 16: NP Completeness I  
Mon  Oct 27  (A)  Lecture 17: NP Completeness II  (HW6 sols) 
Tue  Oct 28  Recitation 10  NP Completeness Colorability  
Wed  Oct 29  (A)  Lecture 18: Combating NP Hardness  
Thur  Oct 30  HW 7 out  
Mon  Nov 3  (D)  Lecture 19: String Algorithms and Suffix Trees  
Tue  Nov 4  Recitation 11  Approximation Algorithms and Suffix Trees  
Wed  Nov 5  (A)  Lecture 20: Streaming Algorithms for Big Data  
Thur  Nov 6  HW 7 due (solutions)  HW 8 out  
Mon  Nov 10  (D)  Lecture 21: Online Algorithms  
Tue  Nov 11  Recitation 12  Paging Number of Distinct Elements  
Wed  Nov 12  (D)  Lect 22: Computational Geometry I  Intro and Convex Hull notes  
Thur  Nov 13  HW 8 due  HW 9 (oral) out  
Mon  Nov 17  (D)  Lect 23: Computational Geometry II  Closest pairs notes1 O(n) alg O(n log n) alg 

Tue  Nov 18  Recitation 13  Segment Trees BentleyOttman Algorithm Backward Analysis Problem 

Wed  Nov 19  (D)  Lecture 24: Computational Geometry III SweepLine Segment Intersection (Demaine notes) Randomized Linear Time 2D LP (Miller notes) 

Mon  Nov 24  (A)  Lecture 25: Machine Learning
Algorithms, Slides Some proofs. (A.Blum survey) 
HW 10 out 
Tue  Nov 25  Recitation 14  
Wed  Nov 26  Thanksgiving Holiday!  
Mon  Dec 1  (A)  Lecture 26: The Gradient Descent Framework Vishnoi notes: see Sections 14.1 and Thm 8 proof. Optional: Hazan notes: Theorem 2.3 for faster convergence. 

Tue  Dec 2  Recitation 15  HW 10 due  
Wed  Dec 3  (D)  Lecture 27: Fast Fourier Transforms notes (txt) notes (pdf) 