6.854/18.415J: Advanced Algorithms (Fall 2020)

Lecture: Monday, Wednesday, and Friday 2:30-4 (Online lectures)
Units: 5-0-7 Graduate H-level
Instructors: David Karger karger@mit.edu Office hours: Arrange by email. In Building 32, Room G592
TAs: Josh Brunner brunnerj@mit.edu
 Christian Altamirano bdiehs@mit.edu
 Thiago Bergamaschi thiagob@mit.edu
Office hours: Monday 5:30-6:30pm and Friday 4-5pm online
Course assistant: Rebecca Yadegar ryadegar@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 Gradescope code (Mandatory) Time Report Peer Grading Sign-up Late Submission
PS1 Wed, Sep. 9 PS1 Sol Josh MY4B55 PS1 Time Survey PS1 Peer Grading PS1 Late Form
PS2 Wed, Sep. 16 PS2 Sol Thiago MPV7N7 PS2 Time Survey PS2 Peer Grading PS2 Late Form
PS3 Wed, Sep. 23 PS3 Sol Christian 95YNW7 PS3 Time Survey PS3 Peer Grading PS3 Late Form
PS4 Wed, Sep. 30 PS4 Sol Josh ME3N7E PS4 Time Survey PS4 Peer Grading PS4 Late Form
PS5 Wed, Oct. 7 PS5 Sol Christian KY53DB PS5 Time Survey PS5 Peer Grading PS5 Late Form
PS6 Wed, Oct. 14 PS6 Sol Josh KY586R PS6 Time Survey PS6 Peer Grading PS6 Late Form
PS7 Wed, Oct. 21 PS7 Sol Christian X3Y4DX PS7 Time Survey PS7 Peer Grading PS7 Late Form
PS8 Wed, Oct. 28 PS8 Sol Thiago KY52ZG PS8 Time Survey PS8 Peer Grading PS8 Late Form
PS9 Wed, Nov. 4 PS9 Sol Josh JBB3V7 PS9 Time Survey PS9 Peer Grading PS9 Late Form
PS10 Thu, Nov. 12 Christian JBB48K PS10 Time Survey PS10 Peer Grading PS10 Late Form
PS11 Wed, Nov. 18 Josh N884Y5 PS11 Time Survey PS11 Peer Grading PS11 Late Form
PS12 Wed, Dec. 2 Christian JBBJY4 PS12 Time Survey PS12 Peer Grading PS12 Late Form

Lectures

Warning: This is last year's schedule, and will be changing. 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 Video
1. Wed, Sep. 2: Course introduction. Fibonacci heaps. MST. nb and nb nb video
2. Fri, Sep. 4: Fibonacci heaps. MST. Persistent Data Structures Intro. nb nb video
3. Wed, Sep. 9: Persistent Data Structures. Splay trees intro. nb nb video
4. Fri, Sep. 11: Splay trees. nb nb video
5. Mon, Sep. 14: Dial's Algorithm. Tries. Multi-level buckets. nb nb video
6. Wed, Sep. 16: van Emde Boas Queues and Hashing nb nb video
7. Fri, Sep. 18: Universal Hashing. Perfect Hashing. Begin Network Flows. video
8. Mon, Sep. 21: Network Flows: Charaterization. Augmenting Paths. Max Flow Min Cut Theorem. nb nb video
9. Wed, Sep. 23: Network Flows: Maximum augmenting path. Capacity Scaling. nb nb video
10. Fri, Sep. 25: Network Flows: Strongly polynomial algorithms. Blocking Flows. nb nb video
11. Mon, Sep. 28: Min-Cost Flows: Feasible prices. nb nb video
12. Wed, Sep. 30: Min-Cost Flows nb video
13. Fri, Oct. 2: Finish Min-Cost Flows and Introduction to Linear Programming. video
14. Mon, Oct. 5: Linear Programming: Structure of Optima. nb nb video
15. Wed, Oct. 7: Linear Programming: Strong Duality. nb nb video
16. Fri, Oct. 9: Linear Programming: Strong Duality and Duality Applications. nb nb video
17. Tue, Oct. 13: Linear Programming: Duality Applications. nb nb video
18. Wed, Oct. 14: Linear Programming: Simplex Method. nb video
19. Fri, Oct. 16: Linear Programming: Ellipsoid Method. nb video
20. Mon, Oct. 19: Introduction to Approximation Algorithms. nb nb video
21. Wed, Oct. 21: Approximation Algorithms: Greedy approaches. Enumeration and FPAS (scheduling) nb video
22. Fri, Oct. 23: Approximation Algorithms: Enumeration, Rounding, Metric TSP. video
23. Mon, Oct. 26: Approximation Algorithms: Relaxations video
24. Wed, Oct. 28: Approximation Algorithms: Randomized Rounding nb video
25. Fri, Oct. 30: Computational Geometry I. nb nb video
26. Mon, Nov. 2: Computational Geometry II: Voronoi Diagrams nb video
27. Wed, Nov. 4: Online Algorithms: Ski Rental, Paging. nb nb video
28. Fri, Nov. 6: Online Algorithms: Paging, Adversaries, Randomization nb nb video
29. Mon, Nov. 9: Online Algorithms: Adversaries, Randomization, k-server. video
30. Fri, Nov. 13: The k-server problem and External Memory Algorithms. video
31. Mon, Nov. 16: External Memory Algorithms. nb video
32. Wed, Nov. 18: Parallel Algorithms. nb video
33. Fri, Nov. 20: Parallel Algorithms. nb video
Below this point is last year's schedule.