6.854/18.415J: Advanced Algorithms (Fall 2014)

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

Course Announcement

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. In this second course in algorithms, we will survey many of the techniques that apply broadly in the design of efficient algorithms, and study their application in a wide range of application domains and computational models. Techniques to be covered include amortization, randomization, fingerprinting, word-level parallelism, bit scaling, dynamic programming, network flow, linear programming, fixed-parameter algorithms, and approximation algorithms. Domains include string algorithms; network optimization; parallel algorithms; computational geometry; online algorithms; external memory, cache, and streaming algorithms; and data structures.

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 Sets

Problem Set Due Date Solutions Grading Supervisor Graders
PS 1 Fri, Sep. 12 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


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

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. Van Emde Boas queues. nb nb
6. Mon, Sep. 15: Van Emde Boas queues cont. Hashing. nb
7. Wed, Sep. 17: Universal Hashing. Perfect Hashing. nb nb nb
Fri, Sep. 19: Student holiday, no class
8. Mon, Sep. 22: Network Flows. Characterization. Decomposition. Augmenting Paths. nb
9. Wed, Sep. 24: Network Flows: Maximum augmenting path. scaling. nb nb nb
Fri, Sep. 26: Optional lecture: Suffix Trees nb
10. Mon, Sep 29: Network Flows: Strongly polynomial algorithms. Shortest augmenting path. Blocking flows. nb nb nb
11. Wed, Oct. 1: Network Flows: More blocking flows. Link Cut trees. 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.
Fri, Oct. 17 Optional lecture
16. Mon, Oct. 20: Linear Programming Algorithms: Simplex nb
17. Wed, Oct. 22: Linear-Programming Algorithms: Eillipsoid.
18. Fri, Oct. 24: Linear-Programming Algorithms: Interior Point.
19. Mon, Oct. 27: NP-hard problems. Approximation Algorithms. Relative Approximations. nb nb
20. Wed, Oct. 29: PAS and FPAS. Scheduling. nb
21. Fri, Oct. 31 Relaxations. 3/2-approximation for TSP. ILP relaxations. nb
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.
Note: The schedule is subject to change, but we will finish lectures before thanksgiving.

Other Material

Tries. Suffix trees (old scribe notes, old latex sources, raw notes).


Wed, Sep. 3
Mon, Sep. 8
Wed, Sep. 10
Fri, Sep. 12
Mon, Sep. 15
Wed, Oct. 8