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