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 Required Background 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. Course Relevance This course is primarily aimed at graduate and advanced undergraduate students interested in doing research in theoretical computer science. 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. 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/
