6.854/18.415J: Advanced Algorithms (Fall 2016)
Lecture:

Monday, Wednesday, and Friday 2:304 in 32141. 


Units:

507 Graduate Hlevel


Instructors:

David Karger

karger at mit edu

Office hours: Arrange by email. In Building
32,
Room G592


Aleksander Mądry

madry at mit edu

Office hours: Arrange by email. In Building
32,
Room G666

TAs:

John Peebles 
jpeebles at mit.edu 


Tal Wagner 
talw at mit.edu


 Office hours:  Mondays, 4:30pm5:30pm, Room 36112 
  Fridays, 4:00pm5:00pm, Room 36144 
Course assistant:

Rebecca Yadegar

ryadegar at csail.mit.edu


Course Announcements
 Sep 22: A little note on why we need persistent data structures.
 Sep 19: Please fill out this quick poll about network flow/LP material.
 Sep 9: Please fill out this quick poll about hashing material.
 Sign up for the course here. You should do this as soon as possible to receive important course announcements.
 Sign up for an NB account here to get access to the problem sets and notes. NB is a system that allows you to annotate PDF files in a collaborative way. You are encouraged to post your questions about problem sets and notes before contacting the course staff as many others likely will have the same question. We will answer questions there on a regular basis.
 Use this Google spreadsheet to look for collaborators to work on the problem sets together. Remember that you should work with at most three other people for each problem set.
 The course info sheet.
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 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.
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
researchoriented. For more details, see the handout on
course information.
Problem Sets
 Homework is due Wednesdays at the beginning of class. We'll have
boxes or piles for dropping them off at the back of the room. Those boxes
will be collected a few minutes in, and homework arriving after will be
considered late.
 Each student has a total budget of 15 "slack" points to accommodate his/her late problem submissions. Each problem that is submitted late but in before Friday class will consume one slack point (and incur no grade penalty). If that problem is submitted in before Monday class, it will consume two slack points (and, again, incur no grade penalty). No late problem will be considered if submitted after the Monday class begins. (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.)
 Write each subproblem on a separate sheet of paper and include your name and email address. Also, make sure your name appears on each page.
 Collaboration is strongly encouraged except where
explicitly forbidden. However, each person must independently write
up his/her own solution, and you must list all collaborators for each
problem on your
problem set. Collaboration groups should be small (3 or 4 students)
to ensure that everyone is actively engaged with the problems.
 You may not seek out answers from other sources without
prior permission. In particular, you may not use bibles or posted
solutions to problems from previous years.
 Each student is required to grade (at least but hopefully) one problem
in the semester. We will have a TAsupervised grading session 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.
 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.
Problem Set 
Due Date 
Grading Supervisor 
Graders 
(Mandatory) Time Report 
(Optional) Difficulty/Usefulness Survey 
PS 1 
Fri, Sep. 16 
John 
sahasag@mit.edu 3(c); bristy@mit.edu 2; baxelrod@mit.edu 1; hongzi@mit.edu 5(c,d); ececca@mit.edu 5(a,b); Yilun Du 4; epayne@mit.edu 3(a,b) 
Link

Link 
PS 2 
Wed, Sep. 21 
Tal 
P1 nkb@mit.edu ; P2 zanger@mit.edu ; P3 umaroy@mit.edu ; P4 timngo@mit.edu ; P5 weiqiaoh@mit.edu ; P6 ztzhang@mit.edu 
Link

Link 
PS 3 
Wed, Sep. 28 
John 
Pset 3 grading signup is here 
Link

Link 
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 
Notes 


1. 
Wed, Sep. 7: 
Course introduction. Persistent data structures. 
nb 

2. 
Fri, Sep. 9: 
Splay trees. 
nb 

3. 
Mon, Sep. 12: 
Integer Queues: Dial's Algorithm. Tries. 
nb 

4. 
Wed, Sep. 14: 
Integer Queues: Denardo and Fox, Van Emde Boas 
nb 

5. 
Fri, Sep. 16: 
Universal Hashing. Perfect Hashing.
Streaming Model I: Distinct Elements Problem. 


6. 
Mon, Sep. 19: 
Streaming Model II: Heavy Hitters Problem
Dimensionality Reduction: JohnsonLindenstrauss Lemma. 



7. 
Wed, Sep. 21: 
Network Flows I: Flow Decomposition and Augmenting Paths. 
nb 



Fri, Sep. 23: 
NO CLASS (Student Holiday). 



8. 
Mon, Sep. 26: 
Network Flows II: Maximum Augmenting Path and Blocking Flow. 



9. 
Wed, Sep. 28: 
Network Flows III: Capacity Scaling and Min Cost Matching. 



10. 
Fri, Sep. 30: 
Introduction to Linear Programming, Structure of Optima. 



References
 Wed, Sep. 7


 Fri, Sep. 9
