6.854/18.415J: Advanced Algorithms (Fall 2006)

Lecture: Monday, Wednesday, and Friday 2:30-4 in 32-144.
Units: 5-0-7 Graduate H-level
Professor: David Karger karger at mit edu Office hours: By appt. in Building 32, Room G592
TA: Punyashloka Biswal punya at mit edu Office hours: Mondays, 6pm onwards in lounge next to "Theory Lab" (32G-575)
Course assistant: Be Blackburn be at theory csail mit edu Office: Building 32, Room G692

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. 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.

Here is some information about the final project.

Problem Sets

Collaboration on problem sets is strongly encouraged except where explicitly forbidden. However, each person must independently write up his/her own solution, and you must list all collaborators on your problem set. You may not seek out answers from other sources without prior perimssion. In particular, no bibles.

Problem Set 1 Due Wed, Sep. 13 Solutions
Problem Set 2 Due Wed, Sep. 20 Solutions
Problem Set 3 Due Wed, Sep. 27 Solutions
Problem Set 4 Due Wed, Oct. 4 Solutions
Problem Set 5 Due Fri, Oct. 13 (note unusual day) Solutions
Problem Set 6 Due Wed, Oct. 18 Solutions
Problem Set 7 Due Wed, Oct. 25 Solutions
Problem Set 8 Due Wed, Nov. 1 Solutions
Problem Set 9 Due Wed, Nov. 8 Solutions
Problem Set 10 Due Wed, Nov. 15
Problem Set 11 Due Wed, Nov. 22

Lectures

The dates are fixed! Props to David Glasser for helping me find the correct dates for various things. —TA

1. Wed, Sep. 6: Course introduction. Fibonacci heaps (scribe notes, latex source) (raw notes on intro, Fibonacci heaps).
2. Fri, Sep. 8: MST. Persistent data structures (notes, sources) (raw notes on persistent data structures).
3. Mon, Sep. 11: Splay trees (old scribe notes, old latex sources, raw notes ).
4. Wed, Sep. 13: Splay trees. Suffix trees (old scribe notes, old latex sources, raw notes). Tries.
5. Fri, Sep. 15: Suffix trees. Tries. Dial's Algorithm.
6. Mon, Sep. 18: Dijkstra's Algorithm. Van Emde Boas Queues (old scribe notes, old latex sources)
(raw notes on multi-level buckets, and vEB queues).
7. Wed, Sep. 20: Van Emde Boas Queues (cont.). Hashing (old scribe notes, old latex sources) (raw notes on hashing).
8. Fri, Sep. 22: 2-Level Hashing. Network Flows (scribe notes, latex sources, raw notes on flow).
9. Wed, Sep. 27: Network Flows: Augmenting Paths, Maximum Augmenting Paths, Scaling. (see notes from previous lecture)
10. Fri, Sep. 29: Reductions between Flow Problems. Bipartite Matching. Shortest Augmenting Path. Blocking Flows
(scribe notes, latex sources).
11. Wed, Oct. 4: Blocking Flows (scribe notes, latex sources).
12. Fri, Oct. 6: Min-Cost Flows: feasible prices. (scribe notes, sources, raw notes on min-cost flow).
13. Wed, Oct. 11: Min-Cost Flows: complementary slackness, pseudopolynomial solution.
(scribe notes, sources).
14. Fri, Oct. 13: Linear-programming: definitions: canonical and standard forms, feasibility and optimization. (scribe notes, sources, raw notes on linear programming).
15. Mon, Oct. 16 Linear-Programming: structure of Optima. (scribe notes, sources)
16. Wed, Oct. 18 Linear-Programming: weak duality.
17. Fri, Oct. 20: Linear-Programming. Strong Duality. (scribe notes, sources).
18. Mon, Oct. 23: Linear-Programming. Complementary Slackness. Algorithms: Simplex, Ellipsoid. (old scribe notes with sources).
19. Wed, Oct. 25 Linear-Programming. Algorithms: Interior Point. NP-hard problems. (scribe notes, latex sources).
20. Fri, Oct. 27: Approximation Algorithms. (scribe notes, latex sources).
21. Mon, Oct. 30: 4/3-approximation for TSP. Scheduling. (notes, sources)
22. Wed, Nov. 1: Scheduling. ILP relaxations. (scribe notes, sources)
Fri, Nov. 3: [Optional] Euclidean TSP.
23. Mon, Nov. 6 Fixed-parameter tractability. (scribe notes, sources)
24. Wed, Nov. 8 More Fixed-parameter tractability. Treewidth. (notes, sources)
25. Mon, Nov. 13 Online algorithms: ski rental, load balancing. (notes, sources)
26. Wed, Nov. 15 Online algorithms: paging. Randomized online algorithms, adversaries. (notes, sources)
27. Fri, Nov. 17 Online algorithms: k-server. Yao's minimax principle. (notes, sources)
28. Mon, Nov. 20 Computational geometry: orthogonal range search, sweep algorithms (segment intersections) (notes, sources)
29. Wed, Nov. 22 Computational geometry: convex hull (notes, sources)
30. Mon, Nov. 27 [Optional] Computational geometry: Voronoi diagrams (notes, sources)
31. Wed, Nov. 29 [Optional] Finish computational geometry. External memory algorithms. (raw notes)
32. Wed, Dec. 6 [Optional] External memory continued.
33. Mon, Dec. 11 [Optional] External memory: cache-oblivious algorithms. Parallel algorithms: circuits and PRAMs. (raw notes on parallel algorithms)

