| Day | Date | Inst | Topics Covered | Readings | Due Dates/Extras | |
|---|---|---|---|---|---|---|
| Tue | 18-Jan | (D) | Lec 01: Intro & Admin. Linear-time Selection
(randomized and deterministic); recursion trees notes, slides, video |
[Ch 9/Ch 2.4] | Programming Tips, handout on recurrences | |
| Thu | 20-Jan | (E) | Lec 02: Concrete models and tight upper/lower bounds notes, slides, video, comic 1, comic 2, evasiveness video (first 20 minutes) |
[Ch 8.1/Ch 2.3] | Q1 HW1 Out |
|
| Fri | 21-Jan | Rec 01: big-O, recurrences, probability, and concrete models worksheet (solutions) | ||||
| Tue | 25-Jan | (E) | Lec 03: Amortized Analysis notes, slides, video | [Ch 17/-] | ||
| Thu | 27-Jan | (D) | Lec 04: Splay Trees notes, video, last year video, applications video | Q2 | ||
| Fri | 28-Jan | Rec 02: Amortized Analysis and Splay Trees worksheet (solutions) | ||||
| Sun | 30-Jan | HW1 Written Due | ||||
| Tue | 01-Feb | (E) | Lec 05: Hashing I: Universal and Perfect Hashing notes, slides, video | [Ch 11/Ch 1.5] | HW2 Out | |
| Thu | 03-Feb | (E) | Lec 06: Hashing II: Streaming Algorithms notes, slides, video | Q3 HW1 Programming Due |
||
| Fri | 04-Feb | Rec 03: Hashing and Streaming worksheet (solutions) | ||||
| Tue | 08-Feb | (D) | Lec 07: Hashing III: Fingerprinting and other applications notes, video | |||
| Wed | 09-Feb | HW2 Oral Presentations (09-Feb to 11-Feb) | ||||
| Thu | 10-Feb | (D) | Lec 08: Dynamic Programming I notes, video | Q4 | ||
| Fri | 11-Feb | Rec 04: Fingerprinting and Dynamic Programming worksheet (solutions) | ||||
| Tue | 15-Feb | Midterm 1 | ||||
| Thu | 17-Feb | (D) | Lec 09: 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] | Q5 | |
| Fri | 18-Feb | Rec 05: Dynamic Programming worksheet (solutions) | HW2 Programming Due, HW3 Out | |||
| Tue | 22-Feb | (DA) | Lec 10: Network Flows I: Flows and Matchings notes, video | |||
| Thu | 24-Feb | (DA) | Lec 11: Network Flows II: Edmonds-Karp and Min-cost Flows notes, Dinic's Algorithm (optional) video | Q6 | ||
| Fri | 25-Feb | Rec 06: Network Flows worksheet (solutions) | ||||
| Mon | 28-Feb | HW3 Written Due | ||||
| Tue | 01-Mar | (D) | Lec 12: Zero Sum Games notes, video | HW4 Out | ||
| Thu | 03-Mar | (D) | Lec 13: Linear Programming I notes, video | [Ch 29/Ch 7.1,7.6] | HW3 Programming Due | |
| Fri | 04-Mar | Mid-Semester Break
Rec 07: Linear Programming worksheet (solutions) |
||||
| Tue | 08-Mar | Spring Break | ||||
| Thu | 10-Mar | Spring Break | ||||
| Fri | 11-Mar | Spring Break | ||||
| Tue | 15-Mar | (D) | Lec 14: Linear Programming II, notes, slides, video | HW4 Written Due
Feedback Form Due HW5 Out |
||
| Thu | 17-Mar | (E) | Lec 15: Mechanism Design notes, slides, video | Q7 | ||
| Fri | 18-Mar | Rec 08: Duality and Mechanism Design worksheet (solutions) | ||||
| Tue | 22-Mar | (E) | Lec 16: Approximation Algorithms notes, slides, video | |||
| Wed | 23-Mar | HW5 Oral Presentations (23-Mar to 25-Mar) | ||||
| Thu | 24-Mar | (D) | Lec 17: Online Algorithms notes, scanned-notes, lecture, marking lecture s21 | Q8 | ||
| Fri | 25-Mar | Rec 09: Approximation + Online Algorithms worksheet (solutions) | ||||
| Tue | 29-Mar | Midterm 2 | ||||
| Thu | 31-Mar | (D) | Lec 18: Multiplicative Weights Algorithm notes, Video2022, Video2020 | Q9 | ||
| Fri | 01-Apr | Rec 10: Multiplicative Weights worksheet (solutions) | ||||
| Sat | 02-Apr | HW5 Programming Due HW6 Out | ||||
| Tue | 05-Apr | (D) | Lec 19: Computational Geometry I: Geometric Primitives and Convex Hull notes, video | |||
| Thu | 07-Apr | Carnival! | ||||
| Fri | 08-Apr | Carnival! | ||||
| Tue | 12-Apr | (D) | Lec 20: Computational Geometry II: Sweepline, Sweepangle, and SegTrees Sweep* notes, SegTree notes, Slides, video | |||
| Thu | 14-Apr | (D) | Lec 21: Computational Geometry III: Closest Pair and Smallest Enclosing Circle CP Notes, SEC Slides, video | Q10 HW6 Written Due |
||
| Fri | 15-Apr | Rec 11: Computational Geometry worksheet (solutions) | HW7 Out | |||
| Tue | 19-Apr | (E) | Lec 22: Byzantine Agreement lecture notes: Chapter 3 of "Foundations of Distributed Consensus and Blockchains" textbook, slides, lecture video | |||
| Thu | 21-Apr | (E) | Lec 23: Oblivious Algorithms lecture notes, lecture video, slides | Q11 | ||
| Fri | 22-Apr | Rec 12: Byzantine Agreement and Oblivious Algorithms worksheet (solutions) | ||||
| Mon | 25-Apr | HW7 Oral Presentations (25-Apr to 27-Apr) | ||||
| Tue | 26-Apr | (D) | Lec 24: Fast Fourier Transform, and Applications notes, s21-lecture-video, s22-lecture-video | |||
| Thu | 28-Apr | (E) | Lec 25: The Algorithmic Magic of Polynomials notes, video | Q12 | ||
| Fri | 29-Apr | Rec 13: FFT, Multiplication, and Polynomials worksheet (solutions) | HW7 Programming Due | |||
| Fri | 6-May | Final Exam (5:30-8:30pm) |