6.854/18.415J: Advanced Algorithms (Fall 2016)

Lecture:	Monday, Wednesday, and Friday 2:30-4 in 32-141.

Units:	5-0-7 Graduate H-level
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:30pm-5:30pm, Room 36-112
		Fridays, 4:00pm-5:00pm, Room 36-144
Course assistant:	Rebecca Yadegar	ryadegar at csail.mit.edu

Submit PSET 11 Here

Course Announcements

Nov 22You can find a list of of graded past projects here
Nov 20: Please fill this survey on topics for the optional lectures.
Nov 14: Use this spreadsheet to look for project collaborators.
Nov 09: Please read the course project description , and pay attention to Problem 6 on Pset 10.

Oct 5: Pset 5 is due Friday (10/14) since Wednesday is an optional lecture. Accordingly Monday's office hour is moved to Wednesday (10/12), 4pm at 32-G431.

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 research-oriented. 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 TA-supervised 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); yilundu@mit.edu 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	P1 sshader@mit.edu; P2 ycy@mit.edu; P3 jimmy42@mit.edu; P4 kaxiotis@mit.edu; P5 tianxiao@mit.edu; P6 ctunoku+6854@mit.edu	Link	Link
PS 4	Wed, Oct. 5	Tal	P1 dzaefn@mit.edu ; P2 keyulu@mit.edu ; P3 pahrens@mit.edu ; P4 luh@mit.edu ; P5 ronuchit@mit.edu	Link	Link
PS 5	Fri, Oct. 14	John	P1 hayks@mit.edu; P2 arsen@mit.edu; P3 alet+6854@mit.edu; P4 hujh@mit.edu; P5 bpchen@mit.edu	Link	Link
PS 6	Wed, Oct. 19	Tal	P1 abhijitm@mit.edu ; P2 kocabey@mit.edu ; P3 diomidov@mit.edu ; P4 akkas@mit.edu ; P5 jbpatel@mit.edu	Link	Link
PS 7	Wed, Oct. 26	John	P1 tclin@mit.edu; P2 calvin3@mit.edu ; P3 karren@mit.edu ; P4 yangk@mit.edu ; P5 aradhana@mit.edu	Link	Link
PS 8	Wed, Nov. 2	John	P1 davidbau@mit.edu; P2 amakelov@mit.edu; P3 jeetmo@mit.edu; P4 trattner@mit.edu	Link	Link
PS 9	Wed, Nov. 11	Tal	P1 kelswong@mit.edu ; P2 trattner@mit.edu ; P3 bando@mit.edu ; P4 badea@mit.edu ; P5 schiefer@mit.edu	Link	Link
PS 10	Wed, Nov. 11	Tal	P1 bmhuang@mit.edu ; P2 ashwath@mit.edu ; P3 jayzee@mit.edu ; P4 alexjl@mit.edu ; P5 shahp@mit.edu	Link	Link
PS 11	Wed, Nov. 23	John	Answer the survey sent via email if you haven't graded	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 Survey

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

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

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

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

5. Fri, Sep. 16:
Universal Hashing. Perfect Hashing.

Streaming Model I: Distinct Elements Problem.

nb

nb
Survey1 Survey2

6. Mon, Sep. 19:
Streaming Model II: Heavy Hitters Problem

Dimensionality Reduction: Johnson-Lindenstrauss Lemma.

nb

nb
Survey1 Survey2

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

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

8. Mon, Sep. 26: Network Flows II: Basic Flow Algorithms and Capacity Scaling. nb Survey

9. Wed, Sep. 28: Network Flows III: Strongly Polynomial Time Max Flow Algorithms. nb Survey

10. Fri, Sep. 30: Network Flows IV: Blocking Flows.
nb

nb
Survey

(o1) Mon, Oct 3: (OPTIONAL LECTURE) Spectral Graph Theory I: The Graph Laplacian and its Eigenvalues. nb Survey

11. Wed, Oct 5: Network Flows V: Min-Cost Flow and Cycle Cancelling Algorithm. Survey

12. Fri, Oct 7: Network Flows VI: Min-Cost Flow and Feasible Prices. Survey

Mon, Oct 10: NO CLASS (Columbus Day).

(o2) Wed, Oct 12: (OPTIONAL LECTURE) Spectral Graph Theory II: Random Walks and Laplacian Spectrum. nb Survey

13. Fri, Oct 14: Introduction to Linear Programming, Structure of Optima. nb Survey
14. Mon, Oct 17: Strong Duality, and Complementary Slackness. nb Survey

15. Wed, Oct 19: Simplex and Ellipsoid Method. Survey

16. Fri, Oct 21: Gradient Descent Method and its Applications. nb Survey

17. Mon, Oct 24: Interior-Point Methods. Survey

18. Wed, Oct 26: Introduction to Approximation Algorithms. Survey

19. Fri, Oct 28: Approximation Algorithms II: Approximation Schemes by Rounding and Enumeration nb Survey

20. Mon, Oct 31: Approximation Algorithms III: Relaxations. TSP, Scheduling, LP Relaxations Survey

21. Wed, Nov 2: Approximation Algorithms IV: Facility Location. Introduction to Online Algorithms (online lecture experiment). nb Survey1 Survey2

22. Fri, Nov 4: Online Algorithms II: Paging, Deterministic and Randomized Survey

23. Mon, Nov 7: Online Algorithms III: k-server. Introduction to External Memory Algorithms nb Survey

24. Wed, Nov 9: External Memory Algorithms Survey

Fri, Nov 11: NO CLASS (Veterans Day).

25. Mon, Nov 14: Computational Geometry I nb Survey

26. Wed, Nov 16: Computational Geometry II. Survey

