Lecture: | Monday, Wednesday, and Friday 2:30-4 in 35-225. | |||
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: | Will Hasenplaugh | whasenpl at mit.edu | Office hours: TBA | |
Georgios Vlachos | gvlachos at mit.edu | Office hours: TBA | ||
Please come back frequently to check the office hour updates. | ||||
Course assistant: | Rebecca Yadegar | ryadegar at csail.mit.edu |
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 | Fri, Sep. 12 | SOL 1 | Georgios | (P1) Tal talw at mit.edu (P2) Jon jweed at mit.edu (P3) Vadim vss at mit.edu (P4) Sam sp765 at mit.edu |
PS 2 | Wed, Sep. 17 | SOL 2 | Will | (P1) Haoran haoranxu510 at gmail.com (P2) Sayeed sayeedt at mit.edu (P3) George gchao at mit.edu (P4) Louis louistao at mit.edu (P5) Quanquan quanquan at mit.edu |
PS 3 | Wed, Sep. 24 | SOL 3 | Georgios | (P1) Aviv adlera at mit.edu (P2) Hunter hjl at mit.edu (P3) Anthony tonyzha1 at mit.edu (P4) William wperry at mit.edu |
PS 4 | Wed, Oct. 1 | SOL 4 | Will | (P1) Zichao zichaoqi at mit.edu (P2) Ariel arielsc at mit.edu (P3) Nirvan ntyagi at mit.edu (P4) Sizhuo szzhang at mit.edu (P5) Michael wallace_ at mit.edu |
PS 5 | Wed, Oct. 8 | SOL 5 | Will | (P1) Donggu donggu at mit.edu (P2) Stuart spbaker at mit.edu (P3) Christian coester at mit.edu (P4) Chennah chennah at mit.edu (P5) Sebastian sclaici at mit.edu (P6) Kai kaix at mit.edu |
PS 6 | Wed, Oct. 15 | SOL 6 | Will | (P1) Matt rmccutch at mit.edu (P2) Yuzhou yuzhougu at mit.edu (P3) Nishanth ndikkala at mit.edu (P4) Tianren liutr at mit.edu (P5) Anil anils at mit.edu (P6) Govind govind at mit.edu |
PS 7 | Wed, Oct. 22 | SOL 7 | Will | (P1) Jeffrey jeffling at mit.edu (P2) Mei mc2922 at mit.edu (P3) Austin ahess at mit.edu (P4) Jonathan jgoot at mit.edu (P5) Emmanouil mzampet at mit.edu |
PS 8 | Wed, Oct. 29 | Georgios | (P1) Daniel dzuo at mit.ed (P2) James payor at mit.edu (P3) Georgios gvlachos at mit.edu (P4) Adit aradha at mit.edu (P5) David drolnick at mit.edu | |
PS 9 | Wed, Nov. 5 |
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. 3: | Course introduction. Fibonacci heaps. MST. | nb | nb | |
2. | Fri, Sep. 5: | Fibonacci heaps. MST. | nb | ||
3. | Mon, Sep. 8: | Persistent data structures. | nb | nb | |
4. | Wed, Sep. 10: | Splay trees. | nb | nb | nb |
5. | Fri, Sep. 12: | Dial's Algorithm. Tries. Multi-level buckets. | nb | nb | |
6. | Mon, Sep. 15: | Van Emde Boas queues. Hashing. Universal Hashing | nb | nb | |
7. | Wed, Sep. 17: | Perfect Hashing. Intro to Network Flows | nb | nb | nb |
Fri, Sep. 19: | Student holiday, no class | ||||
8. | Mon, Sep. 22: | Network Flows. Characterization. Decomposition. Augmenting Paths. | nb | nb | |
9. | Wed, Sep. 24: | Network Flows: Maximum augmenting path. Strongly polynomial algorithms. Shortest augmenting path. | nb | nb | nb |
Fri, Sep. 26: | Optional lecture: Suffix Trees | nb | |||
10. | Mon, Sep 29: | Network Flows: Scaling. Blocking flows. | nb | nb | nb |
11. | Wed, Oct. 1: | Network Flows: Min-Cost Flows. Definitions. Chatacterization. Pseudopolynomial algorithm: cycle canceling. | nb | nb | nb |
12. | Fri, Oct. 3: | Min-Cost Flows: Feasible prices. Polynomial algorithms: shortest augmenting path; scaling. | nb | nb | |
13. | Mon, Oct. 6: | Linear-programming: definitions: canonical and standard forms, feasibility and optimization. Structure of Optima. | nb | nb | nb |
14. | Wed, Oct. 8 | Linear-Programming: Duality Theory. | nb | nb | |
Fri, Oct. 10: | Optional lecture | ||||
Mon, Oct. 13: | Columbus Day, no class. | ||||
15. | Wed, Oct. 15 | Linear-Programing: Duality Applications. | nb | ||
Fri, Oct. 17 | Optional lecture | ||||
16. | Mon, Oct. 20: | Linear Programming Algorithms: Simplex | nb | nb | |
17. | Wed, Oct. 22: | Linear-Programming Algorithms: Eillipsoid, Interior Point. | nb | ||
18. | Fri, Oct. 24: | NP-hard problems. Approximation Algorithms. Relative Approximations. | nb | nb | |
19. | Mon, Oct. 27: | PAS and FPAS. Scheduling. | nb | ||
20. | Wed, Oct. 29: | Relaxations. 3/2-approximation for TSP. ILP relaxations. | nb | ||
21. | Fri, Oct. 31 | Class canceled | |||
22. | Mon, Nov. 3 | ILP relaxations. Randomized Rounding. | |||
23. | Wed, Nov. 5 | Online Algorithms: ski rental, load balancing | online | nb | |
24. | Fri, Nov. 7 | Online algorithms: linked lists, paging. | Erik's Notes | nb1 nb2 | |
Mon, Nov. 10 | Veteran's Day, no class. | ||||
25. | Wed, Nov. 12 | Randomized online algorithms, adversaries. k-server. | |||
26. | Fri, Nov. 14 | Computational geometry: orthogonal range search, Voronoi diagram. | nb | ||
27. | Mon, Nov. 17 | Computational geometry: convex hull, sweep line, Voronoi diagram (Fortune's algorithm animation) | nb nb | ||
28. | Wed, Nov. 19 | External memory algorithms. | nb | ||
Fri, Nov. 21 | Cache oblivious algorithms. | ||||
Mon, Nov. 24 | Parallel algorithms. | ||||
Wed, Nov. 26 | Fixed-parameter tractability, treewidth. | ||||
Wed, Nov. 27 | Thanksgiving | ||||
Wed, Dec. 10 | Final Project due date. |
Tries. Suffix trees (old scribe notes, old latex sources, raw notes). |