6.854/18.415J: Advanced Algorithms (Fall 2018)

Lecture: Monday, Wednesday, and Friday 2:30-4 in 2-190.
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: Kyriakos Axiotis kaxiotis@mit.edu
  Brynmor Chapman brynmor@mit.edu
  Aleksandar Makelov amakelov@mit.edu
  Sandeep Silwal silwal@mit.edu
Office hours: Monday and Friday 4-5pm in 2-135
Course assistant: Rebecca Yadegar ryadegar at csail.mit.edu

Course Announcements

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

Problem Set Due Date Solutions Grading Supervisor Graders (Mandatory) Time Report (Optional) Difficulty/Usefulness Survey
PS 1 Wed, Sep. 12 Sol. 1 Sandeep P2 tslilyai, xygong
P3 gilkur, rkavya
P4 chenxing, jisoomin
P5 mihirs, yyao1
Link Link
PS 2 Wed, Sep. 19 Sol. 2 Brynmor P1a kliment
P2a luciali
P2b cgrunau
P2c nreddy
P3a rogerjin
P3b ineq
P3c aliu99
P3d yiqiuw
P4 mateus
P5 varkey
Link Link
PS 3 Wed, Sep. 26 Sol. 3 Kyriakos P1 jeshi, zyteka
P2 anshula, danifili
P3 hflatval, vrichmon
P4 wellman, yunyizhu
Link Link
PS 4 Wed, Oct. 3 Sol. 4 Aleksandar P1 hansonyu, zixuanxu
P2 maxfish
P3 qqi
P4 ignapb, bdiehs
P5 mcnallyc, alokhina
P6 svelusamy@g.harvard.edu, junyaop
Link Link
PS 5 Wed, Oct. 10 Sol. 5 Sandeep P1 yizhai, jstrang
P2 jasonlu, zeyuans
P3 bchen21, ch3nj
P4 moberst, rbuhai
P5 lillianz, shreyasb
Link Link
PS 6 Wed, Oct. 17 Sol. 6 Brynmor P1 darry140
P2 vibhaa
P3 rahuly
P4 zhulin
P5 ericaw
Link Link
PS 7 Wed, Oct. 24 Sol. 7 Kyriakos P1 ecai
P2 davidja
P3 ldec
P4 dobsonm
P5 tfh
Link Link
PS 8 Wed, Oct. 31 Sol. 8 Aleksandar P1 nwu
P2 turneram
P3 nwu
P4 swooders
P5 stevliu
Link Link
PS 9 Wed, Nov. 7 Sol. 9 Sandeep P1 calvinyw
P2 quach
P3 jisoomin
P4 tkleplae
P5 tianyiz
Link Link
PS 10 Wed, Nov. 14 Sol. 10 Brynmor allenmi
aronto
beanash
dwq
kimvc
sfraser
whu2704
zfarr
Link Link
PS 11 Wed, Nov. 21 Sol. 11 Kyriakos P1 gua
P2 brunnerj, hriveron
P3 ailyas, engstrom
P4 leclerc
P5 adelay, scompton
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 Raw Notes Scribe
1. Wed, Sep. 5: Course introduction. Fibonacci heaps. MST. nb nb
2. Fri, Sep. 7: Persistent Data Structures. nb nb
Mon, Sep. 10: (Optional lecture) Spectral Graph Theory I: Random Walks and the Laplacian Matrix nb
3. Wed, Sep. 12: Splay trees. nb nb
4. Fri, Sep. 14: Dial's Algorithm. Tries. Multi-level buckets. Van Emde Boas queues nb nb
5. Mon, Sep. 17: Hashing. Universal Hashing. Perfect Hashing nb nb
Wed, Sep. 19: (Optional lecture) Spectral Graph Theory II: Graphs and Laplacian Eigenvalues
Fri, Sep. 21: (No class)
6. Mon, Sep. 24: (Video lecture) Network Flows. Characterization. Decomposition. Augmenting Paths. nb nb
7. Wed, Sep. 26: Network Flows: Maximum augmenting path. Capacity Scaling. nb nb
8. Fri, Sep. 28: Network Flows: Strongly polynomial algorithms. Shortest augmenting path. nb
9. Mon, Oct. 1: Min-Cost Flows: Feasible prices. Polynomial algorithms: shortest augmenting path; scaling. nb nb
10. Wed, Oct. 3: Finish Min-Cost Flows. nb
11. Fri, Oct. 5: Introduction to Linear Programming. nb nb
Mon, Oct. 8: (No class)
Wed, Oct. 10: (No class)
12. Fri, Oct. 12: Linear Programming: Structure of Optima. Strong Duality. nb nb
13. Mon, Oct. 15: Linear Programming: Duality Applications.
14. Wed, Oct. 17: (Video lecture) Linear Programming: Simplex and Ellipsoid Method. nb nb
15. Fri, Oct. 19: Linear Programming: Duality Applications (continued). nb nb
16. Mon, Oct. 22: Gradient Descent Method: Convexity, smoothness, strong convexity. nb
17. Wed, Oct. 24: Analysis of Gradient Descent for smooth and strongly convex functions. Regularization. Max flow. nb
18. Fri, Oct. 26: Max flow (continued). Electrical flows. Linear system solving.
19. Mon, Oct. 29: Preconditioning and Laplacian systems. Gradient Descent for general norms. Max flow (continued). Newton's method. nb
20. Wed, Oct. 31: Interior Point Methods. Introduction to Approximation Algorithms. nb nb
21. Fri, Nov. 2: Approximation Algorithms: Greedy approaches. nb
22. Mon, Nov. 5: Approximation Algorithms: Enumeration and FPRAS (scheduling).
23. Wed, Nov. 7: Approximation Algorithms: Combinatorial Approaches (TSP).
24. Fri, Nov. 9: Approximation Algorithms: Rounding LP solutions (Vertex Cover, Facility Location). nb
Mon, Nov. 12: (No class)
25. Wed, Nov. 14: Online Algorithms: Ski Rental, Paging. nb nb
26. Fri, Nov. 16: Online Algorithms: Adversaries, Randomization, k-server.
27. Mon, Nov. 19: Computational Geometry I. nb nb
Wed, Nov. 21: (No class)
Fri, Nov. 23: (No class)
28. Mon, Nov. 26: Computational Geometry II. nb