6.854/18.415J: Advanced Algorithms (Fall 2019)

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
	Aleksander Mądry	madry@mit.edu	Office hours: Arrange by email. In Building 32, Room G666
TAs:	Cenk Baykal	baykal@mit.edu
	Josh Brunner	brunnerj@mit.edu
	Sam Park	sp765@mit.edu
	Office hours:	Monday and Friday 4-5pm in 36-156 (Mon) and 36-112 (Fri)
Course assistant:	Rebecca Yadegar	ryadegar at csail.mit.edu

Course Announcements

Final project is due Dec 10th (Wed) at midnight. Submission instructions will be announced via email.
Course project information is up.
Use this Google spreadsheet to look for collaborators for the project. Project groups should be no larger than 3 people.

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

Submission

We will use gradescope to electronically collect and grade homeworks.
You will receive a registration link from gradescope to create an account.
Once you have an account you can simply use the link next to the problem set to submit your solution.
Make sure to use a seperate 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.

Due Date and Late Submission

Problem sets are due Wednesdays at the beginning of class (2.30pm).
Each student has a total budget of 15 "slack" points to accommodate his/her late problem submissions. Each problem (not pset) 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.)
You are responsible for keeping track of your own slack points.
Late submission can directly be submitted to gradescope as well.
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.

Policy

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.

Peer Grading

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.
Please use the link next to the problem set, to sign up as grader for the corresponding problem set.
Note that no late submissions are allowed if you sign up as peer-grader.

Problem Set	Due Date	Solutions	Grading Supervisor	Submission	(Mandatory) Time Report	Peer Grading Sign-up	Late Submission
PS1	Wed, Sep. 11	PS1 Sol	Sam	PS1 Submission	PS1 Time Survey	PS1 Peer Grading	PS1 Late Form
PS 2	Wed, Sep. 18	PS2 Sol	Cenk	PS2 Submission	PS2 Time Survey	PS2 Peer Grading	PS2 Late Form
PS 3	Wed, Sep. 25	PS3 Sol	Josh	PS3 Submission	PS3 Time Survey	PS3 Peer Grading	PS3 Late Form
PS 4	Wed, Oct. 2	PS4 Sol	Sam	PS4 Submission	PS4 Time Survey	PS4 Peer Grading	PS4 Late Form
PS 5	Wed, Oct. 9	PS5 Sol	Cenk	PS5 Submission	PS5 Time Survey	PS5 Peer Grading	PS5 Late Form
PS 6	Wed, Oct. 16	PS6 Sol	Josh	PS6 Submission	PS6 Time Survey	PS6 Peer Grading	PS6 Late Form
PS 7	Wed, Oct. 23	PS7 Sol	Sam	PS7 Submission	PS7 Time Survey	PS7 Peer Grading	PS7 Late Form
PS 8	Wed, Oct. 30	PS8 Sol	Cenk	PS8 Submission	PS8 Time Survey	PS8 Peer Grading	PS8 Late Form
PS 9	Wed, Nov. 6	PS9 Sol	Josh	PS9 Submission	PS9 Time Survey	PS9 Peer Grading	PS9 Late Form
PS 10	Wed, Nov. 13	PS10 Sol	Sam	PS10 Submission	PS10 Time Survey	PS10 Peer Grading	PS10 Late Form
PS 11	Wed, Nov. 20	PS11 Sol	Cenk	PS11 Submission	PS11 Time Survey	PS11 Peer Grading	PS11 Late Form
PS 12	Wed, Nov. 27	PS12 Sol	Josh	PS12 Submission	PS12 Time Survey		PS12 Late Form

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. 4: Course introduction. Fibonacci heaps. MST. nb nb

2. Fri, Sep. 6: Persistent Data Structures. nb nb

3. Mon, Sep. 9: Splay trees. nb nb

4. Wed, Sep. 11: More Splay trees. nb nb

5. Fri, Sep. 13: Hashing. Universal Hashing. Perfect Hashing nb nb

6. Mon, Sep. 16: Network Flows: Characterization. Decomposition. Augmenting Paths. nb nb

7. Wed, Sep. 18: Network Flows: Maximum augmenting path. Capacity Scaling. nb nb

Network Flows: Strongly polynomial algorithms. nb

Fri, Sep. 20: (No class, student holiday)

8. Mon, Sep. 23: Min-Cost Flows: Feasible prices. nb nb

9. Wed, Sep. 25: Finish Min-Cost Flows. nb

10. Fri, Sep. 27: Introduction to Linear Programming. nb nb

11. Mon, Sep. 30: Linear Programming: Structure of Optima. Strong Duality. nb nb

12. Wed, Oct. 2: Linear Programming: Duality Applications. nb nb

13. Fri, Oct. 4: Linear Programming: Simplex Method. nb

14. Mon, Oct. 7: Linear Programming: Ellipsoid Method. Intro to Gradient Descent Method. nb

15. Wed, Oct. 9: Gradient Descent Method: Convexity, smoothness, strong convexity, convergence. nb

16. Fri, Oct. 11: Newton's Method. Generalized Gradient Descent. Linear System Solving. nb

