| Day | Date | Inst | Topics Covered | Notes and Readings | HWs/Quizzes | |
|---|---|---|---|---|---|---|
| Tue | 14-Jan | (DW) | Lec1: Intro & Admin. Linear-time Selection (randomized and deterministic); recursion trees. slides, notes from previous year, handout on recurrences |
[Ch 9/Ch 2.4] | HW1 Out and Programming Tips HW1 Solutions | |
| Thu | 16-Jan | (DW) | Lec2: Concrete models and tight upper/lower bounds. slides, notes from previous year, comic 1, comic 2 |
[Ch 8.1/Ch 2.3] | Q1 | |
| Fri | 17-Jan | Rec1: big-O, recurrences, probability, and concrete models
worksheet
solutions |
||||
| Tue | 21-Jan | (DS) | Lec3: Amortized Analysis notes | [Ch 17/-] | ||
| Thu | 23-Jan | (DS) | Lec4: Splay Trees notes, video | Q2 | ||
| Fri | 24-Jan | Rec2: Amortized Analysis and Splay Trees (worksheet) (solutions) | ||||
| Tue | 28-Jan | (DW) | Lec5: Hashing I: Universal and Perfect Hashing. slides, notes from previous year, video | [Ch 11/Ch 1.5] | HW2 Out | |
| Thu | 30-Jan | (DW) | Lec6: Hashing II: Streaming Algorithms slides, notes from previous year, video | Q3 | ||
| Fri | 31-Jan | Rec3: Hashing and Streaming (worksheet) (solutions) | ||||
| Tue | 4-Feb | (DW) | Lec7: Hashing III: Fingerprinting and other applications slides, notes from previous year, video | [H2 orals (T-F)] HW 2 Solutions | ||
| Thu | 6-Feb | (DS) | Lec8: Dynamic Programming I notes video | Q4 | ||
| Fri | 7-Feb | Rec4: Streaming, Fingerprinting, Dynamic Programming (worksheet) (solutions) | ||||
| Tue | 11-Feb | (DS) | Lec9: Dynamic Programming II: graph algorithms, including shortest paths (Bellman-Ford) and all-pairs SP (matrix, Floyd-Warshall) notes, video | [Ch 15, 24.1, 25.1-25.2/Ch 6] | HW3 out HW3 Solutions |
|
| Thu | 13-Feb | Midterm Exam | ||||
| Fri | 14-Feb | Rec5: DPs, Shortest paths (worksheet) (solutions) | ||||
| Tue | 18-Feb | (DS) | Lec10: Network Flows I: Flows and Matchings notes video | |||
| Thu | 20-Feb | (DS) | Lec11: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, and blocking flows notes video | [Ch 26/7.2-7.3] | Q5 | |
| Fri | 21-Feb | Rec6: flows and matchings (worksheet) (solutions) | ||||
| Tues | 25-Feb | (DW) | Lec12: Linear Programming 0 and Game Theory I: Zero-sum Games, Minimax Optimality, and Connections to Algorithms slides, notes, video | HW4 Out HW4 Solutions | ||
| Thur | 27-Feb | (DW) | Lec13: Linear Programming I: Basics slides, notes < video | [Ch 29/Ch 7.1,7.6] | Q6 | |
| Fri | 29-Feb | Rec7: flows and zero-sum games and LP (worksheet) (solutions) | ||||
| Tues | 3-Mar | (DW) | Lec14: Linear Programming II: Simplex, Seidel's 2D algorithm slides, notes, video | |||
| Thur | 5-Mar | (DW) | Lec15: Linear Programming III: Duality slides, notes, video | Q7 | ||
| Fri | 6-Mar | Mid-semester Break | HW5 out HW5 Solutions | |||
| Tue | ||||||
| Thu | Spring Break | |||||
| Fri | ||||||
| Tues | 17-Mar | Class canceled | [Ch 34/Ch 8] | |||
| Thur | 19-Mar | (DS) | Lec16: NP-Completeness. notes, slides, panopto-video, zoom-video | |||
| Fri | 20-Mar | Rec8: NP-completeness (worksheet) (solutions) | ||||
| Tues | 24-Mar | (DS) | Lec17: Approximation Algorithms. (notes) (slides) (panopto-video) (zoom-video) | |||
| Thurs | 26-Mar | (DS) | Lec18: Online Algorithms. (notes) (panopto-video) (zoom-video) | |||
| Fri | 27-Mar | Rec9: Approximation and Online Algorithms. (worksheet) (sols) | HW 5 Due 3/28 | |||
| Tues | 31-Mar | Midterm Exam | ||||
| Thu | 2-Apr | (DW) | Lec19: Graph Compression slides, notes, panopto video | HW6 out HW6 Solutions Q8 |
||
| Fri | 3-Apr | Rec10: Graph Compression (worksheet) (solutions) | ||||
| Tues | 7-Apr | (DS) | Lec20: Multiplicative Weights Algorithm (notes) (video) (panopto) | |||
| Thu | 9-Apr | (DS) | Lec21: Computational Geometry I: Geometric Primitives and Convex Hull (notes) (video) (panopto) | Q9 | ||
| Fri | 10-Apr | Rec11: Multiplicative Weights and Computational Geometry (worksheet) (solutions) | ||||
| Tue | 14-Apr | (DS) | Lec22: Computational Geometry II -- Sweepline and SegTrees (Sweepline notes) (SegTree notes) (video) (panopto) | |||
| Thu | 16-Apr | (DS) | Lec23: Computational Geometry III -- Closest Pair (notes) (Smallest Enclosing Circle 1) (SEC2) (video) (panopto) | Q10 | ||
| Fri | 17-Apr | Rec12: Computational Geometry (worksheet) (solutions) |
HW 6 Due 4/17 Programming Due 4/19 |
|||
| Tue | 21-Apr | (DW) | Lec24: Strassen and Karatsuba's Algorithms notes, slides, panopto video | HW 7 out
(square hints) HW 7 Sols | ||
| Thu | 23-Apr | (DW) | Lec25: The Algorithmic Magic of Polynomials notes, slides, panopto video | Q11 | ||
| Fri | 24-Apr | Rec13: Multiplication Algorithms and Polynomials | ||||
| Tue | 28-Apr | (DW) | Lec26: The Fast Fourier Transform Avrim's text file notes, Gary's pdf file notes, slides, panopto video | |||
| Thu | 30-Apr | (DW) | Lec27: Algorithmic Applications of Embeddings slides, notes, panopto video | Q12 | ||
| Fri | 1-May | Rec14: FFT, Embeddings, and Course recap (worksheet) (solutions) | ||||
| Tue | 5-May | Final 8:30 am -- 11:30 am (CMU Hub) |