| Day | Date | Inst | Topics Covered | Notes and Readings | HWs/Quizzes | |
|---|---|---|---|---|---|---|
| Tue | 17-Jan | (D) | Lec1: Intro & Admin. Linear-time Selection (randomized and deterministic); recursion trees. (notes) (handout on recurrences) | [Ch 9/Ch 2.4] | ||
| Thu | 19-Jan | (D) | Lec2: Concrete models and tight upper/lower bounds. (notes) | [Ch 8.1/Ch 2.3] | Q1 due 11:59pm | |
| Fri | 20-Jan | Rec1: big-O, recurrences, probability and concrete models (worksheet) (solution) | H1 out | |||
| Tue | 24-Jan | (D) | Lec3: Amortized Analysis I: Binary Counters, Growing and Shrinking a Table (notes) | [Ch 17/-] | ||
| Thu | 26-Jan | (D) | Lec4: Amortized Analysis II: Splay Trees (notes) | Q2 | ||
| Fri | 27-Jan | Rec2: Amortized Analysis (worksheet) (solution) | ||||
| Tue | 31-Jan | (A) | Lec5: Amortized Analysis III: Union-find (with appendix on MSTs). (notes) | [Ch 21/5.1.3,5.1.4] | H1 sol, H2 out | |
| Thu | 2-Feb | (A) | Lec6: Hashing I: Universal and Perfect Hashing. (notes) | [Ch 11/Ch 1.5] | Q3 | |
| Fri | 3-Feb | Rec3: UF and Hashing (worksheet) (solution) | ||||
| Tue | 7-Feb | (A) | Lec7: Hashing II: Streaming Algorithms (notes) | H2 sols (signup sheet) |
||
| Thu | 9-Feb | (A) | Lec8: Hashing III: Fingerprinting and other applications (notes) | Q4 | ||
| Fri | 10-Feb | Rec4: Streaming and Fingerprinting (worksheet) (solution) | H3 out | |||
| Tue | 14-Feb | (A) | Lec9: Linear Programming 0 and Game Theory I: Zero-sum Games, Minimax Optimality, and Connections to Algorithms (notes) | |||
| Thu | 16-Feb | Midterm Exam | ||||
| Fri | 17-Feb | Rec5: zero-sum games (worksheet) (solutions) | ||||
| Tue | 21-Feb | (D) | Lec10: Dynamic Programming I: (notes) | [Ch 15, 24.1, 25.1-25.2/Ch 6] | ||
| Thu | 23-Feb | (D) | Lec11: Dynamic programming II: graph algorithms, including shortest paths (Bellman-Ford) and all-pairs SP (matrix, Floyd-Warshall), and TSP (subset DP). (notes) | H3 sol | ||
| Fri | 24-Feb | Rec6: DPs and shortest paths (worksheet) (solution) | H4 out, Q5 | |||
| Tue | 28-Feb | (D) | Lec12: Network Flows I: Flows and Matchings (notes) | [Ch 26/7.2-7.3] | ||
| Thu | 2-Mar | (D) | Lec13: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, Dinic's Alg and Blocking Flows (notes) | Q6 | ||
| Fri | 3-Mar | Rec7: flows (worksheet) (sols) | ||||
| Tue | 7-Mar | (D) | Lec14: Linear Programming I: Basics (notes) | [Ch 29/Ch 7.1,7.6] | H4 orals [7-10 Mar](signup sheet) | |
| Thu | 9-Mar | (A) | Lec15: Linear Programming II: Simplex, Seidel's 2D algorithm? (notes) | H4 sol,H5 out, Q7 | ||
| Fri | 10-Mar | Mid-semester Break | ||||
| 13-18 | Spring Break | |||||
| Tue | 21-Mar | (A) | Lec16: Linear Programming III: Duality (notes) | |||
| Thu | 23-Mar | (A) | Lec17: NP-completeness (notes) | Q8 | ||
| Fri | 24-Mar | Rec8: LPs, NP-comp and test prep (worksheet) (sols) | ||||
| Tue | 28-Mar | (A) | Lec18: Approximation Algorithms. (notes) | [Ch 35/Ch 9.2] | H5 sol,H5 due | |
| Thu | 30-Mar | Midterm Exam | ||||
| Fri | 31-Mar | Rec9: NP-comp and Approx(notes)(solutions) | H6 out | |||
| Tue | 4-Apr | (D) | Lec19: Powerful Arrays: SegTrees and Fenwick Trees(notes) | |||
| Thu | 6-Apr | (A) | Lec20: Game Theory II: Auctions and the VCG Mechanism (notes) | Q9 | ||
| Fri | 7-Apr | Rec10: Auctions and seg-trees (worksheet) (sols) | ||||
| Tue | 11-Apr | (D) | Lec21: Computational Geometry I --- Intro and Convex Hull (notes) | |||
| Thu | 13-Apr | (D) | Lec22: Computational Geometry II --- Sweepline algorithms (notes) | Q10 | ||
| Fri | 14-Apr | Rec11: comp.geom. (worksheet) (sols) | ||||
| Tue | 18-Apr | (A) | Lec23: Online Algorithms. (notes) | H6 due, H6 sol, H7 out | ||
| Thu | 20-Apr | Carnival | ||||
| Fri | 21-Apr | Carnival | ||||
| Tue | 25-Apr | (D) | Lec24: Closest Pair (notes) | |||
| Thu | 27-Apr | (D) | Lec25: The Multiplicative Weights Algorithm (notes) | Q11 | ||
| Fri | 28-Apr | Rec12: Online and Random Incremental (worksheet) (sols) | ||||
| Tue | 2-May | (A) | Lec26: High-Dimensional Optimization: Gradient Descent (notes) | H7 orals [1-4 May](Signup Sheet), H7 sol | ||
| Thu | 4-May | (A) | Lec27: The Power of Polynomials (e.g., Matching), and Course Wrapup (notes) | Q12 | ||
| Fri | 5-May | Rec13: Gradient Descent and Polynomials (worksheet) (sols) | ||||
| Sun | 7-May | Final Review Session: 1pm to 4pm, at Gates 4401 (Rashid Auditorium) | practice final | |||
| Tue | 9-May | Final: 5:30-8:30pm, location DH2210/2105/2122 (CMU Hub) |