Advanced Algorithms
Course ID 15850
Description An intensive graduate course on the design and analysis of algorithms.
Key Topics
MSTs. Recap Prim/Kruskal/Boruvka
Shortest paths. recall Dijkstra/Bellman-Ford/etc, Seidel's algorithm using matrix multiplication, recent near-linear time algorithm with negative-weight edges.
Matchings: classical matchings using augmenting paths, matching using matrix inversions (Tutte/Lovasz, Mucha-Sankowski), matchings using random walks, matchings using matrix balancing.
The Experts algorithm via multiplicative weights, online gradient descent.
Flows: max-flows via electrical flows, Sherman's near-linear time max-flow.
Linear and Convex Programming
Solving convex optimization problems via gradient descent, ellipsoid, interior-point methods
Using convex optimization to solve combinatorial problems (maybe)
High-dimensional geometry: Dimension reduction and singular value decompositions.
Fixed-parameter tractable algorithms.
Streaming algorithms (a.k.a. algorithms for big data)
Online algorithms
Approximation Algorithms
The Sums-of-Squares Paradigm
Learning Resources
There is no textbook for the course. Most of our material is not in textbooks (yet), so we will rely on lecture notes, papers and monographs. We will provide you with lecture notes; we appreciate feedback and suggestions for improvements.
Course Relevance
This course is primarily aimed at graduate and advanced undergraduate students interested in doing research in theoretical computer science.
Pre-required Knowledge
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 must learn how to learn.
Assessment Structure
We have 3 lectures a week for the first ~10 weeks of the semester. Attendance is required: it's a fast-moving course, so if you miss lecture you may find it more difficult to keep up. We have ~7 HWs (including HW0). Your grade will depend on these HWs, class participation, and attendance.
Course Link
https://www.cs.cmu.edu/~15850/