| Day | Date | Inst | Topics Covered | Notes and Readings | HWs/Quizzes | |
|---|---|---|---|---|---|---|
| Tue | 02-Feb | (DW) | Lec 01: Intro & Admin. Linear-time Selection
(randomized and deterministic); recursion trees slides, notes, video, handout on recurrences |
[Ch 9/Ch 2.4] | HW1 Out and Programming Tips | |
| Thu | 04-Feb | (DW) | Lec 02: Concrete models and tight upper/lower bounds slides, notes, video |
[Ch 8.1/Ch 2.3] | Q1 | |
| Fri | 05-Feb | Rec 01: big-O, recurrences, probability, and concrete models
worksheet
solutions |
||||
| Tue | 09-Feb | (DS) | Lec 03: Amortized Analysis notes, video | [Ch 17/-] | ||
| Thu | 11-Feb | (DS) | Lec 04: Splay Trees notes, video, review | Q2 | ||
| Fri | 12-Feb | Rec 02: Amortized Analysis and Splay Trees worksheet (solutions) | ||||
| Tue | 16-Feb | (DW) | Lec 05: Hashing I: Universal and Perfect Hashing slides, notes, video | [Ch 11/Ch 1.5] | HW2 Out | |
| Thu | 18-Feb | (DW) | Lec 06: Hashing II: Streaming Algorithms slides, notes, video | Q3 | ||
| Fri | 19-Feb | Rec 03: Hashing and Streaming worksheet solutions | ||||
| Tue | 23-Feb | No Classes | ||||
| Thu | 25-Feb | (DW) | Lec 07: Hashing III: Fingerprinting and other applications slides, notes, video | Q4 | ||
| Fri | 26-Feb | Rec 04: Fingerprinting worksheet solutions | HW1 Grade Dist. | |||
| Tue | 2-Mar | (DS) | Lec 08: Dynamic Programming I notes video | |||
| Thu | 4-Mar | Midterm Exam | HW3 out |
|||
| Fri | 5-Mar | Rec 05: DPs worksheet solutions | ||||
| Tue | 9-Mar | (DS) | Lec 09: Dynamic Programming II: graph algorithms, including shortest paths (Bellman-Ford) and all-pairs SP (matrix, Floyd-Warshall) notes video-2020 video-2021 | [Ch 15, 24.1, 25.1-25.2/Ch 6] | ||
| Thu | 11-Mar | (DS) | Lec 10: Network Flows I: Flows and Matchings notes video | Q5 | ||
| Fri | 12-Mar | Rec 06: DPs and Network Flows worksheet solutions | ||||
| Mon | 15-Mar | HW3 Due, HW4 Out | ||||
| Tue | 16-Mar | (DS) | Lec 11: Network Flows II: Advanced Flow Algorithms notes video implementation video code1 code2 code3 | [Ch 26/7.2-7.3] | ||
| Thu | 18-Mar | (DW) | Lec 12: Linear Programming 0 and Game Theory I: Zero-sum Games, Minimax Optimality, and Connections to Algorithms slides, notes, 2-row games, video | Q6 | ||
| Fri | 19-Mar | Mid-semester Break
rec 07 worksheet
rec 07 solutions | ||||
| Tue | 23-Mar | (DW) | Lec 13: Linear Programming I: Basics slides, notes, video | [Ch 29/Ch 7.1,7.6] | ||
| Thu | 25-Mar | (DW) | Lec 14: Linear Programming II: Simplex, Seidel's 2D algorithm slides, notes, video | Q7, HW4 Due, HW5 Out | ||
| Fri | 26-Mar | Rec 08: LPs and Seidel's Algorithm worksheet solutions | ||||
| Tue | 30-Mar | (DW) | Lec 15: Linear Programming III: Duality slides, notes, video | |||
| Thu | 1-Apr | (DS) | Lec 16: Approximation Algorithms notes, slides video, | Q8 | ||
| Fri | 2-Apr | Rec 09: LP Duality and Approximation Algorithms worksheet solutions | ||||
| Tue | 6-Apr | (DS) | Lec 17: Online Algorithms notes MARKING-notes video | HW5 Due | ||
| Thu | 8-Apr | Midterm Exam | HW6 out | |||
| Fri | 9-Apr | Rec 10: Online Algorithms and Midterm Discussion worksheet solutions | ||||
| Tue | 13-Apr | (DW) | Lec 18: Multiplicative Weights Algorithm notes, slides, panopto | |||
| Thu | 15-Apr | No Classes | ||||
| Fri | 16-Apr | No Classes | ||||
| Tue | 20-Apr | (DS) | Lec 19: Computational Geometry I: Geometric Primitives and Convex Hull notes, video | |||
| Thu | 22-Apr | (DS) | Lec 20: Computational Geometry II -- Sweepline and SegTrees Sweepline notes, SegTree notes, video | Q9, HW6 Due | ||
| Fri | 23-Apr | Rec 11: Multiplicative Weights and Computational Geometry worksheet solutions | HW7 out | |||
| Tue | 27-Apr | (DS) | Lec 21: Computational Geometry III -- Closest Pair (CP) and Smallest Enclosing Circle (SEC), CP Notes, SEC Slides, SEC Book, video(2021), video(2020, CP Grid Algorithm see 0:35-1:09) | |||
| Thu | 29-Apr | (DW) | Lec 22: Strassen and Karatsuba's Algorithms notes, slides, video | Q10 | ||
| Fri | 30-Apr | Rec 12: Computational Geometry and Multiplication worksheet solutions | ||||
| Tue | 4-May | (DS) | Lec 23: Fast Fourier Transform, and Applications notes, video | |||
| Wed | 5-May | HW7 Due, Rect Soln | ||||
| Thu | 6-May | (DW) | Lec 24: The Algorithmic Magic of Polynomials notes, slides, video | Q11 | ||
| Fri | 7-May | Rec 13: FFT and Polynomials worksheet solutions |