References

The stellar course page lists papers that are only available online to the MIT community.
Wed, Sep. 6
Fri, Sep. 8
Mon, Sep. 11
Wed, Sep. 13
Fri, Sep. 15
Mon, Sep. 18

Last Year's Lectures

Lecture 1. Wed, Sep. 7: Course introduction. Fibonacci heaps (scribe notes, latex source) (raw notes on intro, Fibonacci heaps).
Lecture 2. Fri, Sep. 9: MST. Persistent data structures (scribe notes, latex sources) (raw notes on persistent data structures).
Lecture 3. Mon, Sep. 12: Splay trees (scribe notes, latex sources).
Lecture 4. Wed, Sep. 14: Splay trees. Suffix trees (scribe notes, latex sources). Tries.
Lecture 5. Fri, Sep. 16: Suffix trees. Tries. Dial's Algorithm.
Lecture 6. Wed, Sep. 21: Dijkstra's Algorithm.
Van Emde Boas Queues (scribe notes, latex sources)
(raw notes on multi-level buckets, and vEB queues).
Lecture 7. Fri, Sep. 23: Van Emde Boas Queues (cont.). Hashing (scribe notes, latex sources) (raw notes on hashing).
Lecture 8. Mon, Sep. 26: 2-Level Hashing. Network Flows (scribe notes, latex sources).
Lecture 9. Wed, Sep. 28: Network Flows: Augmenting Paths, Maximum Augmenting Paths, Scaling.
Lecture 10. Fri, Sep. 30: Reductions between Flow Problems. Bipartite Matching. Shortest Augmenting Path. Blocking Flows (scribe notes, latex sources).
Lecture 11. Mon, Oct. 3: Blocking Flows (scribe notes, latex sources).
Recitation 1. Wed, Oct. 5: Dynamic Trees. Push-Relabel Max-Flow Algorithm.
Lecture 12. Fri, Oct. 7: Min-Cost Flows (scribe notes, latex sources).
Lecture 13. Wed, Oct. 12: Min-Cost Flows. Linear Programming. (scribe notes, latex sources).
Lecture 14. Fri, Oct. 14: Linear-Programming. Structure of Optima. Weak Duality. (latex sources).
Lecture 15. Mon, Oct. 17: Linear-Programming. Strong Duality. (latex sources).
Recitation 2. Wed, Oct. 19: Simplex
Lecture 16. Fri, Oct. 21: Linear-Programming. Complementary Slackness. Algorithms: Simplex, Ellipsoid. (latex sources).
Lecture 17. Mon, Oct. 24: Linear-Programming. Algorithms: Interior Point. NP-hard problems. (latex sources).
Lecture 18. Fri, Oct. 28: Approximation Algorithms. (latex sources).
Lecture 19. Mon, Oct. 31: 4/3-approximation for TSP. (latex sources).
Lecture 20. Wed, Nov. 2: Relaxations. Directed TSP. (latex sources).
Lecture 21. Fri, Nov. 4: Randomized rounding, Chernoff Bound, Fixed parameter tractability, Kernelization (latex sources).
Lecture 22. Wed Nov. 09: Online algorithms (ski rental, load balancing, paging) (latex sources).
Lecture 23. Mon Nov. 14: Randomized online algorithms (adversaries, Fiat's marking algorithm, potential functions, Yao's minimax principle) (latex sources).
Lecture 24. Wed Nov. 16: k-server problem, double-coverage algorithm, Computational geometry intro (orthogonal range search) (latex sources).
Lecture 25. Fri Nov. 18: Sweep algorithms (convex hull, segment intersection, Voronoi diagrams) (latex sources).
Lecture 26. Mon Nov. 21: Sweep algorithms (Voronoi diagrams).
Randomized Incremental Constructions. Backwards Analysis.
Linear Programming in Fixed Dimension.
Lecture 27. Mon Nov. 28: (Optional material) External memory algorithms.
Lecture 28. Wed Nov. 30: (Optional material) Cache oblivious algorithms: matrix multiplication, linked lists, median.
Lecture 29. Fri Dec. 2: (Optional material) Cache oblivious algorithms: Search.
Streaming Model.

Scribing: Here is the LaTeX style file for scribing, and an example use of it.