| Day | Date | Inst | Topics Covered | Reading | HWs |
|---|---|---|---|---|---|
| Tue | Aug 29 | (D) | Lec 1: Intro & Admin. Linear-time Selection (randomized and deterministic); recursion trees (notes) (handout on recurrences) | [Ch 9/Ch 2.4] | |
| Thu | Aug 31 | (C) | Lec 2: Concrete models and tight upper/lower bounds (notes) | [Ch 8.1/Ch 2.3] | |
| Fri | Sep 1 | Reci 1: Lower and Upper Bounds (worksheet + solutions) | HW1 Out | ||
| Tue | Sep 5 | (D) | Lec 3: Amortized Analysis I: Binary Counters, Growing and Shrinking a Table (notes) | [Ch 17/-] | |
| Thu | Sep 7 | (D) | Lec 4: Amortized Analysis II: Splay Trees (notes) (Splay tree demo) | ||
| Fri | Sep 8 | Reci 2: Amortized analysis (worksheet, solutions) | HW1 Due | ||
| Tue | Sep 12 | (D) | Lec 5: Powerful Arrays: SegTrees and Fenwick Trees (notes) | HW2 Out | |
| Thu | Sep 14 | (C) | Lec 6: Hashing I: Universal and Perfect Hashing (notes) | [Ch 11/-] | |
| Fri | Sep 15 | Reci 3: Hashing, Basic Probability, and SegTrees (worksheet, solution) | [Ch 5/-] | ||
| Tue | Sep 19 | (C) | Lec 7: Hashing II: Streaming Algorithms (heavy hitters) (notes) | ||
| Thu | Sep 21 | (C) | Lec 8: Hashing III: Fingerprinting and other applications (notes) | [Ch. 32.2] | |
| Fri | Sep 22 | Reci 4: Streaming and hashing (worksheet, solutions) | HW2 Due (solution) | ||
| Tue | Sep 26 | (C) | Lec 9: Classic String Matching: Knuth-Morris-Pratt (KMP) and Boyer-Moore (notes) | [Ch. 32] | HW3 Out |
| Thu | Sep 28 | (C) | Lec 10: Suffix trees and arrays (notes) | ||
| Fri | Sep 29 | Reci 5: Fingerprint Oracle and Computing Suffix Arrays (worksheet, solutions) | |||
| Tue | Oct 3 | Midterm #1 | |||
| Thu | Oct 5 | (D) | Lec 11: DFS and Strong Components (notes) | [Ch 22.3,22.5 / Ch 3] | |
| Fri | Oct 6 | Reci 6: Graph algorithms (worksheet, solutions) | |||
| Tue | Oct 10 | (D) | Lec 12: Dynamic Programming I: (notes) | [Ch 15, 24.1, 25.1-25.2/Ch 6] | HW3 Due (solution); HW4 Out |
| Thu | Oct 12 | (D) | Lec 13: Dynamic programming II: graph algorithms, including shortest paths (Bellman-Ford) and all-pairs SP (matrix, Floyd-Warshall), and TSP (subset DP) (notes) | ||
| Fri | Oct 13 | Reci 7: Dynamic programming (worksheet, solutions) | |||
| Tue | Oct 17 | (C) | Lec 14: Game Theory I: Zero-sum Games, Minimax Optimality, and Connections to Algorithms (notes) | ||
| Thu | Oct 19 | (D) | Lec 15: Network Flows I: Flows and Matchings (notes) | [Ch 26/7.2-7.3] | |
| Fri | Oct 20 | Midsem break; No recitation | HW4 Due (solution) | ||
| Tue | Oct 24 | (D) | Lec 16: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, Dinic's Alg and Blocking Flows (notes) | HW5 Out | |
| Thu | Oct 26 | (C) | Lec 17: Linear Programming I: Basics (notes) | [Ch 29/Ch 7] | |
| Fri | Oct 27 | Reci 8: Flows (worksheet, solutions) | |||
| Tue | Oct 31 | (C) | Lec 18: Linear Programming II: Algorithms, e.g. Seidel's 2D algorithm (notes) (bonus optional material: Simplex Algorithm, Code) | [Ch 29/Ch 7] | |
| Thu | Nov 2 | (D) | Lec 19: Linear Programming III: Duality (notes) | [Ch 29.4] | |
| Fri | Nov 3 | Reci 9: Linear programming (worksheet, solutions) | HW5 Due 11/5(solution) | ||
| Tue | Nov 7 | Midterm #2 | |||
| Thu | Nov 9 | (D) | Lec 20: Computational Geometry I --- Intro and Convex Hull (notes) | [Ch 33.1-33.3] | HW6 Out |
| Fri | Nov 10 | CMU 50th Anniversery --- no recitation | |||
| Tue | Nov 14 | (C) | Lec 21: Computational Geometry II --- Sweepline algorithms (notes) | ||
| Thu | Nov 16 | (C) | Lec 22: Computational Geometry III --- Closest Pair (notes) | [33.4] | |
| Fri | Nov 17 | Reci 10: Computational Geometry (worksheet, solutions) | |||
| Tue | Nov 21 | (C) | Lec 23: NP-completeness (notes) | [Ch 34/Ch 8] | |
| Wed | Nov 22 | HW6 Due | |||
| Thu | Nov 23 | Thanksgiving --- no class | |||
| Tue | Nov 28 | (C) | Lec 24: Approximation Algorithms (notes) | [Ch 35/Ch 9.2] | HW7 Out |
| Thu | Nov 30 | (D) | Lec 25: Online Algorithms (notes) | ||
| Fri | Dec 1 | Reci 11: NP-completeness (worksheet, solutions) | |||
| Tue | Dec 5 | (D) | Lec 26: The Multiplicative Weights Algorithm (notes) | ||
| Thu | Dec 7 | (CD) | Lec 27: Fibonacci Heaps (notes) | HW7 Due | |
| Fri | Dec 8 | Reci 12: Multiplicative Weights, and Review (worksheet, solutions) |