6.854/18.415J: Advanced Algorithms (Fall 2017)

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

Course Announcements

Course Overview

The need for efficient algorithms arises in nearly every area of computer science. But the type of problem to be solved, the notion of what algorithms are "efficient," and even the model of computation can vary widely from area to area.
This course is designed to be a capstone course in algorithms that surveys some of the most powerful algorithmic techniques and key computational models. It aims to bring the students up to the level where they can read and understand research papers.
We will cover a broad selection of topics including amortization, hashing, dimensionality reduction, bit scaling, network flow, linear programming, and approximation algorithms. Domains that we will explore include data structures; algorithmic graph theory; streaming algorithms; online algorithms; parallel algorithms; computational geometry; external memory/cache oblivious algorithms; and continuous optimization.

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 Sets

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


Note: The schedule is subject to change, but we will finish lectures before Thanksgiving.

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.