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 | Josh | MY4B55 | PS1 Time Survey | PS1 Peer Grading | PS1 Late Form | |
PS2 | Wed, Sep. 16 | Thiago | MPV7N7 | PS2 Time Survey | PS2 Peer Grading | PS2 Late Form | |
PS3 | Wed, Sep. 23 | Christian | 95YNW7 | PS3 Time Survey | PS3 Peer Grading | PS3 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 | |
4. | Mon, Sep. 14: | Dial's Algorithm. Tries. Multi-level buckets. | nb | nb | video | |
5. | Wed, Sep. 16: | Hashing. Universal Hashing. Perfect Hashing | nb | nb | video | |
6. | Mon, Sep. 14: | Network Flows: Characterization. Decomposition. Augmenting Paths. | nb | nb | video | |
7. | Wed, Sep. 16: | Network Flows: Maximum augmenting path. Capacity Scaling. | nb | nb | ||
Network Flows: Strongly polynomial algorithms. | nb | |||||
Fri, Sep. 18: | (No class, student holiday) | |||||
8. | Mon, Sep. 21: | Min-Cost Flows: Feasible prices. | nb | nb | ||
9. | Wed, Sep. 23: | Finish Min-Cost Flows. | nb | |||
10. | Fri, Sep. 25: | Introduction to Linear Programming. | nb | nb | ||
11. | Mon, Sep. 28: | Linear Programming: Structure of Optima. Strong Duality. | nb | nb | ||
12. | Wed, Sep. 30: | Linear Programming: Duality Applications. | nb | nb | ||
13. | Fri, Oct. 2: | Linear Programming: Simplex Method. | nb | |||
14. | Mon, Oct. 5: | Linear Programming: Ellipsoid Method. | nb | |||
20. | Wed, Oct. 21: | |||||
21. | Fri, Oct. 23: | Introduction to Approximation Algorithms. | nb | nb | ||
22. | Mon, Oct. 26: | Approximation Algorithms: Greedy approaches. Enumeration and FPRAS (scheduling) | nb | |||
23. | Wed, Oct. 28: | Approximation Algorithms: Rounding LP solutions (Vertex Cover, Facility Location). | ||||
24. | Fri, Oct. 30: | Approximation Algorithms: MAX-SAT, parameterized complexity | nb | |||
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 |