6.854/18.415J: Advanced Algorithms (Fall 2020)

Lecture:	Monday, Wednesday, and Friday 2:30-4 (Online lectures)

Units:	5-0-7 Graduate H-level
Instructors:	David Karger	karger@mit.edu	Office hours: Arrange by email. In Building 32, Room G592
TAs:	Josh Brunner	brunnerj@mit.edu
	Christian Altamirano	bdiehs@mit.edu
	Thiago Bergamaschi	thiagob@mit.edu
	Office hours:	Monday 5:30-6:30pm and Friday 4-5pm online
Course assistant:	Rebecca Yadegar	ryadegar@csail.mit.edu

Course Announcements

Lectures will be streamed online during class time and recorded for later viewing. The zoom link is here. We have the waiting room enabled, so make sure to arrive early so that you can be admitted.
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 and HTML 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.
The project handout is here. The project proposal will be due with pset 12.
Use this Google spreadsheet to look for collaborators for the project. Project groups should be no larger than 3 people.
There are sample projects from past years at here to give you more of an idea of what a project should look like for this class.

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.
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 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.
So you can meet more of your classmates and so we can make the collaboration groups more equitable, we will be giving you random partners every 3 psets. Starting on problem set 4, you should not form a group with anyone that you have already worked with on 3 psets or more.

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.

Problem Set	Due Date	Solutions	Grading Supervisor	Gradescope code	(Mandatory) Time Report	Peer Grading Sign-up	Late Submission
PS1	Wed, Sep. 9	PS1 Sol	Josh	MY4B55	PS1 Time Survey	PS1 Peer Grading	PS1 Late Form
PS2	Wed, Sep. 16	PS2 Sol	Thiago	MPV7N7	PS2 Time Survey	PS2 Peer Grading	PS2 Late Form
PS3	Wed, Sep. 23	PS3 Sol	Christian	95YNW7	PS3 Time Survey	PS3 Peer Grading	PS3 Late Form
PS4	Wed, Sep. 30	PS4 Sol	Josh	ME3N7E	PS4 Time Survey	PS4 Peer Grading	PS4 Late Form
PS5	Wed, Oct. 7	PS5 Sol	Christian	KY53DB	PS5 Time Survey	PS5 Peer Grading	PS5 Late Form
PS6	Wed, Oct. 14	PS6 Sol	Josh	KY586R	PS6 Time Survey	PS6 Peer Grading	PS6 Late Form
PS7	Wed, Oct. 21	PS7 Sol	Christian	X3Y4DX	PS7 Time Survey	PS7 Peer Grading	PS7 Late Form
PS8	Wed, Oct. 28	PS8 Sol	Thiago	KY52ZG	PS8 Time Survey	PS8 Peer Grading	PS8 Late Form
PS9	Wed, Nov. 4	PS9 Sol	Josh	JBB3V7	PS9 Time Survey	PS9 Peer Grading	PS9 Late Form
PS10	Thu, Nov. 12	PS10 Sol	Christian	JBB48K	PS10 Time Survey	PS10 Peer Grading	PS10 Late Form
PS11	Wed, Nov. 18	PS11 Sol	Josh	N884Y5	PS11 Time Survey	PS11 Peer Grading	PS11 Late Form
PS12	Wed, Dec. 2	PS12 Sol	Christian	JBBJY4	PS12 Time Survey	PS12 Peer Grading	PS12 Late Form

Lectures

Warning: This is last year's schedule, and will be changing. 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 Video

1. Wed, Sep. 2: Course introduction. Fibonacci heaps. MST. nb and nb nb video

2. Fri, Sep. 4: Fibonacci heaps. MST. Persistent Data Structures Intro. nb nb video

3. Wed, Sep. 9: Persistent Data Structures. Splay trees intro. nb nb video

4. Fri, Sep. 11: Splay trees. nb nb video

5. Mon, Sep. 14: Dial's Algorithm. Tries. Multi-level buckets. nb nb video

6. Wed, Sep. 16: van Emde Boas Queues and Hashing nb nb video

7. Fri, Sep. 18: Universal Hashing. Perfect Hashing. Begin Network Flows. video

8. Mon, Sep. 21: Network Flows: Charaterization. Augmenting Paths. Max Flow Min Cut Theorem. nb nb video

9. Wed, Sep. 23: Network Flows: Maximum augmenting path. Capacity Scaling. nb nb video

10. Fri, Sep. 25: Network Flows: Strongly polynomial algorithms. Blocking Flows. nb nb video

11. Mon, Sep. 28: Min-Cost Flows: Feasible prices. nb nb video

12. Wed, Sep. 30: Min-Cost Flows nb video

13. Fri, Oct. 2: Finish Min-Cost Flows and Introduction to Linear Programming. video

14. Mon, Oct. 5: Linear Programming: Structure of Optima. nb nb video

15. Wed, Oct. 7: Linear Programming: Strong Duality. nb nb video

16. Fri, Oct. 9: Linear Programming: Strong Duality and Duality Applications. nb nb video

17. Tue, Oct. 13: Linear Programming: Duality Applications. nb nb video

18. Wed, Oct. 14: Linear Programming: Simplex Method. nb video

19. Fri, Oct. 16: Linear Programming: Ellipsoid Method. nb video

20. Mon, Oct. 19: Introduction to Approximation Algorithms. nb nb video

21. Wed, Oct. 21: Approximation Algorithms: Greedy approaches. Enumeration and FPAS (scheduling) nb video

