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.
Problem Set | Due Date | Solutions | Grading Supervisor | Gradescope code | (Mandatory) Time Report | Peer Grading Sign-up | Late Submission |
---|---|---|---|---|---|---|---|
PS1 | Wed, Sep. 9 | PS1 Sol | Josh | MY4B55 | PS1 Time Survey | PS1 Peer Grading | PS1 Late Form |
PS2 | Wed, Sep. 16 | PS2 Sol | Thiago | MPV7N7 | PS2 Time Survey | PS2 Peer Grading | PS2 Late Form |
PS3 | Wed, Sep. 23 | PS3 Sol | Christian | 95YNW7 | PS3 Time Survey | PS3 Peer Grading | PS3 Late Form |
PS4 | Wed, Sep. 30 | PS4 Sol | Josh | ME3N7E | PS4 Time Survey | PS4 Peer Grading | PS4 Late Form |
PS5 | Wed, Oct. 7 | PS5 Sol | Christian | KY53DB | PS5 Time Survey | PS5 Peer Grading | PS5 Late Form |
PS6 | Wed, Oct. 14 | PS6 Sol | Josh | KY586R | PS6 Time Survey | PS6 Peer Grading | PS6 Late Form |
PS7 | Wed, Oct. 21 | Christian | X3Y4DX | PS7 Time Survey | PS7 Peer Grading | PS7 Late Form | |
PS8 | Wed, Oct. 28 | Thiago | KY52ZG | PS8 Time Survey | PS8 Peer Grading | PS8 Late Form | |
PS9 | Wed, Nov. 4 | Josh | JBB3V7 | PS8 Time Survey | PS8 Peer Grading | PS8 Late Form |
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 | ||
Below this point is last year's schedule. | ||||||
24. | Mon, Nov. 2: | Computational Geometry I. | nb | nb | ||
25. | Wed, Nov. 4: | Computational Geometry II. | nb | |||
26. | Fri, Nov. 6: | Online Algorithms: Ski Rental, Paging. | nb | nb | ||
24. | Wed, Nov. 9: | Online Algorithms: Ski Rental, Paging. | nb | nb | ||
25. | Fri, Nov. 17: | Online Algorithms: Adversaries, Randomization, k-server. | ||||
26. | Mon, Nov. 20: | Computational Geometry I. | nb | nb | ||
Wed, Nov. 22: | (No class) | |||||
Fri, Nov. 24: | (No class) | |||||
27. | Mon, Nov. 27: | Computational Geometry II. | nb |