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 | P1 tclin@mit.edu; P2 calvin3@mit.edu ; P3 karren@mit.edu ; P4 yangk@mit.edu ; P5 aradhana@mit.edu |
Link | Link |
PS 8 | Wed, Nov. 2 | John | P1 davidbau@mit.edu; P2 amakelov@mit.edu; P3 jeetmo@mit.edu; P4 trattner@mit.edu |
Link | Link |
PS 9 | Wed, Nov. 11 | Tal | P1 kelswong@mit.edu ; P2 trattner@mit.edu ; P3 bando@mit.edu ; P4 badea@mit.edu ; P5 schiefer@mit.edu |
Link | Link |
PS 10 | Wed, Nov. 11 | Tal | P1 bmhuang@mit.edu ; P2 ashwath@mit.edu ; P3 jayzee@mit.edu ; P4 alexjl@mit.edu ; P5 shahp@mit.edu |
Link | Link |
PS 11 | Wed, Nov. 23 | John | Answer the survey sent via email if you haven't graded | 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 | Survey | ||
---|---|---|---|---|---|---|
1. | Wed, Sep. 7: | Course introduction. Persistent data structures. | nb | Survey | ||
2. | Fri, Sep. 9: | Splay trees. | nb | Survey | ||
3. | Mon, Sep. 12: | Integer Queues: Dial's Algorithm. Tries. | nb | Survey | ||
4. | Wed, Sep. 14: | Integer Queues: Denardo and Fox, Van Emde Boas | nb | Survey | ||
5. | Fri, Sep. 16: | Universal Hashing. Perfect Hashing.
Streaming Model I: Distinct Elements Problem. |
Survey1 Survey2 | |||
6. | Mon, Sep. 19: | Streaming Model II: Heavy Hitters Problem
Dimensionality Reduction: Johnson-Lindenstrauss Lemma. |
Survey1 Survey2 | |||
7. | Wed, Sep. 21: | Network Flows I: Flow Decomposition and Augmenting Paths. | nb | Survey | ||
Fri, Sep. 23: | NO CLASS (Student Holiday). | |||||
8. | Mon, Sep. 26: | Network Flows II: Basic Flow Algorithms and Capacity Scaling. | nb | Survey | ||
9. | Wed, Sep. 28: | Network Flows III: Strongly Polynomial Time Max Flow Algorithms. | nb | Survey | ||
10. | Fri, Sep. 30: | Network Flows IV: Blocking Flows. | Survey | |||
(o1) | Mon, Oct 3: | (OPTIONAL LECTURE) Spectral Graph Theory I: The Graph Laplacian and its Eigenvalues. | nb | Survey | ||
11. | Wed, Oct 5: | Network Flows V: Min-Cost Flow and Cycle Cancelling Algorithm. | Survey | |||
12. | Fri, Oct 7: | Network Flows VI: Min-Cost Flow and Feasible Prices. | Survey | |||
Mon, Oct 10: | NO CLASS (Columbus Day). | |||||
(o2) | Wed, Oct 12: | (OPTIONAL LECTURE) Spectral Graph Theory II: Random Walks and Laplacian Spectrum. | nb | Survey | ||
13. | Fri, Oct 14: | Introduction to Linear Programming, Structure of Optima. | nb | Survey | ||
14. | Mon, Oct 17: | Strong Duality, and Complementary Slackness. | nb | Survey | ||
15. | Wed, Oct 19: | Simplex and Ellipsoid Method. | Survey | |||
16. | Fri, Oct 21: | Gradient Descent Method and its Applications. | nb | Survey | ||
17. | Mon, Oct 24: | Interior-Point Methods. | Survey | |||
18. | Wed, Oct 26: | Introduction to Approximation Algorithms. | Survey | |||
19. | Fri, Oct 28: | Approximation Algorithms II: Approximation Schemes by Rounding and Enumeration | nb | Survey | ||
20. | Mon, Oct 31: | Approximation Algorithms III: Relaxations. TSP, Scheduling, LP Relaxations | Survey | |||
21. | Wed, Nov 2: | Approximation Algorithms IV: Facility Location. Introduction to Online Algorithms (online lecture experiment). | nb | Survey1 Survey2 | ||
22. | Fri, Nov 4: | Online Algorithms II: Paging, Deterministic and Randomized | Survey | |||
23. | Mon, Nov 7: | Online Algorithms III: k-server. Introduction to External Memory Algorithms | nb | Survey | ||
24. | Wed, Nov 9: | External Memory Algorithms | Survey | |||
Fri, Nov 11: | NO CLASS (Veterans Day). | |||||
25. | Mon, Nov 14: | Computational Geometry I | nb | Survey | ||
26. | Wed, Nov 16: | Computational Geometry II. | Survey | |||
27. | Fri, Nov 18: | Parallel Computations I. | nb | Survey | ||
28. | Mon, Nov 21: | Parallel Computations II. | Survey | |||
(o3) | Wed, Nov 23: | (OPTIONAL LECTURE) Multiplicative Weight-Update Method, Zero-sum Games, LP Duality | Survey | |||
(o4) | Mon, Nov 28: | (OPTIONAL LECTURE) Fast (Laplacian) Linear System Solving | nb | Survey | ||
(o5) | Wed, Nov 30: | (OPTIONAL LECTURE) Spectral graph theory III: Random Walks, Cuts, and Electrical Flows | Survey | |||
(o6) | Fri, Dec 2: | (OPTIONAL LECTURE) Word-level Parallelism: Sorting Integers in Linear Time | Survey | |||
(o7) | Mon, Dec 5: | (OPTIONAL LECTURE) Computing Maximum Flows with Electrical Flows | nb nb nb | Survey |