6.854/18.415J: Advanced Algorithms (Fall 2019)

Lecture: Monday, Wednesday, and Friday 2:30-4 in 32-123.
Units: 5-0-7 Graduate H-level
Instructors: David Karger karger@mit.edu Office hours: Arrange by email. In Building 32, Room G592
Aleksander Mądry madry@mit.edu Office hours: Arrange by email. In Building 32, Room G666
TAs: Cenk Baykal baykal@mit.edu
  Josh Brunner brunnerj@mit.edu
  Sam Park sp765@mit.edu
Office hours: Monday and Friday 4-5pm in 36-156 (Mon) and 36-112 (Fri)
Course assistant: Rebecca Yadegar ryadegar at csail.mit.edu

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 programming, 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

Submission

Due Date and Late Submission

Policy

Peer Grading

Problem Set Due Date Solutions Grading Supervisor Submission (Mandatory) Time Report Peer Grading Sign-up Late Submission
PS1 Wed, Sep. 11 PS1 Sol Sam PS1 Submission PS1 Time Survey PS1 Peer Grading PS1 Late Form
PS 2 Wed, Sep. 18 PS2 Sol Cenk PS2 Submission PS2 Time Survey PS2 Peer Grading PS2 Late Form
PS 3 Wed, Sep. 25 PS3 Sol Josh PS3 Submission PS3 Time Survey PS3 Peer Grading PS3 Late Form
PS 4 Wed, Oct. 2 PS4 Sol Sam PS4 Submission PS4 Time Survey PS4 Peer Grading PS4 Late Form
PS 5 Wed, Oct. 9 PS5 Sol Cenk PS5 Submission PS5 Time Survey PS5 Peer Grading PS5 Late Form
PS 6 Wed, Oct. 16 PS6 Sol Josh PS6 Submission PS6 Time Survey PS6 Peer Grading PS6 Late Form
PS 7 Wed, Oct. 23 PS7 Sol Sam PS7 Submission PS7 Time Survey PS7 Peer Grading PS7 Late Form
PS 8 Wed, Oct. 30 PS8 Sol Cenk PS8 Submission PS8 Time Survey PS8 Peer Grading PS8 Late Form
PS 9 Wed, Nov. 6   Josh PS9 Submission PS9 Time Survey PS9 Peer Grading PS9 Late Form
PS 10 Wed, Nov. 13   Sam PS10 Submission PS10 Time Survey PS10 Peer Grading PS10 Late Form
PS 11 Wed, Nov. 20   Cenk PS11 Submission PS11 Time Survey PS11 Peer Grading PS11 Late Form

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 Raw Notes Scribe
1. Wed, Sep. 4: Course introduction. Fibonacci heaps. MST. nb nb
2. Fri, Sep. 6: Persistent Data Structures. nb nb
3. Mon, Sep. 9: Splay trees. nb nb
4. Wed, Sep. 11: More Splay trees. nb nb
5. Fri, Sep. 13: Hashing. Universal Hashing. Perfect Hashing nb nb
6. Mon, Sep. 16: Network Flows: Characterization. Decomposition. Augmenting Paths. nb nb
7. Wed, Sep. 18: Network Flows: Maximum augmenting path. Capacity Scaling. nb nb
Network Flows: Strongly polynomial algorithms. nb
Fri, Sep. 20: (No class, student holiday)
8. Mon, Sep. 23: Min-Cost Flows: Feasible prices. nb nb
9. Wed, Sep. 25: Finish Min-Cost Flows. nb
10. Fri, Sep. 27: Introduction to Linear Programming. nb nb
11. Mon, Sep. 30: Linear Programming: Structure of Optima. Strong Duality. nb nb
12. Wed, Oct. 2: Linear Programming: Duality Applications. nb nb
13. Fri, Oct. 4: Linear Programming: Simplex Method. nb
14. Mon, Oct. 7: Linear Programming: Ellipsoid Method. Intro to Gradient Descent Method. nb
15. Wed, Oct. 9: Gradient Descent Method: Convexity, smoothness, strong convexity, convergence. nb
16. Fri, Oct. 11: Newton's Method. Generalized Gradient Descent. Linear System Solving. nb
Mon, Oct. 14: (No class, student holiday)
17. Wed, Oct. 16: Interior Point Method. nb
18. Fri, Oct. 18: Max flow via Gradient Descent. nb
19. Mon, Oct. 21: Max flow via GD (continued). Electrical flows. Linear system solving.
20. Wed, Oct. 23:
21. Fri, Oct. 25: Introduction to Approximation Algorithms. nb nb
22. Mon, Oct. 28: Approximation Algorithms: Greedy approaches. Enumeration and FPRAS (scheduling) nb
23. Wed, Oct. 30: Approximation Algorithms: Rounding LP solutions (Vertex Cover, Facility Location).
24. Fri, Nov. 1: Approximation Algorithms: MAX-SAT, parameterized complexity nb
24. Mon, Nov. 4: Computational Geometry I. nb nb
25. Wed, Nov. 6: Computational Geometry II. nb
26. Fri, Nov. 8: Online Algorithms: Ski Rental, Paging. nb nb
Below is last year's schedule:
24. Wed, Nov. 14: Online Algorithms: Ski Rental, Paging. nb nb
25. Fri, Nov. 16: Online Algorithms: Adversaries, Randomization, k-server.
26. Mon, Nov. 19: Computational Geometry I. nb nb
Wed, Nov. 21: (No class)
Fri, Nov. 23: (No class)
27. Mon, Nov. 26: Computational Geometry II. nb