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