15-850: Advanced Algorithms, Fall 2018

Lecturer: Anupam Gupta, GHC 7203.
TAs: Jason Li, Goran Zuzic
Office hours: Anupam: TBD, Jason: TBD, Goran: TBD.

Location: GHC 4211, MWF 1:30-2:50 (note: 3 days a week)
Blog: coming soon.
Piazza: here



An intensive graduate course on the design and analysis of algorithms, picking up from where 15-451 stopped. It will be more specialized and in-depth than the Graduate Algorithms course 15-750. We will cover advanced algorithmic ideas (some classical, some very recent), and the theory behind it (theorems, proofs). For topics that were covered in 451/750, the goal is to cover advanced content and new techniques.


The current list of potential topics are:
  1. MSTs. Recap Prim/Kruskal/Boruvka, an $O(m \log^\star n)$ time algorithm, a randomized linear-time algorithm, MSTs in directed graphs
  2. Shortest paths. recall Dijkstra/Bellman-Ford/etc, Seidel's algorithm using matrix multiplication, Williams' APSP algorithm from 2014.
  3. Matchings: classical matchings using augmenting paths, matching using matrix inversions (Tutte/Lovasz, Mucha-Sankowski), matchings using random walks.
  4. The Experts algorithm via multiplicative weights, online gradient descent.
  5. Flows: max-flows via electrical flows, Sherman's near-linear time max-flow.
  6. Linear and Convex Programming
  7. High-dimensional geometry: Dimension reduction and singular value decompositions.
  8. Fixed-parameter tractable algorithms.
  9. Streaming algorithms (a.k.a. algorithms for big data)
  10. Online algorithms
  11. Approximation Algorithms
  12. The Sums-of-Squares Paradigm
  13. Submodular Optimization
Here are the Spr 17 and Spr 15 versions of this course. The topics this year will be similar (though not identical). I will take a poll in mid-Oct about topics to cover in the last 4-5 lectures.

Effort and Criteria for Evaluation:

We have 3 lectures a week for the first ~10 weeks of the semester. Attendance is required. You will scribe 1-2 lectures in Latex: either you will polish/augment old lecture notes, or will write new notes. We have ~7 HWs (including HW0), half solved with collaboration, others solved individually. Your grade will depend on these HWs, scribe notes, class participation, and attendance.


There is no textbook for the course. Most of our material is not in textbooks (yet), so we will rely on papers, monographs, and lecture notes.


You should know material in standard UG courses in algorithms, probability, and linear algebra very well. Above all, mathematical maturity/curiosity and problem-solving skills are a must. That way you can make up for gaps in your knowledge yourself. It is natural to not know everything, or for you to get rusty on concepts, but you should learn how to learn. This may seem vague, so here are concrete things.


Your Health & Well-being

This is an intensive (and somewhat intense) course: 3 days a week, studying new/advanced topics, several HWs. One major goal is that you will have fun taking it and learning this new cool material, as much as I hope to have fun teaching it. Part of making sure you have fun involves taking care of yourself. Do your best to maintain a healthy lifestyle this semester by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.

If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS) is here to help: call 412-268-2922 and visit http://www.cmu.edu/counseling/. Consider reaching out to a friend, faculty or family member you trust for help getting connected to the support that can help.

Accommodations for Students with Disabilities:

If you have a disability and are registered with the Office of Disability Resources, I encourage you to use their online system to notify me of your accommodations and come and see me to discuss your needs with me as early in the semester as possible. Since this is a fast-moving course, we should discuss how to make things work out. I will work with you to ensure that accommodations are provided as appropriate. If you suspect that you may have a disability and would benefit from accommodations but are not yet registered with the Office of Disability Resources, I encourage you to contact them at access@andrew.cmu.edu.

Academic Integrity

Honesty and transparency are important features of good scholarship. On the flip side, plagiarism and cheating are serious academic offenses with serious consequences. If you are discovered engaging in either behavior in this course, you will earn a failing grade on the assignment in question, and further disciplinary action may be taken. For a clear description of what counts as plagiarism, cheating, and/or the use of unauthorized sources, please see the University Policy on Academic Integrity and the Carnegie Mellon Code on Academic Integrity.
Maintained by Anupam Gupta