Lecture: | Monday, Wednesday, and Friday 2:30-4 in 32-123. | ||
Units: | 5-0-7 Graduate H-level | ||
Instructors: | David Karger | karger@mit.edu | Office hours: Arrange by email. In Building 32, Room G592 |
TAs: | Angelos Pelecanos | apelecan@mit.edu | Office hours: Monday and Friday 4-6 in Building 36, Room 36-153 and virtually. |
Theia Henderson | theia@mit.edu | ||
William Kuszmaul | kuszmaul@mit.edu | ||
Course assistant: | Rebecca Yadegar | ryadegar@csail.mit.edu |
The prerequisites for this class are strong performance in undergraduate courses in algorithms (e.g., 6.046/18.410) and discrete mathematics and probability (6.042 is more than sufficient), in addition to substantial 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.
Problem Set | Due Date | Solutions | Grading Supervisor | Gradescope | (Mandatory) Time Report | Peer Grading Sign-up | Late Submission |
---|---|---|---|---|---|---|---|
PS1 | Wed, Sep. 15 | V8X428 | PS1 Survey | PS1 Grading | PS1 Late | ||
PS2 | Wed, Sep. 22 | N8N6DB | PS2 Survey | PS2 Grading | PS2 Late |
For notes and videos related to each topic, see the course materials.
# | Date | Topic |
---|---|---|
1. | Wed, Sep. 8: | Course introduction. Fibonacci heaps. MST. |
2. | Fri, Sep. 10: | Fibonacci heaps. |
3. | Mon, Sep. 13: | Fibonacci heaps. MST. Persistent Data Structures. |
4. | Wed, Sep. 15: | Splay Trees. |
5. | Fri, Sep. 17: | Splay Trees. Buckets. |
Below this point is last year's schedule and subject to change. | ||
All lectures will be done before Thanksgiving | ||
6. | Mon, Sep. 20: | van Emde Boas Queues and Hashing |
7. | Wed, Sep. 22: | Universal Hashing. Perfect Hashing. Begin Network Flows. |
8. | Fri, Sep. 24: | Network Flows: Charaterization. Augmenting Paths. Max Flow Min Cut Theorem. |
9. | Mon, Sep. 27: | Network Flows: Maximum augmenting path. Capacity Scaling. |
10. | Wed, Sep. 29: | Network Flows: Strongly polynomial algorithms. Blocking Flows. |
11. | Fri, Oct. 1: | Min-Cost Flows: Feasible prices. |
12. | Mon, Oct. 4: | Min-Cost Flows |
13. | Wed, Oct. 6: | Finish Min-Cost Flows and Introduction to Linear Programming. |
14. | Fri, Oct. 8: | Linear Programming: Structure of Optima. |
Mon, Oct. 11: | Indigenous Peoples Day - No class | |
15. | Wed, Oct. 13: | Linear Programming: Strong Duality. |
16. | Fri, Oct. 15: | Linear Programming: Strong Duality and Duality Applications. |
17. | Mon, Oct. 18: | Linear Programming: Duality Applications. |
18. | Wed, Oct. 20: | Linear Programming: Simplex Method. |
19. | Fri, Oct. 22: | Linear Programming: Ellipsoid Method. |
20. | Mon, Oct. 25: | Introduction to Approximation Algorithms. |
21. | Wed, Oct. 27: | Approximation Algorithms: Greedy approaches. Enumeration and FPAS (scheduling) |
22. | Fri, Oct. 29: | Approximation Algorithms: Enumeration, Rounding, Metric TSP. |
23. | Mon, Nov. 1: | Approximation Algorithms: Relaxations |
24. | Wed, Nov. 3: | Approximation Algorithms: Randomized Rounding |
25. | Fri, Nov. 5: | Computational Geometry I. |
26. | Mon, Nov. 8: | Computational Geometry II: Voronoi Diagrams |
27. | Wed, Nov. 10: | Online Algorithms: Ski Rental, Paging. |
28. | Fri, Nov. 12: | Online Algorithms: Paging, Adversaries, Randomization |
29. | Mon, Nov. 15: | Online Algorithms: Adversaries, Randomization, k-server. |
30. | Wed, Nov. 17: | The k-server problem and External Memory Algorithms. |
31. | Fri, Nov. 19: | External Memory Algorithms. |
32. | Mon, Nov. 22: | Parallel Algorithms. |
33. | Wed, Nov. 24: | Parallel Algorithms. |
Fri, Nov. 26 | Thanksgiving holiday - No class |