Lecture: | Monday, Wednesday, and Friday 2:30-4 in 32-141. | |||
Units: | 5-0-7 Graduate H-level | |||
Instructor: | David Karger | karger at mit edu | Office hours: Arrange by email. In Building 32, Room G592 | |
TAs: | Justin Kopinsky | jkopin at mit.edu | ||
Luke Schaeffer | lrs at mit.edu | |||
Office hours: | Mondays and Fridays 4:00-5:00 Stata G5 lounge (right outside the elevators) | |||
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 | (Mandatory) Time Report | (Optional) Difficulty/Usefulness Survey |
---|---|---|---|---|
PS 1 | Fri, Sep. 15 | SOL 1 | form | form |
PS 2 | Wed, Sep. 20 | form | form | |
PS 3 | Wed, Sep. 27 | form | form | |
PS 4 | Wed, Oct. 4 | |||
PS 5 | Wed, Oct. 11 | |||
PS 6 | Wed, Oct. 18 | |||
PS 7 | Wed, Oct. 25 | |||
PS 8 | Wed, Nov. 1 | |||
PS 9 | Wed, Nov. 8 | |||
PS 10 | Wed, Nov. 15 | |||
PS 11 | Wed, Nov. 22 |
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. 6: | Course introduction. Fibonacci heaps. MST. | nb | nb | |
2. | Fri, Sep. 8: | Fibonacci heaps. Persistent Data Structures. | nb | nb | |
3. | Mon, Sep. 11: | Persistent data structures. | |||
4. | Wed, Sep. 13: | Splay trees. | nb | nb | |
5. | Fri, Sep. 15: | Dial's Algorithm. Tries. Multi-level buckets. | nb | ||
6. | Mon, Sep. 18: | Van Emde Boas queues. Hashing. Universal Hashing | nb | nb | |
7. | Wed, Sep. 20: | Perfect Hashing. Intro to Network Flows | |||
Fri, Sep. 22: | Rosh Hashanah, no class | ||||
8. | Mon, Sep. 25: | Network Flows. Characterization. Decomposition. Augmenting Paths. | |||
9. | Wed, Sep. 27: | Network Flows: Maximum augmenting path. Strongly polynomial algorithms. Shortest augmenting path. | |||
Fri, Sep. 29: | Student Holiday, no class | ||||
10. | Mon, Oct. 2: | Network Flows: Scaling. Blocking flows. | |||
11. | Wed, Oct. 4: | Network Flows: Min-Cost Flows. Definitions. Characterization. Pseudopolynomial algorithm: cycle canceling. | |||
Fri, Oct. 6: | TBD; possibly optional push relabel lecture | ||||
Mon, Oct. 9: | Columbus Day, no class | ||||
12. | Wed, Oct. 11: | Min-Cost Flows: Feasible prices. Polynomial algorithms: shortest augmenting path; scaling. | |||
Fri, Oct. 13: | TBD lecture | ||||
13. | Mon, Oct. 16: | Linear-Programming: definitions: canonical and standard forms, feasibility and optimization. Structure of Optima. | |||
14. | Wed, Oct. 18: | Linear-Programming: Duality Theory. | |||
15. | Fri, Oct. 20: | Linear-Programming: Duality Applications. | |||
16. | Mon, Oct. 23: | Linear Programming Algorithms: Simplex | |||
17. | Wed, Oct. 25: | Linear-Programming Algorithms: Ellipsoid, Interior Point. | |||
18. | Fri, Oct. 27: | NP-hard problems. Approximation Algorithms. Relative Approximations. | |||
19. | Mon, Oct. 30: | PAS and FPAS. Scheduling. | |||
20. | Wed, Nov. 1: | Relaxations. 3/2-approximation for TSP. ILP relaxations. | |||
21. | Fri, Nov. 3: | ILP relaxations. Randomized Rounding. | |||
22. | Mon, Nov. 6: | Online Algorithms: ski rental, load balancing | |||
23. | Wed, Nov. 8: | Online algorithms: linked lists, paging. | |||
Fri, Nov. 10: | Veteran's Day, no class. | ||||
24. | Mon, Nov. 13: | Randomized online algorithms, adversaries. k-server. | |||
25. | Wed, Nov. 15: | Computational geometry: orthogonal range search, convex hull | |||
26. | Fri, Nov. 17: | Computational geometry: Voronoi diagram (Fortune's algorithm animation) | |||
27. | Mon, Nov. 20: | External memory algorithms. | |||
28. | Wed, Nov. 22: | Buffer trees. Cache oblivious algorithms. | |||
Thurs, Nov. 23: | Thanksgiving | ||||
29. | Mon, Nov. 27: | Parallel algorithms--circuits. | |||
30. | Wed, Nov. 29: | Parallel algorithms--PRAMs. | |||
Fri, Dec. 1: | |||||
Mon, Dec. 4: | |||||
Wed, Dec. 6: | |||||
Fri, Dec. 8: | |||||
Mon, Dec. 11: | In-class peer editing assignment. | ||||
Wed, Dec. 13: | Final Project due date. Possible optional lecture. |