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 SOL 1 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 SOL 2 Will (P1) Haoran haoranxu510 at gmail.com (P2) Sayeed sayeedt at mit.edu (P3) George gchao at mit.edu (P4) Louis louistao at mit.edu (P5) Quanquan quanquan at mit.edu
PS 3 Wed, Sep. 24 SOL 3 Georgios (P1) Aviv adlera at mit.edu (P2) Hunter hjl at mit.edu (P3) Anthony tonyzha1 at mit.edu (P4) William wperry at mit.edu
PS 4 Wed, Oct. 1 SOL 4 Will (P1) Zichao zichaoqi at mit.edu (P2) Ariel arielsc at mit.edu (P3) Nirvan ntyagi at mit.edu (P4) Sizhuo szzhang at mit.edu (P5) Michael wallace_ at mit.edu
PS 5 Wed, Oct. 8 SOL 5 Will (P1) Donggu donggu at mit.edu (P2) Stuart spbaker at mit.edu (P3) Christian coester at mit.edu (P4) Chennah chennah at mit.edu (P5) Sebastian sclaici at mit.edu (P6) Kai kaix at mit.edu
PS 6 Wed, Oct. 15 SOL 6 Will (P1) Matt rmccutch at mit.edu (P2) Yuzhou yuzhougu at mit.edu (P3) Nishanth ndikkala at mit.edu (P4) Tianren liutr at mit.edu (P5) Anil anils at mit.edu (P6) Govind govind at mit.edu
PS 7 Wed, Oct. 22 SOL 7Will (P1) Jeffrey jeffling at mit.edu (P2) Mei mc2922 at mit.edu (P3) Austin ahess at mit.edu (P4) Jonathan jgoot at mit.edu (P5) Manolis mzampet at mit.edu
PS 8 Wed, Oct. 29 SOL 8 Georgios (P1) Daniel dzuo at mit.ed (P2) James payor at mit.edu (P3) Claus czheng32 at mit.edu (P4) Adit aradha at mit.edu (P5) David drolnick at mit.edu
PS 9 Wed, Nov. 5 SOL 9 Will (P1) Dai zephyred at mit.edu (P2) Quan quanli at mit.edu (P3) Omer omerc at mit.edu (P4) Santiago sperezde at mit.edu (P5) James jhirst at mit.edu
PS 10 Wed, Nov. 12 SOL 10 Georgios (P1) Michael gaoz at mit.edu (P2) Nicholas npaggi at mit.edu (P3) Giulio gueltro at mit.edu (P4) Anand asrini at mit.edu (P5) Qianli lql at mit.edu
PS 11 Wed, Nov. 19 Georgios (P2) Rik rsengupt at mit.edu (P3) Omer omerc at mit.edu (P4) Manolis mzampet at mit.edu (P5) Jianan jianan at mit.edu
PS 12 Wed, Nov. 26

Lectures

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. nb nb
6. Mon, Sep. 15: Van Emde Boas queues. Hashing. Universal Hashing nb nb
7. Wed, Sep. 17: Perfect Hashing. Intro to Network Flows nb nb nb
Fri, Sep. 19: Student holiday, no class
8. Mon, Sep. 22: Network Flows. Characterization. Decomposition. Augmenting Paths. nb nb
9. Wed, Sep. 24: Network Flows: Maximum augmenting path. Strongly polynomial algorithms. Shortest augmenting path. nb nb nb
Fri, Sep. 26: Optional lecture: Suffix Trees nb
10. Mon, Sep 29: Network Flows: Scaling. Blocking flows. nb nb nb
11. Wed, Oct. 1: Network Flows: 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. nb
Fri, Oct. 17 Optional lecture
16. Mon, Oct. 20: Linear Programming Algorithms: Simplex nb nb
17. Wed, Oct. 22: Linear-Programming Algorithms: Eillipsoid, Interior Point. nb
18. Fri, Oct. 24: NP-hard problems. Approximation Algorithms. Relative Approximations. nb nb
19. Mon, Oct. 27: PAS and FPAS. Scheduling. nb
20. Wed, Oct. 29: Relaxations. 3/2-approximation for TSP. ILP relaxations. nb
21. Fri, Oct. 31 TBD
22. Mon, Nov. 3 ILP relaxations. Randomized Rounding.
23. Wed, Nov. 5 Online Algorithms: ski rental, load balancing onlinenb 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, convex hull nb
27. Mon, Nov. 17 Computational geometry: 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).

References

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