6.854/18.415J: Advanced Algorithms (Fall 2021)

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
TAs: Angelos Pelecanos apelecan@mit.edu Office hours: Monday and Friday 4-6 in Building 36, Room 36-153 and virtually.
Theia Henderson theia@mit.edu
William Kuszmaul kuszmaul@mit.edu
Course assistant: Rebecca Yadegar ryadegar@csail.mit.edu

Announcements

  1. The final project is due on on the last day of classes, Wednesday, December 9 at midnight.
  2. We will have a required in-class peer editing session on Monday, December 6.

Past Announcements

  1. If you intend to take this course please fill out this survey. Note that this form does NOT replace official registration via MIT Registrar's office, it's for our own internal bookkeeping.
  2. We will be using NB, a tool that permits students to discuss and ask questions about lecture videos, notes, and problems sets. For feature reasons we will be using one version of the tool to view and discuss videos and another to view and discuss notes and problems sets. You should sign up for NBv1 at this link. You will get a separate invite for NBv2.
  3. We've added this class to psetpartners, which you can use to find collaborators and comply with the collaboration policy which limits the number of psets you can work on with any individual collaborator.
  4. Homework 2 is due on Wednesday 9/22. Don't forget that you can use NB to publicly (or privately to the staff) annotate the problem set with questions and clarifications! Just drag a rectangle around what you want to talk about.
  5. You can now find the course materials for the first half of this course, including all notes and videos, here. These materials should serve to supplement the in-person lectures but not replace them. We've done our best to synchronize everything but there are inevitable inconsistencies between historic lectures and this year's.
  6. The project handout is here.
  7. The project collaborator search spreadsheet is here.

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

Problem Set Due Date Solutions Grading Supervisor Gradescope (Mandatory) Time Report Peer Grading Sign-up Late Submission
PS1 Wed, Sep. 15 PS1 Solutions V8X428 PS1 Survey PS1 Grading PS1 Late
PS2 Wed, Sep. 22 PS2 Solutions N8N6DB PS2 Survey PS2 Grading PS2 Late
PS3 Wed, Sep. 29 PS3 Solutions 2RWD6Z PS3 Survey PS3 Grading PS3 Late
PS4 Wed, Oct. 6 PS4 Solutions 86W8Z5 PS4 Survey PS4 Grading PS4 Late
PS5 Wed, Oct. 13 PS5 Solutions P5J7W4 PS5 Survey PS5 Grading PS5 Late
PS6 Wed, Oct. 20 PS6 Solutions RW47W6 PS6 Survey PS6 Grading PS6 Late
PS7 Wed, Oct. 27 PS7 Solutions 8684BJ PS7 Survey PS7 Grading PS7 Late
PS8 Wed, Nov. 3 PS8 Solutions BP7DXX PS8 Survey PS8 Grading PS8 Late
PS9 Wed, Nov. 10 4P7E83 PS9 Survey PS9 Grading PS9 Late
PS10 Wed, Nov. 17 2RVNWP PS10 Survey PS10 Grading PS10 Late
PS11 Wed, Nov. 24 N873NK PS11 Survey PS11 Grading PS11 Late

Submission

Due Date and Late Submission

Collaboration Policy

Peer Grading

Lectures

For notes and videos related to each topic, see the course materials.

All lectures will be done before Thanksgiving
# Date Topic
1. Wed, Sep. 8: Course introduction. Fibonacci heaps. MST.
2. Fri, Sep. 10: Fibonacci heaps.
3. Mon, Sep. 13: Fibonacci heaps. MST. Persistent Data Structures.
4. Wed, Sep. 15: Persistent Data Structures. Splay Trees.
5. Fri, Sep. 17: Splay Trees.
6. Mon, Sep. 20: Buckets.
7. Wed, Sep. 22: Van Emde Boas Queues. Universal Hashing. Pre-recorded lectures: this from 15:00 and this till 28:00.
8. Fri, Sep. 24: Perfect Hashing. Max Flow: Flow Decomposition. S-T Cuts.
9. Mon, Sep. 27: Max Flow: Max-Flow Min-Cut. Augmenting Path Algorithms.
10. Wed, Sep. 29: Max Flow: Scaling. Strongly polynomial algorithms. Blocking Flows. Pre-recorded lectures: this from 37:30 and this till 43:00.
11. Fri, Oct. 1: Blocking Flows. State-of-the-Art Max Flow Results.
12. Mon, Oct. 4: Min Cost Flows
13. Wed, Oct. 6: Min Cost Flow Algorithms
14. Fri, Oct. 8: Linear Programming: Introduction. Size of Solutions. Pre-recorded lectures: this from 54:20 and this till 47:20.
Mon, Oct. 11: Indigenous Peoples Day - No class
15. Wed, Oct. 13: Linear Programming: Geometry. Structure of Optima. Duality Introduction.
16. Fri, Oct. 15: Linear Programming: Strong Duality.
17. Mon, Oct. 18: Linear Programming: Rules for Taking Duals. Duality Examples. Complementary Slackness.
18. Wed, Oct. 20: Linear Programming: Min-Cost Circulation Dual. Simplex Method.
19. Fri, Oct. 22: Linear Programming: Simplex Method. Ellipsoid Method.
20. Mon, Oct. 25: Linear Programming: Interior Point Method. Approximation Algorithms: Introduction.
21. Wed, Oct. 27: Approximation Algorithms: Greedy approaches. Scheduling. Approximation Schemes (PAS).
22. Fri, Oct. 29: Approximation Algorithms: Fully Polynomial Time Approximation Schemes (FPAS). Rounding. Enumeration.
23. Mon, Nov. 1: Approximation Algorithms: Relaxations. TSP. LP Relaxations.
24. Wed, Nov. 3: Approximation Algorithms: LP Relaxations. Facility Location. Approximation-Preserving Reductions.
25. Fri, Nov. 5: Approximation Algorithms: Randomized Rounding. Fixed Parameter Tractability.
26. Mon, Nov. 8: Treewidth. Computational Geometry: Range Trees. Sweep Algorithms.
27. Wed, Nov. 10: Computational Geometry: Voronoi Diagrams.
28. Fri, Nov. 12: Online Algorithms: Ski Rental. Finance.
29. Mon, Nov. 15: Online Algorithms: Load Balancing. Paging. Randomization.
30. Wed, Nov. 17: Online Algorithms: Paging. Randomization. K-Server Problem.
31. Fri, Nov. 19: Online Algorithms: K-Server Problem. External Memory Algorithms: Matrices. Linked Lists. Search Trees.
32. Mon, Nov. 22: External Memory Algorithms: Sorting. Buffer Trees. Cache Oblivious Algorithms.
33. Wed, Nov. 24: Thanksgiving holiday - No class
Fri, Nov. 26 Thanksgiving holiday - No class
Accessibility