Mon, Oct. 14: (No class, student holiday)

17. Wed, Oct. 16: Interior Point Method. nb

18. Fri, Oct. 18: Max flow via Gradient Descent. nb

19. Mon, Oct. 21: Max flow via GD (continued). Electrical flows. Linear system solving.

20. Wed, Oct. 23: Max flow via GD (continued). Electrical flows. Linear system solving.

21. Fri, Oct. 25: Introduction to Approximation Algorithms. nb nb

22. Mon, Oct. 28: Approximation Algorithms: Greedy approaches. Enumeration and FPRAS (scheduling) nb

23. Wed, Oct. 30: Approximation Algorithms: Rounding LP solutions (Vertex Cover, Facility Location).

24. Fri, Nov. 1: Approximation Algorithms: MAX-SAT, parameterized complexity nb

24. Mon, Nov. 4: Computational Geometry I. nb nb

25. Wed, Nov. 6: Computational Geometry II. nb

26. Fri, Nov. 8: Online Algorithms: Ski Rental, Paging. nb nb

27. Mon, Nov. 11: (No class)

28. Wed, Nov. 13: Online Algorithms: Adversaries, Randomization, k-server.

29. Fri, Nov. 15: Online Algorithms: Adversaries, Randomization, k-server.

29. Mon, Nov. 18: Parallel algorithms-circuits. nb

30. Wed, Nov. 20: Parallel algorithms-PRAMs. nb

31. Fri, Nov. 22: External memory algorithms. nb

32. Mon, Nov. 25: Streaming algorithms. nb

Mon, Dec. 2: [Optional] Random walks. pdf

#	Date	Topic	Raw Notes	Scribe
1.	Wed, Sep. 4:	Course introduction. Fibonacci heaps. MST.	nb	nb
2.	Fri, Sep. 6:	Persistent Data Structures.	nb	nb
3.	Mon, Sep. 9:	Splay trees.	nb	nb
4.	Wed, Sep. 11:	More Splay trees.	nb	nb
5.	Fri, Sep. 13:	Hashing. Universal Hashing. Perfect Hashing	nb	nb
6.	Mon, Sep. 16:	Network Flows: Characterization. Decomposition. Augmenting Paths.	nb	nb
7.	Wed, Sep. 18:	Network Flows: Maximum augmenting path. Capacity Scaling.	nb	nb
		Network Flows: Strongly polynomial algorithms.	nb
	Fri, Sep. 20:	(No class, student holiday)
8.	Mon, Sep. 23:	Min-Cost Flows: Feasible prices.	nb	nb
9.	Wed, Sep. 25:	Finish Min-Cost Flows.		nb
10.	Fri, Sep. 27:	Introduction to Linear Programming.	nb	nb
11.	Mon, Sep. 30:	Linear Programming: Structure of Optima. Strong Duality.	nb	nb
12.	Wed, Oct. 2:	Linear Programming: Duality Applications.	nb	nb
13.	Fri, Oct. 4:	Linear Programming: Simplex Method.	nb
14.	Mon, Oct. 7:	Linear Programming: Ellipsoid Method. Intro to Gradient Descent Method.	nb
15.	Wed, Oct. 9:	Gradient Descent Method: Convexity, smoothness, strong convexity, convergence.	nb
16.	Fri, Oct. 11:	Newton's Method. Generalized Gradient Descent. Linear System Solving.	nb
	Mon, Oct. 14:	(No class, student holiday)
17.	Wed, Oct. 16:	Interior Point Method.	nb
18.	Fri, Oct. 18:	Max flow via Gradient Descent.	nb
19.	Mon, Oct. 21:	Max flow via GD (continued). Electrical flows. Linear system solving.
20.	Wed, Oct. 23:	Max flow via GD (continued). Electrical flows. Linear system solving.
21.	Fri, Oct. 25:	Introduction to Approximation Algorithms.	nb	nb
22.	Mon, Oct. 28:	Approximation Algorithms: Greedy approaches. Enumeration and FPRAS (scheduling)		nb
23.	Wed, Oct. 30:	Approximation Algorithms: Rounding LP solutions (Vertex Cover, Facility Location).
24.	Fri, Nov. 1:	Approximation Algorithms: MAX-SAT, parameterized complexity		nb
24.	Mon, Nov. 4:	Computational Geometry I.	nb	nb
25.	Wed, Nov. 6:	Computational Geometry II.		nb
26.	Fri, Nov. 8:	Online Algorithms: Ski Rental, Paging.	nb	nb
27.	Mon, Nov. 11:	(No class)
28.	Wed, Nov. 13:	Online Algorithms: Adversaries, Randomization, k-server.
29.	Fri, Nov. 15:	Online Algorithms: Adversaries, Randomization, k-server.
29.	Mon, Nov. 18:	Parallel algorithms-circuits.	nb
30.	Wed, Nov. 20:	Parallel algorithms-PRAMs.	nb
31.	Fri, Nov. 22:	External memory algorithms.	nb
32.	Mon, Nov. 25:	Streaming algorithms.	nb
	Mon, Dec. 2:	[Optional] Random walks.	pdf