6.854/18.415J: Advanced Algorithms (Fall 2005)

Lecture: Monday and Wednesday 2:30-4 in 32-144.
Recitations: Friday 2:30-4 in 32-144. (Note that lecture material will be presented during the recitations.)
Units: 5-0-7 Graduate H-level
Professor: David Karger karger at mit edu Office hours: By appt. in Building 32, Room G592
TA: Anastasios Sidiropoulos tasos at mit edu Office hours: Monday, 5pm-6pm, in Building 32, Room G596
Sergey Yekhanin yekhanin at mit edu Office hours: Monday, 1pm-2pm, in Building 32, Room G614
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.

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.

1. Problem Set 1 (pdf). Due: Wed, Sep 14. Solutions (pdf).
2. Problem Set 2 (pdf). Due: Wed, Sep 21. Solutions, and complementary diagram (courtesy of Ali Mohammad).
3. Problem Set 3 (pdf). Due: Wed, Sep 28. Solutions (pdf).
4. Problem Set 4 (pdf). Due: Fri, Oct 7. Solutions.
5. Problem Set 5 (pdf). Due: Wed, Oct 12. Solutions.
6. Problem Set 6 (pdf). Due: Wed, Oct 19. Solutions.
7. Problem Set 7 (pdf). Due: Wed, Oct 26. Solutions.
8. Problem Set 8 (pdf). Due: Wed, Nov 2. Solutions.
9. Problem Set 9 (pdf). Due: Wed, Nov 9. Solutions.
10. Problem Set 10 (pdf). Due: Wed, Nov 16. Solutions.
11. Problem Set 11 (pdf). Due: Wed, Nov 23. Solutions.
12. Problem Set 12 (pdf). Due: Wed, Nov 28 and Mon, Dec 5. Solutions.

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.

Other Course Handouts

  1. Course information (html version).
  2. Papers related to Lecture 2:
  3. Course Project Description (pdf).

Preliminary Course Schedule

The following is last year's schedule, to give some sense of the course's content. You can also get the actual course notes here.
Lecture 1. Course introduction. Fibonacci heaps.
Lecture 2. Persistent data structures. Suffix trees.
Lecture 3. Suffix trees (continued).
Lecture 4. Treaps.
Recitation 1. Splay trees.
Lecture 5. Hashing: 2-universal, perfect hashing. Fingerprinting.
Lecture 6. Fingerprinting (continued). Max flows.
Lecture 7. Max flows (continued).
Lecture 8. Max flows (continued).
Lecture 9. Max flows (continued -- max flow of min cost)
Recitation 2. Dynamic Trees. Preflow-push algorithm.
Lecture 10. Min cost flow algorithms. Linear programming
Lecture 11. Linear programming. Farkas Lemma. Duality.
Recitation 3. Goldberg-Tarjan Min-cost Flow.
Lecture 12. Linear programming: more duality (weak and strong duality). Complementary slackness conditions
Lecture 13. Linear programming: complementary slackness conditions.
Lecture 14. LP: Interior points algorithm. Approximation algorithms: constant, relative approximation.
Lecture 15. Approximation algorithm (continuation): PAS, FPAS, rounding, enumeration.
Lecture 16. Approximation algorithm (continuation): rounding, relaxation.
Lecture 17. Approximation algorithm (continuation): LP relaxation, randomized rounding.
Lecture 18. Fixed parameter tractability.
Lecture 19. Fixed parameter tractability -- treewidth. Online algorithms.
Lecture 20. Online algorithms (continued): paging, randomization , potential functions.
Lecture 21. Randomized online algorithms (adversarial models, Marking algorithm).
Lecture 22. Lower bounds for randomized online algorithms. Geometry: range search.
Lecture 23. Convex Hulls, voronoi diagrams.
Lecture 24. Voronoi Diagrams (cont'd), randomized incremental construction: binary space partition.
Lecture 25. Backwards Analysis for RIC: convex hull, linear programming.
Lecture 26. External memory algorithms.
Lecture 27. Cache-oblivious algorithms.