| LEC # | TOPICS | KEY DATES |
|---|---|---|
| 1 | Course Introduction Fibonacci Heaps | |
| 2 | MST Persistent Data Structures | |
| 3 | Splay Trees | |
| 4 | Splay Trees (cont.) Suffix Trees Tries | Problem set 1 due |
| 5 | Suffix Trees (cont.) Tries (cont.) Dial's Algorithm | |
| 6 | Dijkstra's Algorithm Van Emde Boas Queues | Problem set 2 due |
| 7 | Van Emde Boas Queues (cont.) Hashing | |
| 8 | 2-Level Hashing Network Flows | |
| 9 | Network Flows: Augmenting Paths, Maximum Augmenting Paths, Scaling | Problem set 3 due |
| 10 | Reductions between Flow Problems Bipartite Matching Shortest Augmenting Path Blocking Flows | |
| 11 | Blocking Flows (cont.) | |
| Recitation Topics: Dynamic Trees, Push-Relabel Max-Flow Algorithm | ||
| 12 | Min-Cost Flows | Problem set 4 due |
| 13 | Min-Cost Flows (cont.) Linear Programming | Problem set 5 due |
| 14 | Linear Programming (cont.) Structure of Optima Weak Duality | |
| 15 | Linear Programming (cont.) Strong Duality | |
| Recitation Topic: Simplex | Problem set 6 due | |
| 16 | Linear Programming (cont.) Complementary Slackness Algorithms: Simplex, Ellipsoid | |
| 17 | Linear Programming (cont.) Algorithms: Interior Point NP-hard problems | Problem set 7 due two days after Lec #17 |
| 18 | Approximation Algorithms | |
| 19 | 4/3-Approximation for TSP | |
| 20 | Relaxations Directed TSP | Problem set 8 due |
| 21 | Randomized Rounding Chernoff Bound Fixed Parameter Tractability Kernelization | |
| 22 | Online Algorithms (Ski Rental, Load Balancing, Paging) | Problem set 9 due |
| 23 | Randomized Online Algorithms (Adversaries, Fiat's Marking Algorithm, Potential Functions, Yao's Minimax Principle) | |
| 24 | K-Server Problem Double-Coverage Algorithm Computational Geometry Introduction (Orthogonal Range Search) | Problem set 10 due |
| 25 | Sweep Algorithms (Convex Hull, Segment Intersection, Voronoi Diagrams) | |
| 26 | Sweep Algorithms (Voronoi Diagrams) Randomized Incremental Constructions Backwards Analysis Linear Programming in Fixed Dimension | Problem set 11 due two days after Lec #26 |
| 27 | (Optional Material) External Memory Algorithms | Problem set 12, problem 1 due |
| 28 | (Optional Material) Cache Oblivious Algorithms: Matrix Multiplication, Linked Lists, Median | |
| 29 | (Optional Material) Cache Oblivious Algorithms: Search Streaming Model | Rest of problem set 12 due three days after Lec #29 |