6.854/18.415J: Advanced Algorithms (Fall 2013)

Lecture: Monday, Wednesday, and Friday 2:30-4 in 32-155.
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: Ofir Nachum ofir at mit.edu Office hours: Mon 4:15PM - 5:45PM and Fri 4:15PM - 5PM, CSAIL 5th floor lounge
  Jin Hao Wan jhwan at mit.edu Office hours: Mon 4:15PM - 5:45PM and Fri 4:15PM - 5PM, CSAIL 5th floor lounge
  Please come back frequently to check the office hour updates.
Course assistant: Nina Olff olff@csail.mit.edu Office: Building 32, Room 32-G764 and 32-G434

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 Wed, Sep. 18 SOL 1 Jin gauravjs@mit.edu (P1), Madalina Persu mpersu@mit.edu (P2), Fermi Ma fermima@mit.edu + Erik Waingarten eaw@mit.edu (P3), Rajan Udwani rudwani@mit.edu (P5), Georgios Vlachos gvlachos@mit.edu + Max Zimet maxzimet@mit.edu (P6)
PS 2 Wed, Sep. 25 SOL 2 Ofir Pritish Kamath pritish@mit.edu + Eugenio Fortanely erf@mit.edu (P1+P3), Chrisantha Perera cperera@mit.edu + Daniel Grier grierd@mit.edu (P2), Matt Jordan jordanm@mit.edu (P4), Eric Mannes mannes@mit.edu (P5)
PS 3 Wed, Oct. 2 SOL 3 Jin John Peebles jpeebles@mit.edu + Max Kolysh mkolysh@mit.edu (P1), Caelan Garrett caelan@mit.edu + Chris Graves graves@mit.edu (P2), Prashant Vasudevan prashvas@mit.edu (P3), Ali Vakilian vakilian@mit.edu (P4), Casey O'Brien cmobrien@mit.edu (P5)
PS 4 Wed, Oct. 9 SOL 4 Ofir Victor Pontis vpontis@mit.edu (P1), Anvisha Pai anvishap@mit.edu (P2), Varun Ramaswamy vrama@mit.edu + Jan Polášek jpolasek@mit.edu (P3), Dennis Tseng dtseng@mit.edu (P4), Julian Chaidez jchaidez@mit.edu + Maryam Aliakbarpour maryama@mit.edu (P5)
PS 5 Wed, Oct. 16 SOL 5 Jin Chrisantha Perera cperera@mit.edu + Hoon Cho hhcho@mit.edu (P1), Bianca Homberg bhomberg@mit.edu (P2), Emily Lindemer lindemer@mit.edu (P3), Ernest Zeidman zeidman@mit.edu (P4 + P6), Laphonchai Jirachup doraepon@mit.edu + Suthee Ruangwises Suthee@mit.edu (P5)
PS 6 Wed, Oct. 23 SOL 6 Ofir Ellen Finch finche@mit.edu + Sam Elder same@mit.edu (P1), Miles Lubin mlubin@mit.edu (P2), Alex Wein awein@mit.edu (P3), Jerry Li jerryzli@mit.edu (P4), Amy Ousterhat aousterh@mit.edu (P5)
PS 7 Wed, Oct. 30 SOL 7 Jin Erin Davis edavis5@mit.edu (P1), Payut Pantawongdecha payutp@mit.edu (P2), Aloni Cohen aloni@mit.edu (P3), Bryan Collazo bcollazo@mit.edu (P4), Fereshte Khani fereshtekhani@gmail.com (P5)
PS 8 Wed, Nov. 6 SOL 8 Ofir Rumen Hristov rhristov@mit.edu (P1), Anderson Wang asw@mit.edu (P2), Leon Lin leonxlin@mit.edu (P3), Min Zhang mzhang94@mit.edu (P4), Michael Xu michaelx@mit.edu + Tommy Zhang trzhang@mit.edu (P5), Robi Bhattacharjee robibhat@mit.edu (P6)
PS 9 Wed, Nov. 13 SOL 9 Ofir Patrick Yang pbyang@mit.edu (P1), Phillip Ai pzai@mit.edu (P2), Mohammed Ali Auoad aaouad@mit.edu (P3), Yun William Yu ywy@mit.edu (P4), Joseph DelPreto delpreto@mit.edu (P5)
PS 10 Wed, Nov. 20 SOL 10 Jin Yongyi Chen yongyic@mit.edu (P1), Jin Pan jinpan@mit.edu (P2), Neil Gurram ngurram@mit.edu (P3), Lauren Stephens lhs@mit.edu (P4), Adam Eagle areagle@mit.edu (P5)
PS 11 Wed, Nov. 27 SOL 11 Jin Ulziibayar Otgonbaatar ulziibay@mit.edu (P1 + P4), Evangelos Taratoris evtara@mit.edu (P2 + P4), Michael DuPlessis mdupless928@gmail.com (P3)

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. 4: Course introduction. Fibonacci heaps. MST. nb nb
Fri, Sep. 6: No class.
2. Mon, Sep. 9: Fibonacci heaps. MST. nb
3. Wed, Sep. 11: Persistent data structures. nb nb
4. Fri, Sep. 13: Splay trees. nb nb nb
5. Mon, Sep. 16: Dial's Algorithm. Tries. Multi-level buckets. Van Emde Boas queues. nb nb
6. Wed, Sep. 18: Van Emde Boas queues cont. Hashing. nb
Fri, Sep. 20: Student holiday, no class
7. Mon, Sep. 23: Universal Hashing. Perfect Hashing. nb nb nb
8. Wed, Sep. 25: Network Flows. Characterization. Decomposition. Augmenting Paths. nb
Fri, Sep. 27: Optional lecture: Suffix Trees nb
9. Mon, Sep. 30: Network Flows: Maximum augmenting path. scaling. nb nb nb
10. Wed, Oct. 2: Network Flows: Strongly polynomial algorithms. Shortest augmenting path. Blocking flows. nb nb nb
Fri, Oct. 4: Optional Lecture: Push-relabel.
11. Mon, Oct. 7: Network Flows: More blocking flows. Link Cut trees. Min-Cost Flows. Definitions. Chatacterization. Pseudopolynomial algorithm: cycle canceling. nb nb nb
12. Wed, Oct. 9: Min-Cost Flows: Feasible prices. Polynomial algorithms: shortest augmenting path; scaling. nb nb
13. Fri, Oct. 11: Linear-programming: definitions: canonical and standard forms, feasibility and optimization. Structure of Optima. nb nb nb
Mon, Oct. 14: Columbus Day, no class.
14. Wed, Oct. 16 Linear-Programming: Duality Theory. nb nb
15. Fri, Oct. 18 Linear-Programing: Duality Applications.
16. Mon, Oct. 21: Linear Programming Algorithms: Simplex nb
17. Wed, Oct. 23: Linear-Programming Algorithms: Eillipsoid.
18. Fri, Oct. 25: Linear-Programming Algorithms: Interior Point.
19. Mon, Oct. 28: NP-hard problems. Approximation Algorithms. Relative Approximations. nb nb
20. Wed, Oct. 30: PAS and FPAS. Scheduling. nb
21. Fri, Nov. 1 Relaxations. 3/2-approximation for TSP. ILP relaxations. nb
22. Mon, Nov. 4 ILP relaxations. Randomized Rounding.
23. Wed, Nov. 6 Online Algorithms: ski rental, load balancing online nb
24. Fri, Nov. 8 Online algorithms: linked lists, paging. Erik's Notes nb1 nb2
Mon, Nov. 11 Veteran's Day, no class.
25. Wed, Nov. 13 Randomized online algorithms, adversaries. k-server.
26. Fri, Nov. 15 Computational geometry: orthogonal range search, Voronoi diagram. nb
27. Mon, Nov. 18 Computational geometry: convex hull, sweep line, Voronoi diagram (Fortune's algorithm animation) nb nb
28. Wed, Nov. 20 External memory algorithms. nb
Fri, Nov. 22 Cache oblivious algorithms.
Mon, Nov. 25 Parallel algorithms.
Wed, Nov. 27 Fixed-parameter tractability, treewidth.
Wed, Dec. 11 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. 4
Wed, Sep. 11
Fri, Sep. 13
Mon, Sep. 16