Schedule
Links
- PDF Schedule (last updated January 5th 2025)
- Cumulative Lecture Notes (all lectures in one document)
Week 1
| Tue 14-Jan | Lecture 1: Introduction, Algorithm Analysis, Linear-time Selection | [Notes] [Slides] |
| Thu 16-Jan | Lecture 2: Concrete Models and Lower Bounds | [Notes] [Slides] |
| Homework 1 released | [Homework 1] | |
| Fri 17-Jan | Recitation 1: Lower Bounds | [Recitation 1] [Solutions] |
Week 2
| Tue 21-Jan | Lecture 3: Integer Models and Integer Sorting | [Notes] [Slides] |
| Wed 22-Jan | Homework 1 due | [Solutions] |
| Thu 23-Jan | Lecture 4: Hashing: Universal and Perfect Hashing | [Notes] [Slides] |
| Homework 2 released | [Homework 2] | |
| Fri 24-Jan | Recitation 2: Integer Sorting and Hashing | [Recitation 2] [Solutions] |
Week 3
| Tue 28-Jan | Lecture 5: Fingerprinting | [Notes] [Slides] |
| Programming Problem 1 Released | [Programming 1] | |
| Wed 29-Jan | Homework 2 due | [Solutions] |
| Thu 30-Jan | Lecture 6: Streaming Algorithms | [Notes] [Slides] |
| Homework 3 released | [Homework 3] | |
| Fri 31-Jan | Recitation 3: Fingerprinting and Streaming | [Recitation 3] [Solutions] |
Week 4
| Tue 04-Feb | Lecture 7: Amortized Analysis | [Notes] [Slides] |
| Wed 05-Feb | Homework 3 orals | |
| Thu 06-Feb | Lecture 8: Union-Find (More Amortized Analysis!) | [Notes] [Slides] |
| Homework 3 orals | ||
| Fri 07-Feb | Recitation 4: Amortized Analysis and Union Find | [Recitation 4] [Solutions] |
| Homework 3 orals | [Solutions] | |
| Programming Problem 1 due |
Week 5
| Tue 11-Feb | Midterm One at 7:00pm | |
| Thu 13-Feb | Lecture 9: Range Query Data Structures | [Notes] [Slides] |
| Homework 4 released | [Homework 4] | |
| Fri 14-Feb | Recitation 5: Range Queries | [Recitation 5] [Solutions] |
Week 6
| Tue 18-Feb | Lecture 10: Dynamic Programming I | [Notes] [Slides] |
| Programming Problem 2 Released | [Programming 2] | |
| Wed 19-Feb | Homework 4 due | [Solutions] |
| Thu 20-Feb | Lecture 11: Dynamic Programming II | [Notes] [Slides] |
| Homework 5 released | [Homework 5] | |
| Fri 21-Feb | Recitation 6: Dynamic Programming | [Recitation 6] [Solutions] |
Week 7
| Tue 25-Feb | Lecture 12: Network Flows I: Flows, Cuts, and Matchings | [Notes] [Slides] |
| Wed 26-Feb | Homework 5 due | [Solutions] |
| Thu 27-Feb | Lecture 13: Network Flows II: Polynomial-time Algorithms and Minimum-cost Flows | [Notes] [Slides] |
| Fri 28-Feb | Recitation 7: Network Flow | [Recitation 7] [Solutions] |
| Programming Problem 2 due |
Spring Break!
| Mon 03-Mar | Spring Break begins | |
| Fri 07-Mar | Spring Break ends |
Week 8
| Tue 11-Mar | Lecture 14: Game Theory | [Notes] [Slides] |
| Programming Problem 3 Released | [Programming 3] | |
| Thu 13-Mar | Lecture 15: Linear Programming | [Notes] [Slides] |
| Homework 6 released | [Homework 6] | |
| Fri 14-Mar | Recitation 8: Game Theory and LPs | [Recitation 8] [Solutions] |
Week 9
| Tue 18-Mar | Lecture 16: Linear Programming II: Duality | [Notes] [Slides] |
| Wed 19-Mar | Homework 6 orals | |
| Thu 20-Mar | Lecture 17: Linear Programming III: Seidel's Algorithm | [Notes] [Slides] |
| Homework 6 orals | ||
| Fri 21-Mar | Recitation 9: More Linear Programming | [Recitation 9] [Solutions] |
| Homework 6 orals | [Solutions] | |
| Programming Problem 3 due |
Week 10
| Tue 25-Mar | Midterm Two at 7:00pm | |
| Thu 27-Mar | Lecture 18: Online Learning and the Multiplicative Weights Algorithm | [Notes] [Slides] |
| Homework 7 released | [Homework 7] | |
| Fri 28-Mar | Recitation 10: Online Learning and the Multiplicative Weights Algorithm | [Recitation 10] [Solutions] |
Week 11
| Tue 01-Apr | Lecture 19: Approximation Algorithms | [Notes] [Slides] |
| Wed 02-Apr | Homework 7 due | [Solutions] |
| Thu 03-Apr | Carnival begins | |
| Sat 05-Apr | Carnival ends |
Week 12
| Tue 08-Apr | Lecture 21: Online Algorithms | [Notes] [Slides] |
| Programming Problem 4 Released | [Programming 4] | |
| Thu 10-Apr | Lecture 22: Computation Geometry I: Fundamentals and the Convex Hull | [Notes] [Slides] |
| Homework 8 released | [Homework 8] | |
| Fri 11-Apr | Recitation 11: Approximation and Online Algorithms | [Recitation 11] [Solutions] |
| Programming Problem 4 due |
Week 13
| Tue 15-Apr | Lecture 23: Computational Geometry II: Randomized Incremental Algorithms | [Slides] |
| Wed 16-Apr | Homework 8 due | [Solutions] |
| Thu 17-Apr | Lecture 20: The Algorithmic Magic of Polynomials | [Notes] [Slides] |
| Homework 9 released | [Homework 9] | |
| Fri 18-Apr | Recitation 12: Computational Geometry | [Recitation 12] [Solutions] |
Week 14
| Tue 22-Apr | Lecture 24: The Fast Fourier Transform | [Slides] |
| Wed 23-Apr | Homework 9 orals | |
| Thu 24-Apr | Lecture 25: Gradient Descent | [Slides] |
| Homework 9 orals | ||
| Fri 25-Apr | Recitation 13: Polynomials, FFT, Gradient Descent | [Recitation 13] [Solutions] |
| Homework 9 orals | [Solutions] |
Finals
| TBD | Final Exam |