Lecture: | Monday, Wednesday, and Friday 2:30-4 in 32-141. | |||
Units: | 5-0-7 Graduate H-level | |||
Instructors: | David Karger | karger at mit edu | Office hours: Arrange by email. In Building 32, Room G592 | |
Aleksander Mądry | madry at mit edu | Office hours: Arrange by email. In Building 32, Room G666 | ||
TAs: | John Peebles | jpeebles at mit.edu | ||
Tal Wagner | talw at mit.edu | |||
Office hours: | Mondays, 4:30pm-5:30pm, Room 36-112 | |||
Fridays, 4:00pm-5:00pm, Room 36-144 | ||||
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 | Grading Supervisor | Graders | (Mandatory) Time Report | (Optional) Difficulty/Usefulness Survey |
---|---|---|---|---|---|
PS 1 | Fri, Sep. 16 | John | sahasag@mit.edu 3(c); bristy@mit.edu 2; baxelrod@mit.edu 1; hongzi@mit.edu 5(c,d); ececca@mit.edu 5(a,b); yilundu@mit.edu 4; epayne@mit.edu 3(a,b) | Link | Link |
PS 2 | Wed, Sep. 21 | Tal | P1 nkb@mit.edu ; P2 zanger@mit.edu ; P3 umaroy@mit.edu ; P4 timngo@mit.edu ; P5 weiqiaoh@mit.edu ; P6 ztzhang@mit.edu |
Link | Link |
PS 3 | Wed, Sep. 28 | John | P1 sshader@mit.edu; P2 ycy@mit.edu; P3 jimmy42@mit.edu; P4 kaxiotis@mit.edu; P5 tianxiao@mit.edu; P6 ctunoku+6854@mit.edu |
Link | Link |
PS 4 | Wed, Oct. 5 | Tal | P1 dzaefn@mit.edu ; P2 keyulu@mit.edu ; P3 pahrens@mit.edu ; P4 luh@mit.edu ; P5 ronuchit@mit.edu |
Link | Link |
PS 5 | Fri, Oct. 14 | John | P1 hayks@mit.edu; P2 arsen@mit.edu; P3 alet+6854@mit.edu; P4 hujh@mit.edu; P5 bpchen@mit.edu |
Link | Link |
PS 6 | Wed, Oct. 19 | Tal | P1 abhijitm@mit.edu ; P2 kocabey@mit.edu ; P3 diomidov@mit.edu ; P4 akkas@mit.edu ; P5 jbpatel@mit.edu |
Link | Link |
PS 7 | Wed, Oct. 26 | John | Sign up here to grade pset7 | 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 | Notes | ||
---|---|---|---|---|---|
1. | Wed, Sep. 7: | Course introduction. Persistent data structures. | nb | ||
2. | Fri, Sep. 9: | Splay trees. | nb | ||
3. | Mon, Sep. 12: | Integer Queues: Dial's Algorithm. Tries. | nb | ||
4. | Wed, Sep. 14: | Integer Queues: Denardo and Fox, Van Emde Boas | nb | ||
5. | Fri, Sep. 16: | Universal Hashing. Perfect Hashing.
Streaming Model I: Distinct Elements Problem. |
|||
6. | Mon, Sep. 19: | Streaming Model II: Heavy Hitters Problem
Dimensionality Reduction: Johnson-Lindenstrauss Lemma. |
|||
7. | Wed, Sep. 21: | Network Flows I: Flow Decomposition and Augmenting Paths. | nb | ||
Fri, Sep. 23: | NO CLASS (Student Holiday). | ||||
8. | Mon, Sep. 26: | Network Flows II: Basic Flow Algorithms and Capacity Scaling. | nb | ||
9. | Wed, Sep. 28: | Network Flows III: Strongly Polynomial Time Max Flow Algorithms. | nb | ||
10. | Fri, Sep. 30: | Network Flows IV: Blocking Flows. | |||
Mon, Oct 3: | (OPTIONAL LECTURE) Spectral Graph Theory I: The Graph Laplacian and its Eigenvalues. | nb | |||
11. | Wed, Oct 5: | Network Flows V: Min-Cost Flow and Cycle Cancelling Algorithm. | |||
12. | Fri, Oct 7: | Network Flows VI: Min-Cost Flow and Feasible Prices. | |||
Mon, Oct 10: | NO CLASS (Columbus Day). | ||||
Wed, Oct 12: | (OPTIONAL LECTURE) Spectral Graph Theory II: Random Walks and Laplacian Spectrum. | nb | |||
13. | Fri, Oct 14: | Introduction to Linear Programming, Structure of Optima. | nb | ||
14. | Mon, Oct 17: | Strong Duality, and Complementary Slackness. | nb | ||
15. | Wed, Oct 19: | Simplex and Ellipsoid Method. | |||
16. | Fri, Oct 21: | Gradient Descent Method and its Applications. | nb | ||
17. | Mon, Oct 24: | Interior-Point Methods. |