6.854/18.415J: Advanced Algorithms (Fall 2016)

Lecture: Monday, Wednesday, and Friday 2:30-4 in 32-141.
Units: 5-0-7 Graduate H-level
Instructors: David Karger karger at mit edu Office hours: Arrange by email. In Building 32, Room G592
Aleksander Mądry madry at mit edu Office hours: Arrange by email. In Building 32, Room G666
TAs: John Peebles jpeebles at mit.edu
  Tal Wagner talw at mit.edu
Office hours: Mondays, 4:30pm-5:30pm, Room 36-112
Fridays, 4:00pm-5:00pm, Room 36-144
Course assistant: Rebecca Yadegar ryadegar at csail.mit.edu

Submit PSET 11 Here


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.
This course is designed to be a capstone course in algorithms that surveys some of the most powerful algorithmic techniques and key computational models. It aims to bring the students up to the level where they can read and understand research papers.
We will cover a broad selection of topics including amortization, hashing, dimensionality reduction, bit scaling, network flow, linear programing, and approximation algorithms. Domains that we will explore include data structures; algorithmic graph theory; streaming algorithms; online algorithms; parallel algorithms; computational geometry; external memory/cache oblivious algorithms; and continuous optimization.

The prerequisites for this class are strong performance in undergraduate courses in algorithms (e.g., 6.046/18.410) and discrete mathematics and probability (6.042 is more than sufficient), in addition to substantial 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 Grading Supervisor Graders (Mandatory) Time Report (Optional) Difficulty/Usefulness Survey
PS 1 Fri, Sep. 16 John sahasag@mit.edu 3(c); bristy@mit.edu 2; baxelrod@mit.edu 1; hongzi@mit.edu 5(c,d); ececca@mit.edu 5(a,b); yilundu@mit.edu 4; epayne@mit.edu 3(a,b) Link Link
PS 2 Wed, Sep. 21 Tal P1 nkb@mit.edu ;
P2 zanger@mit.edu ;
P3 umaroy@mit.edu ;
P4 timngo@mit.edu ;
P5 weiqiaoh@mit.edu ;
P6 ztzhang@mit.edu
Link Link
PS 3 Wed, Sep. 28 John P1 sshader@mit.edu;
P2 ycy@mit.edu;
P3 jimmy42@mit.edu;
P4 kaxiotis@mit.edu;
P5 tianxiao@mit.edu;
P6 ctunoku+6854@mit.edu
Link Link
PS 4 Wed, Oct. 5 Tal P1 dzaefn@mit.edu ;
P2 keyulu@mit.edu ;
P3 pahrens@mit.edu ;
P4 luh@mit.edu ;
P5 ronuchit@mit.edu
Link Link
PS 5 Fri, Oct. 14 John P1 hayks@mit.edu;
P2 arsen@mit.edu;
P3 alet+6854@mit.edu;
P4 hujh@mit.edu;
P5 bpchen@mit.edu
Link Link
PS 6 Wed, Oct. 19 Tal P1 abhijitm@mit.edu ;
P2 kocabey@mit.edu ;
P3 diomidov@mit.edu ;
P4 akkas@mit.edu ;
P5 jbpatel@mit.edu
Link Link
PS 7 Wed, Oct. 26 John P1 tclin@mit.edu;
P2 calvin3@mit.edu ;
P3 karren@mit.edu ;
P4 yangk@mit.edu ;
P5 aradhana@mit.edu
Link Link
PS 8 Wed, Nov. 2 John P1 davidbau@mit.edu;
P2 amakelov@mit.edu;
P3 jeetmo@mit.edu;
P4 trattner@mit.edu
Link Link
PS 9 Wed, Nov. 11 Tal P1 kelswong@mit.edu ;
P2 trattner@mit.edu ;
P3 bando@mit.edu ;
P4 badea@mit.edu ;
P5 schiefer@mit.edu
Link Link
PS 10 Wed, Nov. 11 Tal P1 bmhuang@mit.edu ;
P2 ashwath@mit.edu ;
P3 jayzee@mit.edu ;
P4 alexjl@mit.edu ;
P5 shahp@mit.edu
Link Link
PS 11 Wed, Nov. 23 John Answer the survey sent via email if you haven't graded Link Link

