6.854/18.415J: Advanced Algorithms (Fall 2017)

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

Units:	5-0-7 Graduate H-level
Instructor:	David Karger	karger at mit edu	Office hours: Arrange by email. In Building 32, Room G592
TAs:	Justin Kopinsky	jkopin at mit.edu
	Luke Schaeffer	lrs at mit.edu
	Office hours:	Mondays and Fridays 4:00-5:00 Stata G5 lounge (right outside the elevators)
Course assistant:	Rebecca Yadegar	ryadegar at csail.mit.edu

Course Announcements

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.
Use this Google spreadsheet to look for collaborators for the project. Project groups should be no larger than 3 people.
The course info sheet.
NEW! Course project information is up.

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

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) 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 both TAs.

Problem Set	Due Date	Solutions	(Mandatory) Time Report	(Optional) Difficulty/Usefulness Survey
PS 1	Fri, Sep. 15	SOL 1	form	form
PS 2	Wed, Sep. 20	SOL 2	form	form
PS 3	Wed, Sep. 27	SOL 3	form	form
PS 4	Wed, Oct. 4	SOL 4	form	form
PS 5	Wed, Oct. 11	SOL 5	form	form
PS 6	Wed, Oct. 18	SOL 6	form	form
PS 7	Wed, Oct. 25	SOL 7	form	form
PS 8	Wed, Nov. 1	SOL 8	form	form
PS 9	Wed, Nov. 8	SOL 9	form	form
PS 10	Wed, Nov. 15	SOL 10	form	form
PS 11	Wed, Nov. 22	SOL 11	form	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. 6: Course introduction. Fibonacci heaps. MST. nb nb

2. Fri, Sep. 8: Fibonacci heaps. Persistent Data Structures. nb nb

3. Mon, Sep. 11: Persistent data structures.

4. Wed, Sep. 13: Splay trees. nb nb

5. Fri, Sep. 15: Dial's Algorithm. Tries. Multi-level buckets. nb

6. Mon, Sep. 18: Van Emde Boas queues. Hashing. Universal Hashing nb nb

7. Wed, Sep. 20: Perfect Hashing. Intro to Network Flows

Fri, Sep. 22: Rosh Hashanah, no class

8. Mon, Sep. 25: Network Flows. Characterization. Decomposition. Augmenting Paths. nb nb

9. Wed, Sep. 27: Network Flows: Maximum augmenting path. Strongly polynomial algorithms. Shortest augmenting path. nb nb

Fri, Sep. 29: Student Holiday, no class

10. Mon, Oct. 2: Network Flows: Scaling. Blocking flows. nb nb

11. Wed, Oct. 4: Network Flows: Min-Cost Flows. Definitions. Characterization. Pseudopolynomial algorithm: cycle canceling.

Fri, Oct. 6: Suffix Trees (optional)

Mon, Oct. 9: Columbus Day, no class

12. Wed, Oct. 11: Min-Cost Flows: Feasible prices. Polynomial algorithms: shortest augmenting path; scaling. nb nb

Fri, Oct. 13: Finish min cost flows

13. Mon, Oct. 16: Linear-Programming: definitions: canonical and standard forms, feasibility and optimization. Structure of Optima. nb nb

14. Wed, Oct. 18: Linear-Programming: Duality Theory. nb nb

15. Fri, Oct. 20: Linear-Programming: Duality Applications.

16. Mon, Oct. 23: Linear Programming Algorithms: Simplex nb

17. Wed, Oct. 25: Linear-Programming Algorithms: Ellipsoid, Interior Point. nb

18. Fri, Oct. 27: NP-hard problems. Approximation Algorithms. Relative Approximations. nb

19. Mon, Oct. 30: PAS and FPAS. Scheduling. nb nb

20. Wed, Nov. 1: Relaxations. 3/2-approximation for TSP. ILP relaxations. nb

21. Fri, Nov. 3: ILP relaxations. Randomized Rounding. nb nb

22. Mon, Nov. 6: Online Algorithms: ski rental, load balancing nb nb

23. Wed, Nov. 8: Online algorithms: linked lists, paging. nb

Fri, Nov. 10: Veteran's Day, no class.

24. Mon, Nov. 13: Randomized online algorithms, adversaries. k-server. nb

25. Wed, Nov. 15: Computational geometry: orthogonal range search, convex hull nb nb

