• 6.5210/18.415: Advanced Algorithms
  • PSets
  • Calendar
  • Materials
  • Information
  • Course Information

    Lectures: Monday, Wednesday, and Friday 2:30-4 in 32-123

    Units: 5-0-7 Graduate H-level


    Role Name Email Office Hours
    Instructor David Karger karger@mit.edu Arrange by email.
    TA Theia Henderson theia@mit.edu M4-6 in 36-153, F4-5 in 36-144
    TA Michael Coulombe mcoulomb@mit.edu M7-9 in 36-153, F4-5 in 36-144


    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. 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.


    I hope that this class will confer


    The goal is to be broad rather than deep. This list is approximate.


    Strong performance in an undergraduate class in algorithms (e.g., 6.1220/18.410, previously 6.046), discrete mathematics and probability (6.1200/18.062, previously 6.042, is more than sufficient), and substantial mathematical maturity.


    Homework and Collaboration Policy.


    Homework is due Wednesdays on Gradescope at the beginning of class (2:35p).

    Because we are doing peer grading, you will need to add a separate Gradescope course for submission each week. Each week will have a Gradescope course code and there will be a single assignment to submit to in Gradescope for that week. Make sure to use a separate page for each (sub-)problem. Gradescope lets you associate each subproblem with the corresponding pages on your solution. Make sure not to skip this step. Your problem set will not be graded otherwise, and you will lose the corresponding points!

    After your submission has been graded, you can submit a regrade request directly in gradescope.

    Late Submissions

    Homework arriving after the deadline (Wednesday at 2:35pm) will be considered late. Late submission can directly be submitted to Gradescope as well.

    Each student has a total budget of 15 “slack” points to accommodate their late problem submissions.

    So, for example, if there is a problem set with a total of five problems on it, submitting three of these problems on time, one of them before Friday class, and one of them before Monday class will consume three slack points in total.

    In order for the late submission to be graded students are additionally required to fill out the late submission form. The link to the form can be found next to the problem set.


    Collaboration is encouraged, except where explicitly forbidden.

    Peer Grading

    Each student is required to grade (at least but hopefully) one problem in the semester.

    We will have a TA-supervised grading meeting each week. This session is used to make sure that the graders fully understand the solution, while they can grade the problems at home after this session.

    Please use the link next to the problem set, to sign up as grader for the corresponding problem set. Make sure to sign up before the pset due date as soon as possible because slots to grade a given pset can fill up. Peer graders need to finish grading their assigned problem by the Friday 9 days after the problem set is due. They are also responsible for grading late submissions and regrade requests. Note that no late submissions are allowed if you sign up as peer-grader.

    For questions about grading, please contact the graders (emails listed on the website) first. Once you reach an agreement, the grader should send an email to the grading supervisor with a short explanation and a new grade. All late psets should be sent electronically to the TA supervising the grading.


    There are no textbooks covering a majority of the material we will be studying. Lectures will often draw from the following (optional) texts, all of which are nice to have.