We’ve done our best to synchronize a breadth of materials developed over this course’s history for your reference. But be aware that some of the materials here — particularly the scribe notes and 2013 lectures — do not necessarily reflect exactly what has or will happen in this year’s class. Be sure to check this year’s course calendar for the most up-to-date syllabus.
Unit | Topic | Notes | Scribe | 2013 | 2020 | 2021 |
---|---|---|---|---|---|---|
Introduction | 1 | 1 | ||||
Data Structures | Fibonacci Heaps | 1 | 1 | 1, 2 | ||
Persistent | 1 | 1 | 1, 2 | |||
Splay Trees | 1 | 1 | 1, 2 | 1, 2, 3 | ||
Buckets | 1 | 1, 2 | 1, 2 | 1 | ||
↳VeB Queues | ^ | 1 | 1 | 1 | ||
Hashing | 1 | 1 | 1, 2 | 1, 2 | ||
↳Perfect | ^ | ^ | 1 | 1 | 1 | |
Flow | Maximum Flow | 1 | 1 | 1 | 1, 2 | 1, 2 |
↳Algorithms | 1 | ^ | 1 | 1, 2 | 1 | |
↳Strongly Poly | 1 | 1 | 1 | 1, 2 | ||
↳Blocking | 1 | 1 | 1, 2 | 1 | 1 | |
Min Cost Flow | 1 | 1 | 1 | 1 | ||
↳Algorithms | ^ | ^ | 1, 2 | 1, 2 | 1 | |
Linear Programming | Introduction | 1 | 1 | 1, 2 | 1, 2 | |
Geometry & Optima | ^ | 1 | 1 | 1, 2 | 1 | |
Duality | 1 | 1 | 1 | 1, 2 | 1,2,3 | |
↳Practice | ^ | 1 | 1 | 1, 2 | 1, 2 | |
Algorithms | 1 | 1 | 1, 2 | 1, 2 | 1,2,3 | |
Approximation | Greedy | 1 | 1 | 1 | 1, 2 | 1, 2 |
Schemes | ^ | ^ | 1, 2 | 1, 2 | 1, 2 | |
Relaxations | ^ | 1, 2 | 1, 2 | 1 | ||
↳LP | ^ | 1 | 1, 2 | 1,2,3 | ||
Fixed Parameter Tractability | Introduction | 1 | 1 | 1 | 1 | |
Treewidth | ^ | ^ | 1 | 1, 2 | ||
Comp. Geometry | Range Search | 1 | 1 | 1 | ||
Sweep | ^ | 1 | 1 | 1 | ||
Voronoi | ^ | 1 | 1 | 1, 2 | ||
Online | Introduction | 1 | 1 | 1 | 1, 2 | |
Paging | ^ | 1 | 1 | 1, 2 | 1 | |
↳Randomized | ^ | ^ | 1 | 1, 2 | 1, 2 | |
↳K-Server | ^ | ^ | 1, 2 | 1, 2 | ||
External Memory | 1 | 1 | 1, 2 | 1, 2 | ||
Parallel | 1 | 1, 2 |