26. Fri, Nov. 17: Computational geometry: Voronoi diagram (Fortune's algorithm animation)

27. Mon, Nov. 20: External memory algorithms.

28. Wed, Nov. 22: Buffer trees. Cache oblivious algorithms.

Thurs, Nov. 23: Thanksgiving

29. Mon, Nov. 27: Parallel algorithms--circuits.

30. Wed, Nov. 29: Parallel algorithms--PRAMs.

Fri, Dec. 1:

Mon, Dec. 4:

Wed, Dec. 6:

Fri, Dec. 8:

Mon, Dec. 11: In-class peer editing assignment.

Wed, Dec. 13: Final Project due date. Possible optional lecture.

#	Date	Topic	Raw Notes	Scribe
1.	Wed, Sep. 6:	Course introduction. Fibonacci heaps. MST.	nb	nb
2.	Fri, Sep. 8:	Fibonacci heaps. Persistent Data Structures.	nb	nb
3.	Mon, Sep. 11:	Persistent data structures.
4.	Wed, Sep. 13:	Splay trees.	nb	nb
5.	Fri, Sep. 15:	Dial's Algorithm. Tries. Multi-level buckets.	nb
6.	Mon, Sep. 18:	Van Emde Boas queues. Hashing. Universal Hashing	nb	nb
7.	Wed, Sep. 20:	Perfect Hashing. Intro to Network Flows
	Fri, Sep. 22:	Rosh Hashanah, no class
8.	Mon, Sep. 25:	Network Flows. Characterization. Decomposition. Augmenting Paths.	nb	nb
9.	Wed, Sep. 27:	Network Flows: Maximum augmenting path. Strongly polynomial algorithms. Shortest augmenting path.	nb	nb
	Fri, Sep. 29:	Student Holiday, no class
10.	Mon, Oct. 2:	Network Flows: Scaling. Blocking flows.	nb	nb
11.	Wed, Oct. 4:	Network Flows: Min-Cost Flows. Definitions. Characterization. Pseudopolynomial algorithm: cycle canceling.
	Fri, Oct. 6:	Suffix Trees (optional)
	Mon, Oct. 9:	Columbus Day, no class
12.	Wed, Oct. 11:	Min-Cost Flows: Feasible prices. Polynomial algorithms: shortest augmenting path; scaling.	nb	nb
	Fri, Oct. 13:	Finish min cost flows
13.	Mon, Oct. 16:	Linear-Programming: definitions: canonical and standard forms, feasibility and optimization. Structure of Optima.	nb	nb
14.	Wed, Oct. 18:	Linear-Programming: Duality Theory.	nb	nb
15.	Fri, Oct. 20:	Linear-Programming: Duality Applications.
16.	Mon, Oct. 23:	Linear Programming Algorithms: Simplex	nb
17.	Wed, Oct. 25:	Linear-Programming Algorithms: Ellipsoid, Interior Point.	nb
18.	Fri, Oct. 27:	NP-hard problems. Approximation Algorithms. Relative Approximations.		nb
19.	Mon, Oct. 30:	PAS and FPAS. Scheduling.	nb	nb
20.	Wed, Nov. 1:	Relaxations. 3/2-approximation for TSP. ILP relaxations.		nb
21.	Fri, Nov. 3:	ILP relaxations. Randomized Rounding.	nb	nb
22.	Mon, Nov. 6:	Online Algorithms: ski rental, load balancing	nb	nb
23.	Wed, Nov. 8:	Online algorithms: linked lists, paging.		nb
	Fri, Nov. 10:	Veteran's Day, no class.
24.	Mon, Nov. 13:	Randomized online algorithms, adversaries. k-server.		nb
25.	Wed, Nov. 15:	Computational geometry: orthogonal range search, convex hull	nb	nb
26.	Fri, Nov. 17:	Computational geometry: Voronoi diagram (Fortune's algorithm animation)
27.	Mon, Nov. 20:	External memory algorithms.
28.	Wed, Nov. 22:	Buffer trees. Cache oblivious algorithms.
	Thurs, Nov. 23:	Thanksgiving
29.	Mon, Nov. 27:	Parallel algorithms--circuits.
30.	Wed, Nov. 29:	Parallel algorithms--PRAMs.
	Fri, Dec. 1:
	Mon, Dec. 4:
	Wed, Dec. 6:
	Fri, Dec. 8:
	Mon, Dec. 11:	In-class peer editing assignment.
	Wed, Dec. 13:	Final Project due date. Possible optional lecture.