27. Fri, Nov 18: Parallel Computations I. nb Survey

28. Mon, Nov 21: Parallel Computations II. Survey

(o3) Wed, Nov 23: (OPTIONAL LECTURE) Multiplicative Weight-Update Method, Zero-sum Games, LP Duality Survey

(o4) Mon, Nov 28: (OPTIONAL LECTURE) Fast (Laplacian) Linear System Solving nb Survey

(o5) Wed, Nov 30: (OPTIONAL LECTURE) Spectral graph theory III: Random Walks, Cuts, and Electrical Flows Survey

(o6) Fri, Dec 2: (OPTIONAL LECTURE) Word-level Parallelism: Sorting Integers in Linear Time Survey

(o7) Mon, Dec 5: (OPTIONAL LECTURE) Computing Maximum Flows with Electrical Flows nb nb nb Survey

#	Date	Topic	Notes	Survey
1.	Wed, Sep. 7:	Course introduction. Persistent data structures.	nb	Survey
2.	Fri, Sep. 9:	Splay trees.	nb	Survey
3.	Mon, Sep. 12:	Integer Queues: Dial's Algorithm. Tries.	nb	Survey
4.	Wed, Sep. 14:	Integer Queues: Denardo and Fox, Van Emde Boas	nb	Survey
5.	Fri, Sep. 16:	Universal Hashing. Perfect Hashing. Streaming Model I: Distinct Elements Problem.	nb nb	Survey1 Survey2
6.	Mon, Sep. 19:	Streaming Model II: Heavy Hitters Problem Dimensionality Reduction: Johnson-Lindenstrauss Lemma.	nb nb	Survey1 Survey2
7.	Wed, Sep. 21:	Network Flows I: Flow Decomposition and Augmenting Paths.	nb	Survey
	Fri, Sep. 23:	NO CLASS (Student Holiday).
8.	Mon, Sep. 26:	Network Flows II: Basic Flow Algorithms and Capacity Scaling.	nb	Survey
9.	Wed, Sep. 28:	Network Flows III: Strongly Polynomial Time Max Flow Algorithms.	nb	Survey
10.	Fri, Sep. 30:	Network Flows IV: Blocking Flows.	nb nb	Survey
(o1)	Mon, Oct 3:	(OPTIONAL LECTURE) Spectral Graph Theory I: The Graph Laplacian and its Eigenvalues.	nb	Survey
11.	Wed, Oct 5:	Network Flows V: Min-Cost Flow and Cycle Cancelling Algorithm.		Survey
12.	Fri, Oct 7:	Network Flows VI: Min-Cost Flow and Feasible Prices.		Survey
	Mon, Oct 10:	NO CLASS (Columbus Day).
(o2)	Wed, Oct 12:	(OPTIONAL LECTURE) Spectral Graph Theory II: Random Walks and Laplacian Spectrum.	nb	Survey
13.	Fri, Oct 14:	Introduction to Linear Programming, Structure of Optima.	nb	Survey
14.	Mon, Oct 17:	Strong Duality, and Complementary Slackness.	nb	Survey
15.	Wed, Oct 19:	Simplex and Ellipsoid Method.		Survey
16.	Fri, Oct 21:	Gradient Descent Method and its Applications.	nb	Survey
17.	Mon, Oct 24:	Interior-Point Methods.		Survey
18.	Wed, Oct 26:	Introduction to Approximation Algorithms.		Survey
19.	Fri, Oct 28:	Approximation Algorithms II: Approximation Schemes by Rounding and Enumeration	nb	Survey
20.	Mon, Oct 31:	Approximation Algorithms III: Relaxations. TSP, Scheduling, LP Relaxations		Survey
21.	Wed, Nov 2:	Approximation Algorithms IV: Facility Location. Introduction to Online Algorithms (online lecture experiment).	nb	Survey1 Survey2
22.	Fri, Nov 4:	Online Algorithms II: Paging, Deterministic and Randomized		Survey
23.	Mon, Nov 7:	Online Algorithms III: k-server. Introduction to External Memory Algorithms	nb	Survey
24.	Wed, Nov 9:	External Memory Algorithms		Survey
	Fri, Nov 11:	NO CLASS (Veterans Day).
25.	Mon, Nov 14:	Computational Geometry I	nb	Survey
26.	Wed, Nov 16:	Computational Geometry II.		Survey
27.	Fri, Nov 18:	Parallel Computations I.	nb	Survey
28.	Mon, Nov 21:	Parallel Computations II.		Survey
(o3)	Wed, Nov 23:	(OPTIONAL LECTURE) Multiplicative Weight-Update Method, Zero-sum Games, LP Duality		Survey
(o4)	Mon, Nov 28:	(OPTIONAL LECTURE) Fast (Laplacian) Linear System Solving	nb	Survey
(o5)	Wed, Nov 30:	(OPTIONAL LECTURE) Spectral graph theory III: Random Walks, Cuts, and Electrical Flows		Survey
(o6)	Fri, Dec 2:	(OPTIONAL LECTURE) Word-level Parallelism: Sorting Integers in Linear Time		Survey
(o7)	Mon, Dec 5:	(OPTIONAL LECTURE) Computing Maximum Flows with Electrical Flows	nb nb nb	Survey

References

Wed, Sep. 7

N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Commun. ACM, 29:669-679, 1986.

Driscoll, N. Sarnak and R. E. Tarjan. Making Data Structures Persistent Journal of Computer and System Sciences 38(1):86-124, 1989

Fri, Sep. 9

D. D. Sleator and R. E. Tarjan 1985. Self-adjusting binary search trees. J. ACM 32, 3 (Jul. 1985), 652-686.