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 | |
Aleksander Mądry | madry@mit.edu | Office hours: Arrange by email. In Building 32, Room G666 | ||
TAs: | Cenk Baykal | baykal@mit.edu | ||
Josh Brunner | brunnerj@mit.edu | |||
Sam Park | sp765@mit.edu | |||
Office hours: | Monday and Friday 4-5pm in 36-156 (Mon) and 36-112 (Fri) | |||
Course assistant: | Rebecca Yadegar | ryadegar at 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 | |
---|---|---|---|---|---|
1. | Wed, Sep. 4: | Course introduction. Fibonacci heaps. MST. | nb | nb | |
2. | Fri, Sep. 6: | Persistent Data Structures. | nb | nb | |
3. | Mon, Sep. 9: | Splay trees. | nb | nb | |
4. | Wed, Sep. 11: | More Splay trees. | nb | nb | |
5. | Fri, Sep. 13: | Hashing. Universal Hashing. Perfect Hashing | nb | nb | |
6. | Mon, Sep. 16: | Network Flows: Characterization. Decomposition. Augmenting Paths. | nb | nb | |
7. | Wed, Sep. 18: | Network Flows: Maximum augmenting path. Capacity Scaling. | nb | nb | |
Network Flows: Strongly polynomial algorithms. | nb | ||||
Fri, Sep. 20: | (No class, student holiday) | ||||
8. | Mon, Sep. 23: | Min-Cost Flows: Feasible prices. | nb | nb | |
9. | Wed, Sep. 25: | Finish Min-Cost Flows. | nb | ||
10. | Fri, Sep. 27: | Introduction to Linear Programming. | nb | nb | |
11. | Mon, Sep. 30: | Linear Programming: Structure of Optima. Strong Duality. | nb | nb | |
12. | Wed, Oct. 2: | Linear Programming: Duality Applications. | nb | nb | |
13. | Fri, Oct. 4: | Linear Programming: Simplex Method. | nb | ||
14. | Mon, Oct. 7: | Linear Programming: Ellipsoid Method. Intro to Gradient Descent Method. | nb | ||
15. | Wed, Oct. 9: | Gradient Descent Method: Convexity, smoothness, strong convexity, convergence. | nb | ||
16. | Fri, Oct. 11: | Newton's Method. Generalized Gradient Descent. Linear System Solving. | nb | ||
Mon, Oct. 14: | (No class, student holiday) | ||||
17. | Wed, Oct. 16: | Interior Point Method. | nb | ||
18. | Fri, Oct. 18: | Max flow via Gradient Descent. | nb | ||
19. | Mon, Oct. 21: | Max flow via GD (continued). Electrical flows. Linear system solving. | |||
20. | Wed, Oct. 23: | ||||
21. | Fri, Oct. 25: | Introduction to Approximation Algorithms. | nb | nb | |
22. | Mon, Oct. 28: | Approximation Algorithms: Greedy approaches. Enumeration and FPRAS (scheduling) | nb | ||
23. | Wed, Oct. 30: | Approximation Algorithms: Rounding LP solutions (Vertex Cover, Facility Location). | |||
24. | Fri, Nov. 1: | Approximation Algorithms: MAX-SAT, parameterized complexity | nb | ||
24. | Mon, Nov. 4: | Computational Geometry I. | nb | nb | |
25. | Wed, Nov. 6: | Computational Geometry II. | nb | ||
26. | Fri, Nov. 8: | Online Algorithms: Ski Rental, Paging. | nb | nb | |
Below is last year's schedule: | |||||
24. | Wed, Nov. 14: | Online Algorithms: Ski Rental, Paging. | nb | nb | |
25. | Fri, Nov. 16: | Online Algorithms: Adversaries, Randomization, k-server. | |||
26. | Mon, Nov. 19: | Computational Geometry I. | nb | nb | |
Wed, Nov. 21: | (No class) | ||||
Fri, Nov. 23: | (No class) | ||||
27. | Mon, Nov. 26: | Computational Geometry II. | nb |