6.854/18.415J: Advanced Algorithms (Fall 2003)

Lecture: Monday and Wednesday 2:30-4 in 3-442
Units: 3-0-9 Graduate H-level
Professor: Erik Demaine edemaine@mit.edu Office hours: By appt. in NE43-317
Professor: David Karger karger@lcs.mit.edu Office hours: By appt. in NE43-322
TA: Grant Wang gjw@theory.lcs.mit.edu Office hours: 10:00-11:00 am, Friday in NE43-313
Course assistant: Kathleen Dickey kvdickey@mit.edu Office: NE43-330

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. See the handout for more details.

Course Schedule

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

Lecture 1. Wed, Sep. 3: Course introduction. Rabin-Karp fingerprinting algorithm. Suffix trees. (scribe notes, raw)
Lecture 2. Mon, Sep. 8: Suffix trees (continued) (scribe notes), Fibonacci heaps
Lecture 3. Wed, Sep. 10: Fibonacci heaps (continued) (scribe notes), van Emde Boas priority queues.
Lecture 4. Mon, Sep. 15: Van Emde Boas priority queues (continued) (scribe notes), integer sorting.
Lecture 5. Wed, Sep. 17: Integer sorting (continued) (scribe notes) , persistent data structures (scribe notes, raw notes)
Lecture 6. Wed, Sep. 24: Network flow - introduciton, augmenting paths (scribe notes)
Lecture 7. Mon, Sep. 29: Network flow - bit scaling, blocking flow (scribe notes)
Lecture 8. Wed, Oct. 1: Minimum cost maximum flow, minimum cost circulation (scribe notes)
Lecture 9. Mon, Oct. 6: Minimum cost circulation, linear programming (mcc notes, lp notes)
Lecture 10. Wed, Oct. 8: Farkas' lemma, Duality (scribe notes)
Lecture 11. Wed, Oct. 15: Dual-taking, complementary slackness (scribe notes)
Lecture 12. Mon, Oct. 20: Approximation algorithms (scribe notes)
Lecture 13. Wed, Oct. 22: Approximation algorithms, continued (scribe notes)
Lecture 14. Mon, Oct. 27: Relaxation techniques (scribe notes)
Lecture 15. Wed, Oct. 29: Fixed-parameter tractability (scribe notes)
Lecture 16. Mon, Nov. 3: Fixed-parameter tractability, computational geometry: line-sweep
Lecture 17. Wed, Nov. 5: Randomized incremental construction, backwards analysis
Lecture 18. Wed, Nov. 12: More randomized incremental construction, range searching (scribe notes)
Lecture 19. Mon, Nov. 17: Online algorithms (scribe notes)
Lecture 20. Wed, Nov. 19: More online algorithms (scribe notes)
Lecture 21. Mon, Nov. 24: External-memory algorithms (scribe notes)
Lecture 22. Wed, Nov. 26: Cache-oblivious algorithms (scribe notes)
Lecture 23. Mon, Dec. 1: Streaming algorithms, parallel algorithms and circuits (scribe notes)
Lecture 24. Wed, Dec. 3: More parallel algorithms: list ranking
Lecture 25. Mon, Dec. 8: Count-min data structure, applications to streaming
Lecture 26. Wed, Dec. 10: Fast Fourier Transform (scribe notes)

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
  2. Problem set 1 solutions, diagram
  3. Problem set 2
  4. Problem set 2 solutions
  5. Problem set 3
  6. Problem set 3 solutions
  7. Problem set 4
  8. Problem set 4 solutions
  9. Problem set 5
  10. Problem set 5 solutions
  11. Problem set 6
  12. Problem set 6 solutions
  13. Problem set 7
  14. Problem set 7 solutions
  15. Problem set 8
  16. Problem set 8 solutions
  17. Problem set 9
  18. Problem set 9 solutions
  19. Problem set 10
  20. Problem set 10 solutions
  21. Problem set 11
  22. Problem set 11 solutions
  23. Problem set 12
  24. Problem set 12 solutions
  25. Problem set 13
  26. Problem set 13 solutions

Other Course Handouts

  1. Course information