Lecture: | Monday, Wednesday, and Friday 2:30-4 in 32-144. | |||
Units: | 5-0-7 Graduate H-level | |||
Professor: | David Karger | karger at mit edu | Office hours: By appt. in Building 32, Room G592 | |
TA: | Punyashloka Biswal | punya at mit edu | Office hours: Mondays, 6pm onwards in lounge next to "Theory Lab" (32G-575) | |
Course assistant: | Be Blackburn | be at theory csail mit edu | Office: Building 32, Room G692 | |
The prerequisites for this class are undergraduate courses in algorithms (e.g., 6.046) and discrete mathematics and probability (e.g., 6.042), in addition to mathematical maturity.
The coursework will involve problem sets and a final project that is research-oriented. For more details, see the handout on course information.
Here is some information about the final project.
Problem Set 1 | Due Wed, Sep. 13 | Solutions |
Problem Set 2 | Due Wed, Sep. 20 | Solutions |
Problem Set 3 | Due Wed, Sep. 27 | Solutions |
Problem Set 4 | Due Wed, Oct. 4 | Solutions |
Problem Set 5 | Due Fri, Oct. 13 (note unusual day) | Solutions |
Problem Set 6 | Due Wed, Oct. 18 | Solutions |
Problem Set 7 | Due Wed, Oct. 25 | Solutions |
Problem Set 8 | Due Wed, Nov. 1 | Solutions |
Problem Set 9 | Due Wed, Nov. 8 | Solutions |
Problem Set 10 | Due Wed, Nov. 15 | |
Problem Set 11 | Due Wed, Nov. 22 |
The dates are fixed! Props to David Glasser for helping me find the correct dates for various things. —TA
1. | Wed, Sep. 6: | Course introduction. Fibonacci heaps (scribe notes, latex source) (raw notes on intro, Fibonacci heaps). | |
2. | Fri, Sep. 8: | MST. Persistent data structures (notes, sources) (raw notes on persistent data structures). | |
3. | Mon, Sep. 11: | Splay trees (old scribe notes, old latex sources, raw notes ). | |
4. | Wed, Sep. 13: | Splay trees. Suffix trees (old scribe notes, old latex sources, raw notes). Tries. | |
5. | Fri, Sep. 15: | Suffix trees. Tries. Dial's Algorithm. | |
6. | Mon, Sep. 18: | Dijkstra's Algorithm. Van Emde Boas Queues
(old scribe
notes, old latex
sources) (raw notes on multi-level buckets, and vEB queues). |
|
7. | Wed, Sep. 20: | Van Emde Boas Queues (cont.). Hashing (old scribe notes, old latex sources) (raw notes on hashing). | |
8. | Fri, Sep. 22: | 2-Level Hashing. Network Flows (scribe notes, latex sources, raw notes on flow). | |
9. | Wed, Sep. 27: | Network Flows: Augmenting Paths, Maximum Augmenting Paths, Scaling. (see notes from previous lecture) | |
10. | Fri, Sep. 29: | Reductions between Flow Problems.
Bipartite Matching.
Shortest Augmenting Path.
Blocking Flows (scribe notes, latex sources). |
|
11. | Wed, Oct. 4: | Blocking Flows (scribe notes, latex sources). | |
12. | Fri, Oct. 6: | Min-Cost Flows: feasible prices. (scribe notes, sources, raw notes on min-cost flow). | |
13. | Wed, Oct. 11: | Min-Cost Flows: complementary slackness, pseudopolynomial
solution. (scribe notes, sources). |
|
14. | Fri, Oct. 13: | Linear-programming: definitions: canonical and standard forms, feasibility and optimization. (scribe notes, sources, raw notes on linear programming). | |
15. | Mon, Oct. 16 | Linear-Programming: structure of Optima. (scribe notes, sources) | |
16. | Wed, Oct. 18 | Linear-Programming: weak duality. | |
17. | Fri, Oct. 20: | Linear-Programming. Strong Duality. (scribe notes, sources). | |
18. | Mon, Oct. 23: | Linear-Programming. Complementary Slackness. Algorithms: Simplex, Ellipsoid. (old scribe notes with sources). | |
19. | Wed, Oct. 25 | Linear-Programming. Algorithms: Interior Point. NP-hard problems. (scribe notes, latex sources). | |
20. | Fri, Oct. 27: | Approximation Algorithms. (scribe notes, latex sources). | |
21. | Mon, Oct. 30: | 4/3-approximation for TSP. Scheduling. (notes, sources) | |
22. | Wed, Nov. 1: | Scheduling. ILP relaxations. (scribe notes, sources) | |
Fri, Nov. 3: | [Optional] Euclidean TSP. | ||
23. | Mon, Nov. 6 | Fixed-parameter tractability. (scribe notes, sources) | |
24. | Wed, Nov. 8 | More Fixed-parameter tractability. Treewidth. (notes, sources) | |
25. | Mon, Nov. 13 | Online algorithms: ski rental, load balancing. (notes, sources) | |
26. | Wed, Nov. 15 | Online algorithms: paging. Randomized online algorithms, adversaries. (notes, sources) | |
27. | Fri, Nov. 17 | Online algorithms: k-server. Yao's minimax principle. (notes, sources) | |
28. | Mon, Nov. 20 | Computational geometry: orthogonal range search, sweep algorithms (segment intersections) (notes, sources) | |
29. | Wed, Nov. 22 | Computational geometry: convex hull (notes, sources) | |
30. | Mon, Nov. 27 | [Optional] Computational geometry: Voronoi diagrams (notes, sources) | |
31. | Wed, Nov. 29 | [Optional] Finish computational geometry. External memory algorithms. (raw notes) | |
32. | Wed, Dec. 6 | [Optional] External memory continued. | |
33. | Mon, Dec. 11 | [Optional] External memory: cache-oblivious algorithms. Parallel algorithms: circuits and PRAMs. (raw notes on parallel algorithms) |
Lecture 1. | Wed, Sep. 7: | Course introduction. Fibonacci heaps (scribe notes, latex source) (raw notes on intro, Fibonacci heaps). |
Lecture 2. | Fri, Sep. 9: | MST. Persistent data structures (scribe notes, latex sources) (raw notes on persistent data structures). |
Lecture 3. | Mon, Sep. 12: | Splay trees (scribe notes, latex sources). |
Lecture 4. | Wed, Sep. 14: | Splay trees. Suffix trees (scribe notes, latex sources). Tries. |
Lecture 5. | Fri, Sep. 16: | Suffix trees. Tries. Dial's Algorithm. |
Lecture 6. | Wed, Sep. 21: |
Dijkstra's Algorithm. Van Emde Boas Queues (scribe notes, latex sources) (raw notes on multi-level buckets, and vEB queues). |
Lecture 7. | Fri, Sep. 23: | Van Emde Boas Queues (cont.). Hashing (scribe notes, latex sources) (raw notes on hashing). |
Lecture 8. | Mon, Sep. 26: | 2-Level Hashing. Network Flows (scribe notes, latex sources). |
Lecture 9. | Wed, Sep. 28: | Network Flows: Augmenting Paths, Maximum Augmenting Paths, Scaling. |
Lecture 10. | Fri, Sep. 30: | Reductions between Flow Problems. Bipartite Matching. Shortest Augmenting Path. Blocking Flows (scribe notes, latex sources). |
Lecture 11. | Mon, Oct. 3: | Blocking Flows (scribe notes, latex sources). |
Recitation 1. | Wed, Oct. 5: | Dynamic Trees. Push-Relabel Max-Flow Algorithm. |
Lecture 12. | Fri, Oct. 7: | Min-Cost Flows (scribe notes, latex sources). |
Lecture 13. | Wed, Oct. 12: | Min-Cost Flows. Linear Programming. (scribe notes, latex sources). |
Lecture 14. | Fri, Oct. 14: | Linear-Programming. Structure of Optima. Weak Duality. (latex sources). |
Lecture 15. | Mon, Oct. 17: | Linear-Programming. Strong Duality. (latex sources). |
Recitation 2. | Wed, Oct. 19: | Simplex |
Lecture 16. | Fri, Oct. 21: | Linear-Programming. Complementary Slackness. Algorithms: Simplex, Ellipsoid. (latex sources). |
Lecture 17. | Mon, Oct. 24: | Linear-Programming. Algorithms: Interior Point. NP-hard problems. (latex sources). |
Lecture 18. | Fri, Oct. 28: | Approximation Algorithms. (latex sources). |
Lecture 19. | Mon, Oct. 31: | 4/3-approximation for TSP. (latex sources). |
Lecture 20. | Wed, Nov. 2: | Relaxations. Directed TSP. (latex sources). |
Lecture 21. | Fri, Nov. 4: | Randomized rounding, Chernoff Bound, Fixed parameter tractability, Kernelization (latex sources). |
Lecture 22. | Wed Nov. 09: | Online algorithms (ski rental, load balancing, paging) (latex sources). |
Lecture 23. | Mon Nov. 14: | Randomized online algorithms (adversaries, Fiat's marking algorithm, potential functions, Yao's minimax principle) (latex sources). |
Lecture 24. | Wed Nov. 16: | k-server problem, double-coverage algorithm, Computational geometry intro (orthogonal range search) (latex sources). |
Lecture 25. | Fri Nov. 18: | Sweep algorithms (convex hull, segment intersection, Voronoi diagrams) (latex sources). |
Lecture 26. | Mon Nov. 21: |
Sweep algorithms (Voronoi diagrams). Randomized Incremental Constructions. Backwards Analysis. Linear Programming in Fixed Dimension. |
Lecture 27. | Mon Nov. 28: |
(Optional material)
External memory algorithms. |
Lecture 28. | Wed Nov. 30: |
(Optional material)
Cache oblivious algorithms: matrix multiplication, linked lists, median. |
Lecture 29. | Fri Dec. 2: |
(Optional material)
Cache oblivious algorithms: Search. Streaming Model. |
Scribing: Here is the LaTeX style file for scribing, and an example use of it.