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 | SOL 2 | form | form |
PS 3 | Wed, Sep. 27 | SOL 3 | form | form |
PS 4 | Wed, Oct. 4 | SOL 4 | form | form |
PS 5 | Wed, Oct. 11 | SOL 5 | form | form |
PS 6 | Wed, Oct. 18 | SOL 6 | form | form |
PS 7 | Wed, Oct. 25 | SOL 7 | form | form |
PS 8 | Wed, Nov. 1 | SOL 8 | form | form |
PS 9 | Wed, Nov. 8 | SOL 9 | form | form |
PS 10 | Wed, Nov. 15 | SOL 10 | form | form |
PS 11 | Wed, Nov. 22 | SOL 11 | form | form |
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. | nb | nb | ||
9. | Wed, Sep. 27: | Network Flows: Maximum augmenting path. Strongly polynomial algorithms. Shortest augmenting path. | nb | nb | ||
Fri, Sep. 29: | Student Holiday, no class | |||||
10. | Mon, Oct. 2: | Network Flows: Scaling. Blocking flows. | nb | nb | ||
11. | Wed, Oct. 4: | Network Flows: Min-Cost Flows. Definitions. Characterization. Pseudopolynomial algorithm: cycle canceling. | ||||
Fri, Oct. 6: | Suffix Trees (optional) | |||||
Mon, Oct. 9: | Columbus Day, no class | |||||
12. | Wed, Oct. 11: | Min-Cost Flows: Feasible prices. Polynomial algorithms: shortest augmenting path; scaling. | nb | nb | ||
Fri, Oct. 13: | Finish min cost flows | |||||
13. | Mon, Oct. 16: | Linear-Programming: definitions: canonical and standard forms, feasibility and optimization. Structure of Optima. | nb | nb | ||
14. | Wed, Oct. 18: | Linear-Programming: Duality Theory. | nb | nb | ||
15. | Fri, Oct. 20: | Linear-Programming: Duality Applications. | ||||
16. | Mon, Oct. 23: | Linear Programming Algorithms: Simplex | nb | |||
17. | Wed, Oct. 25: | Linear-Programming Algorithms: Ellipsoid, Interior Point. | nb | |||
18. | Fri, Oct. 27: | NP-hard problems. Approximation Algorithms. Relative Approximations. | nb | |||
19. | Mon, Oct. 30: | PAS and FPAS. Scheduling. | nb | nb | ||
20. | Wed, Nov. 1: | Relaxations. 3/2-approximation for TSP. ILP relaxations. | nb | |||
21. | Fri, Nov. 3: | ILP relaxations. Randomized Rounding. | nb | nb | ||
22. | Mon, Nov. 6: | Online Algorithms: ski rental, load balancing | nb | nb | ||
23. | Wed, Nov. 8: | Online algorithms: linked lists, paging. | nb | |||
Fri, Nov. 10: | Veteran's Day, no class. | |||||
24. | Mon, Nov. 13: | Randomized online algorithms, adversaries. k-server. | nb | |||
25. | Wed, Nov. 15: | Computational geometry: orthogonal range search, convex hull | nb | nb | ||
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. |