Lecture: | Monday, Wednesday, and Friday 2:30-4 in 2-190. | |||
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: | Kyriakos Axiotis | kaxiotis@mit.edu | ||
Brynmor Chapman | brynmor@mit.edu | |||
Aleksandar Makelov | amakelov@mit.edu | |||
Sandeep Silwal | silwal@mit.edu | |||
Office hours: | Monday and Friday 4-5pm in 2-135 | |||
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.
Problem Set | Due Date | Solutions | Grading Supervisor | Graders | (Mandatory) Time Report | (Optional) Difficulty/Usefulness Survey |
---|---|---|---|---|---|---|
PS 1 | Wed, Sep. 12 | Sol. 1 | Sandeep |
P2 tslilyai, xygong P3 gilkur, rkavya P4 chenxing, jisoomin P5 mihirs, yyao1 |
Link | Link |
PS 2 | Wed, Sep. 19 | Sol. 2 | Brynmor |
P1a kliment
P2a luciali P2b cgrunau P2c nreddy P3a rogerjin P3b ineq P3c aliu99 P3d yiqiuw P4 mateus P5 varkey |
Link | Link |
PS 3 | Wed, Sep. 26 | Sol. 3 | Kyriakos |
P1 jeshi, zyteka P2 anshula, danifili P3 hflatval, vrichmon P4 wellman, yunyizhu |
Link | Link |
PS 4 | Wed, Oct. 3 | Sol. 4 | Aleksandar |
P1 hansonyu, zixuanxu
P2 maxfish P3 qqi P4 ignapb, bdiehs P5 mcnallyc, alokhina P6 svelusamy@g.harvard.edu, junyaop |
Link | Link |
PS 5 | Wed, Oct. 10 | Sol. 5 | Sandeep |
P1 yizhai, jstrang P2 jasonlu, zeyuans P3 bchen21, ch3nj P4 moberst, rbuhai P5 lillianz, shreyasb |
Link | Link |
PS 6 | Wed, Oct. 17 | Sol. 6 | Brynmor |
P1 darry140 P2 vibhaa P3 rahuly P4 zhulin P5 ericaw |
Link | Link |
PS 7 | Wed, Oct. 24 | Sol. 7 | Kyriakos |
P1 ecai P2 davidja P3 ldec P4 dobsonm P5 tfh |
Link | Link |
PS 8 | Wed, Oct. 31 | Sol. 8 | Aleksandar |
P1 nwu P2 turneram P3 nwu P4 swooders P5 stevliu |
Link | Link |
PS 9 | Wed, Nov. 7 | Sol. 9 | Sandeep |
P1 calvinyw P2 quach P3 jisoomin P4 tkleplae P5 tianyiz |
Link | Link |
PS 10 | Wed, Nov. 14 | Sol. 10 | Brynmor |
allenmi aronto beanash dwq kimvc sfraser whu2704 zfarr |
Link | Link |
PS 11 | Wed, Nov. 21 | Sol. 11 | Kyriakos |
P1 gua P2 brunnerj, hriveron P3 ailyas, engstrom P4 leclerc P5 adelay, scompton |
Link | Link |
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. 5: | Course introduction. Fibonacci heaps. MST. | nb | nb | |
2. | Fri, Sep. 7: | Persistent Data Structures. | nb | nb | |
Mon, Sep. 10: | (Optional lecture) Spectral Graph Theory I: Random Walks and the Laplacian Matrix | nb | |||
3. | Wed, Sep. 12: | Splay trees. | nb | nb | |
4. | Fri, Sep. 14: | Dial's Algorithm. Tries. Multi-level buckets. Van Emde Boas queues | nb | nb | |
5. | Mon, Sep. 17: | Hashing. Universal Hashing. Perfect Hashing | nb | nb | |
Wed, Sep. 19: | (Optional lecture) Spectral Graph Theory II: Graphs and Laplacian Eigenvalues | ||||
Fri, Sep. 21: | (No class) | ||||
6. | Mon, Sep. 24: | (Video lecture) Network Flows. Characterization. Decomposition. Augmenting Paths. | nb | nb | |
7. | Wed, Sep. 26: | Network Flows: Maximum augmenting path. Capacity Scaling. | nb | nb | |
8. | Fri, Sep. 28: | Network Flows: Strongly polynomial algorithms. Shortest augmenting path. | nb | ||
9. | Mon, Oct. 1: | Min-Cost Flows: Feasible prices. Polynomial algorithms: shortest augmenting path; scaling. | nb | nb | |
10. | Wed, Oct. 3: | Finish Min-Cost Flows. | nb | ||
11. | Fri, Oct. 5: | Introduction to Linear Programming. | nb | nb | |
Mon, Oct. 8: | (No class) | ||||
Wed, Oct. 10: | (No class) | ||||
12. | Fri, Oct. 12: | Linear Programming: Structure of Optima. Strong Duality. | nb | nb | |
13. | Mon, Oct. 15: | Linear Programming: Duality Applications. | |||
14. | Wed, Oct. 17: | (Video lecture) Linear Programming: Simplex and Ellipsoid Method. | nb | nb | |
15. | Fri, Oct. 19: | Linear Programming: Duality Applications (continued). | nb | nb | |
16. | Mon, Oct. 22: | Gradient Descent Method: Convexity, smoothness, strong convexity. | nb | ||
17. | Wed, Oct. 24: | Analysis of Gradient Descent for smooth and strongly convex functions. Regularization. Max flow. | nb | ||
18. | Fri, Oct. 26: | Max flow (continued). Electrical flows. Linear system solving. | |||
19. | Mon, Oct. 29: | Preconditioning and Laplacian systems. Gradient Descent for general norms. Max flow (continued). Newton's method. | nb | ||
20. | Wed, Oct. 31: | Interior Point Methods. Introduction to Approximation Algorithms. | nb | nb | |
21. | Fri, Nov. 2: | Approximation Algorithms: Greedy approaches. | nb | ||
22. | Mon, Nov. 5: | Approximation Algorithms: Enumeration and FPRAS (scheduling). | |||
23. | Wed, Nov. 7: | Approximation Algorithms: Combinatorial Approaches (TSP). | |||
24. | Fri, Nov. 9: | Approximation Algorithms: Rounding LP solutions (Vertex Cover, Facility Location). | nb | ||
Mon, Nov. 12: | (No class) | ||||
25. | Wed, Nov. 14: | Online Algorithms: Ski Rental, Paging. | nb | nb | |
26. | Fri, Nov. 16: | Online Algorithms: Adversaries, Randomization, k-server. | |||
27. | Mon, Nov. 19: | Computational Geometry I. | nb | nb | |
Wed, Nov. 21: | (No class) | ||||
Fri, Nov. 23: | (No class) | ||||
28. | Mon, Nov. 26: | Computational Geometry II. | nb |