| 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 - Big-Oh 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: Union-Find 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.1-25.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.2-7.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: Non-Bipartite Matchings and Blossoms preliminary notes | |
| Tue | Oct 7 | Recitation 7 - Midterm Review | ||
| Wed | Oct 8 | (A) | Lecture 13: Linear Programming 0: Game Theory and Zero-sum Games | |
| Thur | Oct 9 | HW 5 due (sols) | ||
| Mon | Oct 13 | In-class Midterm | ||
| Tue | Oct 14 | Recitation 8 - Zero-sum 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 Bentley-Ottman Algorithm Backward Analysis Problem |
||
| Wed | Nov 19 | (D) | Lecture 24: Computational Geometry III Sweep-Line 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 1-4.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) |