Lectures

Note: The schedule is subject to change, but we will finish lectures before Thanksgiving.

Be aware that some of the scribe notes might be very old, and do not necessarily reflect exactly what happened in this year's class.
# Date Topic Notes Survey
1. Wed, Sep. 7: Course introduction. Persistent data structures. nb Survey
2. Fri, Sep. 9: Splay trees. nb Survey
3. Mon, Sep. 12: Integer Queues: Dial's Algorithm. Tries. nb Survey
4. Wed, Sep. 14: Integer Queues: Denardo and Fox, Van Emde Boas nb Survey
5. Fri, Sep. 16:
Universal Hashing. Perfect Hashing.
Streaming Model I: Distinct Elements Problem.
Survey1 Survey2
6. Mon, Sep. 19:
Streaming Model II: Heavy Hitters Problem
Dimensionality Reduction: Johnson-Lindenstrauss Lemma.
Survey1 Survey2
7. Wed, Sep. 21: Network Flows I: Flow Decomposition and Augmenting Paths. nb Survey
Fri, Sep. 23: NO CLASS (Student Holiday).
8. Mon, Sep. 26: Network Flows II: Basic Flow Algorithms and Capacity Scaling. nb Survey
9. Wed, Sep. 28: Network Flows III: Strongly Polynomial Time Max Flow Algorithms. nb Survey
10. Fri, Sep. 30: Network Flows IV: Blocking Flows. Survey
(o1) Mon, Oct 3: (OPTIONAL LECTURE) Spectral Graph Theory I: The Graph Laplacian and its Eigenvalues. nb Survey
11. Wed, Oct 5: Network Flows V: Min-Cost Flow and Cycle Cancelling Algorithm. Survey
12. Fri, Oct 7: Network Flows VI: Min-Cost Flow and Feasible Prices. Survey
Mon, Oct 10: NO CLASS (Columbus Day).
(o2) Wed, Oct 12: (OPTIONAL LECTURE) Spectral Graph Theory II: Random Walks and Laplacian Spectrum. nb Survey
13. Fri, Oct 14: Introduction to Linear Programming, Structure of Optima. nb Survey
14. Mon, Oct 17: Strong Duality, and Complementary Slackness. nb Survey
15. Wed, Oct 19: Simplex and Ellipsoid Method. Survey
16. Fri, Oct 21: Gradient Descent Method and its Applications. nb Survey
17. Mon, Oct 24: Interior-Point Methods. Survey
18. Wed, Oct 26: Introduction to Approximation Algorithms. Survey
19. Fri, Oct 28: Approximation Algorithms II: Approximation Schemes by Rounding and Enumeration nb Survey
20. Mon, Oct 31: Approximation Algorithms III: Relaxations. TSP, Scheduling, LP Relaxations Survey
21. Wed, Nov 2: Approximation Algorithms IV: Facility Location. Introduction to Online Algorithms (online lecture experiment). nb Survey1 Survey2
22. Fri, Nov 4: Online Algorithms II: Paging, Deterministic and Randomized Survey
23. Mon, Nov 7: Online Algorithms III: k-server. Introduction to External Memory Algorithms nb Survey
24. Wed, Nov 9: External Memory Algorithms Survey
Fri, Nov 11: NO CLASS (Veterans Day).
25. Mon, Nov 14: Computational Geometry I nb Survey
26. Wed, Nov 16: Computational Geometry II. Survey
27. Fri, Nov 18: Parallel Computations I. nb Survey
28. Mon, Nov 21: Parallel Computations II. Survey
(o3) Wed, Nov 23: (OPTIONAL LECTURE) Multiplicative Weight-Update Method, Zero-sum Games, LP Duality Survey
(o4) Mon, Nov 28: (OPTIONAL LECTURE) Fast (Laplacian) Linear System Solving nb Survey
(o5) Wed, Nov 30: (OPTIONAL LECTURE) Spectral graph theory III: Random Walks, Cuts, and Electrical Flows Survey
(o6) Fri, Dec 2: (OPTIONAL LECTURE) Word-level Parallelism: Sorting Integers in Linear Time Survey


References

Wed, Sep. 7
Fri, Sep. 9