Lecture: | Monday, Wednesday, and Friday 2:30-4 (Online lectures) | |||
Units: | 5-0-7 Graduate H-level | |||
Instructors: | David Karger | karger@mit.edu | Office hours: Arrange by email. In Building 32, Room G592 | |
TAs: | Josh Brunner | brunnerj@mit.edu | ||
Christian Altamirano | bdiehs@mit.edu | |||
Thiago Bergamaschi | thiagob@mit.edu | |||
Office hours: | Monday 5:30-6:30pm and Friday 4-5pm online | |||
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.
Be aware that some of the scribe notes might be very old, and do not necessarily reflect exactly what happened in this year's class.
# | Date | Topic | Raw Notes | Scribe | Video | |
---|---|---|---|---|---|---|
1. | Wed, Sep. 2: | Course introduction. Fibonacci heaps. MST. | nb and nb | nb | video | |
2. | Fri, Sep. 4: | Fibonacci heaps. MST. Persistent Data Structures Intro. | nb | nb | video | |
3. | Wed, Sep. 9: | Persistent Data Structures. Splay trees intro. | nb | nb | video | |
4. | Fri, Sep. 11: | Splay trees. | nb | nb | video | |
5. | Mon, Sep. 14: | Dial's Algorithm. Tries. Multi-level buckets. | nb | nb | video | |
6. | Wed, Sep. 16: | van Emde Boas Queues and Hashing | nb | nb | video | |
7. | Fri, Sep. 18: | Universal Hashing. Perfect Hashing. Begin Network Flows. | video | |||
8. | Mon, Sep. 21: | Network Flows: Charaterization. Augmenting Paths. Max Flow Min Cut Theorem. | nb | nb | video | |
9. | Wed, Sep. 23: | Network Flows: Maximum augmenting path. Capacity Scaling. | nb | nb | video | |
10. | Fri, Sep. 25: | Network Flows: Strongly polynomial algorithms. Blocking Flows. | nb nb | video | ||
11. | Mon, Sep. 28: | Min-Cost Flows: Feasible prices. | nb | nb | video | |
12. | Wed, Sep. 30: | Min-Cost Flows | nb | video | ||
13. | Fri, Oct. 2: | Finish Min-Cost Flows and Introduction to Linear Programming. | video | |||
14. | Mon, Oct. 5: | Linear Programming: Structure of Optima. | nb | nb | video | |
15. | Wed, Oct. 7: | Linear Programming: Strong Duality. | nb | nb | video | |
16. | Fri, Oct. 9: | Linear Programming: Strong Duality and Duality Applications. | nb | nb | video | |
17. | Tue, Oct. 13: | Linear Programming: Duality Applications. | nb | nb | video | |
18. | Wed, Oct. 14: | Linear Programming: Simplex Method. | nb | video | ||
19. | Fri, Oct. 16: | Linear Programming: Ellipsoid Method. | nb | video | ||
20. | Mon, Oct. 19: | Introduction to Approximation Algorithms. | nb | nb | video | |
21. | Wed, Oct. 21: | Approximation Algorithms: Greedy approaches. Enumeration and FPAS (scheduling) | nb | video | ||
22. | Fri, Oct. 23: | Approximation Algorithms: Enumeration, Rounding, Metric TSP. | video | |||
23. | Mon, Oct. 26: | Approximation Algorithms: Relaxations | video | |||
24. | Wed, Oct. 28: | Approximation Algorithms: Randomized Rounding | nb | video | ||
25. | Fri, Oct. 30: | Computational Geometry I. | nb | nb | video | |
26. | Mon, Nov. 2: | Computational Geometry II: Voronoi Diagrams | nb | video | ||
27. | Wed, Nov. 4: | Online Algorithms: Ski Rental, Paging. | nb | nb | video | |
28. | Fri, Nov. 6: | Online Algorithms: Paging, Adversaries, Randomization | nb | nb | video | |
29. | Mon, Nov. 9: | Online Algorithms: Adversaries, Randomization, k-server. | video | |||
30. | Fri, Nov. 13: | The k-server problem and External Memory Algorithms. | video | |||
31. | Mon, Nov. 16: | External Memory Algorithms. | nb | video | ||
32. | Wed, Nov. 18: | Parallel Algorithms. | nb | video | ||
33. | Fri, Nov. 20: | Parallel Algorithms. | nb | video | ||
Below this point is last year's schedule. |