22. Fri, Oct. 23: Approximation Algorithms: Enumeration, Rounding, Metric TSP. video

23. Mon, Oct. 26: Approximation Algorithms: Relaxations video

24. Wed, Oct. 28: Approximation Algorithms: Randomized Rounding nb video

25. Fri, Oct. 30: Computational Geometry I. nb nb video

26. Mon, Nov. 2: Computational Geometry II: Voronoi Diagrams nb video

27. Wed, Nov. 4: Online Algorithms: Ski Rental, Paging. nb nb video

28. Fri, Nov. 6: Online Algorithms: Paging, Adversaries, Randomization nb nb video

29. Mon, Nov. 9: Online Algorithms: Adversaries, Randomization, k-server. video

30. Fri, Nov. 13: The k-server problem and External Memory Algorithms. video

31. Mon, Nov. 16: External Memory Algorithms. nb video

32. Wed, Nov. 18: Parallel Algorithms. nb video

33. Fri, Nov. 20: Parallel Algorithms. nb video

Below this point is last year's schedule.

#	Date	Topic	Raw Notes	Scribe	Video
1.	Wed, Sep. 2:	Course introduction. Fibonacci heaps. MST.	nb and nb	nb	video
2.	Fri, Sep. 4:	Fibonacci heaps. MST. Persistent Data Structures Intro.	nb	nb	video
3.	Wed, Sep. 9:	Persistent Data Structures. Splay trees intro.	nb	nb	video
4.	Fri, Sep. 11:	Splay trees.	nb	nb	video
5.	Mon, Sep. 14:	Dial's Algorithm. Tries. Multi-level buckets.	nb	nb	video
6.	Wed, Sep. 16:	van Emde Boas Queues and Hashing	nb	nb	video
7.	Fri, Sep. 18:	Universal Hashing. Perfect Hashing. Begin Network Flows.			video
8.	Mon, Sep. 21:	Network Flows: Charaterization. Augmenting Paths. Max Flow Min Cut Theorem.	nb	nb	video
9.	Wed, Sep. 23:	Network Flows: Maximum augmenting path. Capacity Scaling.	nb	nb	video
10.	Fri, Sep. 25:	Network Flows: Strongly polynomial algorithms. Blocking Flows.	nb nb		video
11.	Mon, Sep. 28:	Min-Cost Flows: Feasible prices.	nb	nb	video
12.	Wed, Sep. 30:	Min-Cost Flows		nb	video
13.	Fri, Oct. 2:	Finish Min-Cost Flows and Introduction to Linear Programming.			video
14.	Mon, Oct. 5:	Linear Programming: Structure of Optima.	nb	nb	video
15.	Wed, Oct. 7:	Linear Programming: Strong Duality.	nb	nb	video
16.	Fri, Oct. 9:	Linear Programming: Strong Duality and Duality Applications.	nb	nb	video
17.	Tue, Oct. 13:	Linear Programming: Duality Applications.	nb	nb	video
18.	Wed, Oct. 14:	Linear Programming: Simplex Method.	nb		video
19.	Fri, Oct. 16:	Linear Programming: Ellipsoid Method.	nb		video
20.	Mon, Oct. 19:	Introduction to Approximation Algorithms.	nb	nb	video
21.	Wed, Oct. 21:	Approximation Algorithms: Greedy approaches. Enumeration and FPAS (scheduling)		nb	video
22.	Fri, Oct. 23:	Approximation Algorithms: Enumeration, Rounding, Metric TSP.			video
23.	Mon, Oct. 26:	Approximation Algorithms: Relaxations			video
24.	Wed, Oct. 28:	Approximation Algorithms: Randomized Rounding		nb	video
25.	Fri, Oct. 30:	Computational Geometry I.	nb	nb	video
26.	Mon, Nov. 2:	Computational Geometry II: Voronoi Diagrams		nb	video
27.	Wed, Nov. 4:	Online Algorithms: Ski Rental, Paging.	nb	nb	video
28.	Fri, Nov. 6:	Online Algorithms: Paging, Adversaries, Randomization	nb	nb	video
29.	Mon, Nov. 9:	Online Algorithms: Adversaries, Randomization, k-server.			video
30.	Fri, Nov. 13:	The k-server problem and External Memory Algorithms.			video
31.	Mon, Nov. 16:	External Memory Algorithms.	nb		video
32.	Wed, Nov. 18:	Parallel Algorithms.	nb		video
33.	Fri, Nov. 20:	Parallel Algorithms.	nb		video
		Below this point is last year's schedule.

References

Wed, Sep. 3

M. Fredman and R. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, 34 (1987), 596-615.

Fri, Sep. 5

H. Gabow, Z. Galil, T. Spencer, R. Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica 6(2): 109-122 (1986).
D. Karger, P. Klein, R. Tarjan, A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees, J. ACM 42(2): 321-328 (1995).
S. Pettie, V. Ramachandran, An optimal minimum spanning tree algorithm, Journal of the ACM, vol. 49, no. 1, pp.16-34, 2002.
B. Chazelle, A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, Journal of the ACM, 47 (2000), 1028-1047.

Mon, Sep. 8

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

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.

Mon, Sep. 15

Boris V. Cherkassky, Andrew V. Goldberg and Craig Silverstein. Buckets, heaps, lists, and monotone priority queues.

Wed, Oct. 8

Eva Tardos. A Strongly Polynomial Minimum Cost Circulation Algorithm

Accessibility