6.854/18.415J: Advanced Algorithms (Fall 2018)

Lecture: Monday, Wednesday, and Friday 2:30-4 in 2-190.
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: Kyriakos Axiotis kaxiotis@mit.edu
  Brynmor Chapman brynmor@mit.edu
  Aleksandar Makelov amakelov@mit.edu
  Sandeep Silwal silwal@mit.edu
Office hours: Monday and Friday 4-5pm in 2-135
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

Problem Set Due Date Solutions Grading Supervisor Graders (Mandatory) Time Report (Optional) Difficulty/Usefulness Survey
PS 1 Wed, Sep. 12 Sol. 1 Sandeep P2 xygong@mit.edu, tslilyai@mit.edu
P3 rkavya@mit.edu, gilkur@mit.edu
P4 chenxing@mit.edu, jisoomin@mit.edu
P5 yyao1@mit.edu, mihirs@mit.edu
Link Link
PS 2 Wed, Sep. 19 Sol. 2 Brynmor Sign up Link Link
PS 2 Wed, Sep. 26 Sol. 3

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. 5: Course introduction. Fibonacci heaps. MST. nb nb
2. Fri, Sep. 7: Persistent Data Structures. nb nb
Mon, Sep. 10: (Optional lecture) Spectral Graph Theory I nb
3. Wed, Sep. 12: Splay trees. nb nb
4. Fri, Sep. 14: Dial's Algorithm. Tries. Multi-level buckets. Van Emde Boas queues nb nb
5. Mon, Sep. 17: Hashing. Universal Hashing. Perfect Hashing nb nb
Wed, Sep. 19: (Optional lecture) Spectral Graph Theory II