Lecture: | Monday, Wednesday, and Friday 2:30-4 in 32-155. | |||
Units: | 5-0-7 Graduate H-level | |||
Professor: | David Karger | karger at mit edu | Office hours: Arrange by email. In Building 32, Room G592 | |
TA: | Ofir Nachum | ofir at mit.edu | Office hours: Mon 4:15PM - 5:45PM and Fri 4:15PM - 5PM, CSAIL 5th floor lounge | |
Jin Hao Wan | jhwan at mit.edu | Office hours: Mon 4:15PM - 5:45PM and Fri 4:15PM - 5PM, CSAIL 5th floor lounge | ||
Please come back frequently to check the office hour updates. | ||||
Course assistant: | Nina Olff | olff@csail.mit.edu | Office: Building 32, Room 32-G764 and 32-G434 |
The prerequisites for this class are undergraduate courses in algorithms (e.g., 6.046) and discrete mathematics and probability (e.g., 6.042), in addition to 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 |
---|---|---|---|---|
PS 1 | Wed, Sep. 18 | SOL 1 | Jin | |
PS 2 | Wed, Sep. 25 | SOL 2 | Ofir | Pritish Kamath pritish@mit.edu + Eugenio Fortanely erf@mit.edu (P1+P3), Chrisantha Perera cperera@mit.edu + Daniel Grier grierd@mit.edu (P2), Matt Jordan jordanm@mit.edu (P4), Eric Mannes mannes@mit.edu (P5) |
PS 3 | Wed, Oct. 2 | SOL 3 | Jin | John Peebles jpeebles@mit.edu + Max Kolysh mkolysh@mit.edu (P1), Caelan Garrett caelan@mit.edu + Chris Graves graves@mit.edu (P2), Prashant Vasudevan prashvas@mit.edu (P3), Ali Vakilian vakilian@mit.edu (P4), Casey O'Brien cmobrien@mit.edu (P5) |
PS 4 | Wed, Oct. 9 | SOL 4 | Ofir | Victor Pontis vpontis@mit.edu (P1), Anvisha Pai anvishap@mit.edu (P2), Varun Ramaswamy vrama@mit.edu + Jan Polášek jpolasek@mit.edu (P3), Dennis Tseng dtseng@mit.edu (P4), Julian Chaidez jchaidez@mit.edu + Maryam Aliakbarpour maryama@mit.edu (P5) |
PS 5 | Wed, Oct. 16 | SOL 5 | Jin | Chrisantha Perera cperera@mit.edu + Hoon Cho hhcho@mit.edu (P1), Bianca Homberg bhomberg@mit.edu (P2), Emily Lindemer lindemer@mit.edu (P3), Ernest Zeidman zeidman@mit.edu (P4 + P6), Laphonchai Jirachup doraepon@mit.edu + Suthee Ruangwises Suthee@mit.edu (P5) |
PS 6 | Wed, Oct. 23 | SOL 6 | Ofir | Ellen Finch finche@mit.edu + Sam Elder same@mit.edu (P1), Miles Lubin mlubin@mit.edu (P2), Alex Wein awein@mit.edu (P3), Jerry Li jerryzli@mit.edu (P4), Amy Ousterhat aousterh@mit.edu (P5) |
PS 7 | Wed, Oct. 30 | SOL 7 | Jin | Erin Davis edavis5@mit.edu (P1), Payut Pantawongdecha payutp@mit.edu (P2), Aloni Cohen aloni@mit.edu (P3), Bryan Collazo bcollazo@mit.edu (P4), Fereshte Khani fereshtekhani@gmail.com (P5) |
PS 8 | Wed, Nov. 6 | SOL 8 | Ofir | Rumen Hristov rhristov@mit.edu (P1), Anderson Wang asw@mit.edu (P2), Leon Lin leonxlin@mit.edu (P3), Min Zhang mzhang94@mit.edu (P4), Michael Xu michaelx@mit.edu + Tommy Zhang trzhang@mit.edu (P5), Robi Bhattacharjee robibhat@mit.edu (P6) |
PS 9 | Wed, Nov. 13 | SOL 9 | Ofir | Patrick Yang pbyang@mit.edu (P1), Phillip Ai pzai@mit.edu (P2), Mohammed Ali Auoad aaouad@mit.edu (P3), Yun William Yu ywy@mit.edu (P4), Joseph DelPreto delpreto@mit.edu (P5) |
PS 10 | Wed, Nov. 20 | SOL 10 | Jin | Yongyi Chen yongyic@mit.edu (P1), Jin Pan jinpan@mit.edu (P2), Neil Gurram ngurram@mit.edu (P3), Lauren Stephens lhs@mit.edu (P4), Adam Eagle areagle@mit.edu (P5) |
PS 11 | Wed, Nov. 27 | SOL 11 | Jin | Ulziibayar Otgonbaatar ulziibay@mit.edu (P1 + P4), Evangelos Taratoris evtara@mit.edu (P2 + P4), Michael DuPlessis mdupless928@gmail.com (P3) |
Be aware that the scribe notes are all very old, and do not necessarily reflect exactly what happened in this year's class. Use the raw notes as the most authentic references.
# | Date | Topic | Raw Notes | Scribe Notes | Lec Videos |
---|---|---|---|---|---|
1. | Wed, Sep. 4: | Course introduction. Fibonacci heaps. MST. | nb | nb | |
Fri, Sep. 6: | No class. | ||||
2. | Mon, Sep. 9: | Fibonacci heaps. MST. | nb | ||
3. | Wed, Sep. 11: | Persistent data structures. | nb | nb | |
4. | Fri, Sep. 13: | Splay trees. | nb | nb | nb |
5. | Mon, Sep. 16: | Dial's Algorithm. Tries. Multi-level buckets. Van Emde Boas queues. | nb | nb | |
6. | Wed, Sep. 18: | Van Emde Boas queues cont. Hashing. | nb | ||
Fri, Sep. 20: | Student holiday, no class | ||||
7. | Mon, Sep. 23: | Universal Hashing. Perfect Hashing. | nb | nb | nb |
8. | Wed, Sep. 25: | Network Flows. Characterization. Decomposition. Augmenting Paths. | nb | ||
Fri, Sep. 27: | Optional lecture: Suffix Trees | nb | |||
9. | Mon, Sep. 30: | Network Flows: Maximum augmenting path. scaling. | nb | nb | nb |
10. | Wed, Oct. 2: | Network Flows: Strongly polynomial algorithms. Shortest augmenting path. Blocking flows. | nb | nb | nb |
Fri, Oct. 4: | Optional Lecture: Push-relabel. | ||||
11. | Mon, Oct. 7: | Network Flows: More blocking flows. Link Cut trees. Min-Cost Flows. Definitions. Chatacterization. Pseudopolynomial algorithm: cycle canceling. | nb | nb | nb |
12. | Wed, Oct. 9: | Min-Cost Flows: Feasible prices. Polynomial algorithms: shortest augmenting path; scaling. | nb | nb | |
13. | Fri, Oct. 11: | Linear-programming: definitions: canonical and standard forms, feasibility and optimization. Structure of Optima. | nb | nb | nb |
Mon, Oct. 14: | Columbus Day, no class. | ||||
14. | Wed, Oct. 16 | Linear-Programming: Duality Theory. | nb | nb | |
15. | Fri, Oct. 18 | Linear-Programing: Duality Applications. | |||
16. | Mon, Oct. 21: | Linear Programming Algorithms: Simplex | nb | ||
17. | Wed, Oct. 23: | Linear-Programming Algorithms: Eillipsoid. | |||
18. | Fri, Oct. 25: | Linear-Programming Algorithms: Interior Point. | |||
19. | Mon, Oct. 28: | NP-hard problems. Approximation Algorithms. Relative Approximations. | nb | nb | |
20. | Wed, Oct. 30: | PAS and FPAS. Scheduling. | nb | ||
21. | Fri, Nov. 1 | Relaxations. 3/2-approximation for TSP. ILP relaxations. | nb | ||
22. | Mon, Nov. 4 | ILP relaxations. Randomized Rounding. | |||
23. | Wed, Nov. 6 | Online Algorithms: ski rental, load balancing | online | nb | |
24. | Fri, Nov. 8 | Online algorithms: linked lists, paging. | Erik's Notes | nb1 nb2 | |
Mon, Nov. 11 | Veteran's Day, no class. | ||||
25. | Wed, Nov. 13 | Randomized online algorithms, adversaries. k-server. | |||
26. | Fri, Nov. 15 | Computational geometry: orthogonal range search, Voronoi diagram. | nb | ||
27. | Mon, Nov. 18 | Computational geometry: convex hull, sweep line, Voronoi diagram (Fortune's algorithm animation) | nb nb | ||
28. | Wed, Nov. 20 | External memory algorithms. | nb | ||
Fri, Nov. 22 | Cache oblivious algorithms. | ||||
Mon, Nov. 25 | Parallel algorithms. | ||||
Wed, Nov. 27 | Fixed-parameter tractability, treewidth. | ||||
Wed, Dec. 11 | Final Project due date. |
Tries. Suffix trees (old scribe notes, old latex sources, raw notes). |