15-457A/15-859E: Advanced Algorithms, Spring 2015
- Lecturer: Anupam
Gupta, GHC 7203.
- TA: Euiwoong
Lee
GHC 7503.
Office hours: Anupam: Mondays 3-4pm (or as announced on the blog);
Euiwoong: Thursdays 4-5pm (or by email).
- Location: GHC 4211, MWF 1:30-2:50.
- Blog: https://cmuadvancedalgos.wordpress.com
Announcements
Homeworks
Lectures
- Lecture 1. MSTs. Recap Prim/Kruskal/Boruvka. An $O(m \log^* n)$ time
algorithm. (unedited scribe notes, my notes)
- Lecture 2. MSTs. A randomized linear time-algorithm. MST
verification. (unedited scribe notes, my notes)
- Lecture 3: Directed MSTs
a.k.a. arborescences. Chu-Liu-Edmonds-Bock algorithm. LP Dual fitting.
(my notes)
And some very basic information on LPs and duality:
- Very basic notes from
15-451: basics, duality
- Course on linear programs/semidefinite programs in CS by Ryan O'Donnell and me.
- Chapter on duality from the excellent Matousek and Gaertner
book. (CMU only)
- Lecture 4: Shortest Paths. Seidel's algorithm for (unweighted
undirected) APSP using
matrix multiplication.
(unedited scribe notes, my notes)
- Lecture 5: Shortest Paths. Williams' algorithm for APSP using
polynomials and matrix multiplication.
(unedited scribe notes, my notes)
We didn't get a chance to go over Fredman's proof that APSP can be
solved using only $O(n^{2.5})$ comparisons.
- Lecture 6: Low-stretch Trees. Bartal's construction.
(unedited scribe notes, my notes)
- Lecture
notes from our randomized algorithms course (S11).
- Alon, Karp, Peleg, West: A Graph-Theoretic Game and its
Application to the k-Server Problem, SICOMP.
- Bartal: Probabilistic Approximation of Metric Spaces and its
Algorithmic Applications, FOCS 96
Our presentation pretty much followed his general construction.
- Fakcharoenphol, Rao,
Talwar, A
tight bound on approximating arbitrary metrics by tree
metrics, STOC 03.
This paper gives the best possible algorithm
for the metric graph case.
- Abraham, Neiman: Using Petal-Decompositions to Build a Low Stretch
Spanning Tree.
This paper gives the current best algorithm
for the general graph case.
Some other low-diameter decomposition schemes:
And applications of low-stretch spanning trees to some problems:
- Approximation Algorithms, solving linear systems.
- Lecture 7: Matchings in Graphs: combinatorial algorithms
(unedited scribe notes, my notes)
- Lecture 8: Edmonds' Blossom Algorithm.
(unedited scribe notes, my notes, same as for Lec#7)
- Lecture 9: Max-Weight Matchings.
(unedited scribe notes, my notes)
- Lecture 10: LPs. The Perfect Matching Polytope. Integrality of polytopes.
(unedited scribe notes, my notes 1, 2)
- Lecture 11: Matrix-based algorithms for
Matchings via Polynomial Identity Testing.
(unedited scribe notes,
my notes)
And other papers that we did not get to (or discussed in passing):
- Lecture 12: Online Learning and the Multiplicative-Weights Algorithm.
(unedited scribe notes, my
notes from the LP/SDP course)
- Avrim's slides
from 15-451 (F13).
- The
Arora-Hazan-Kale survey.
- Lecture 13: Applications of MW:
zero-sum-games, solving LPs (start)
(unedited scribe notes, notes on 0-sum games, my
notes from the LP/SDP course)
- Pages of the
Arora-Hazan-Kale survey
talking about zero-sum games.
- Lecture 14: Applications of MW: solving LPs, max-flows
using shortest paths. (unedited scribe notes, LP
notes, flow notes)
- The notes
from the LP/SDP course have Ax ge b instead of Ax le b, but the idea
is really the same.
Also, it has an example running the
algorithm for solving the Set Cover LP.
- Rohit
Khandekar's thesis
makes great reading about solving convex programs using MW; so
does Satyen
Kale's thesis;
both have great survey chapters.
- Relevant section of the
Arora-Hazan-Kale survey.
- Lecture 15: Applications of MW: max-flows
using electrical flows.
(unedited scribe notes, electrical flow
notes)
- Lecture 16: Gradient Descent. Yet another low-regret
algorithm.
(unedited scribe notes, my notes)
- Lecture 17: The Ellipsoid Algorithm: an overview
(scribe notes, my notes)
- Lecture 18: Concentration of Measure: "Chernoff-Hoeffding" Bounds.
(unedited scribe notes, my notes)
And some history:
- Lecture 19: Dimension Reduction: JL and related topics
(my scribe notes)
- No Lecture on Feb 27. HW #4 due, please give to Euiwoong.
- Lecture 20: Streaming I: Computing Frequency Moments and JL
(my scribe notes)
- Lecture 21: Dimension Reduction: Singular Value Decompositions
(scribe notes, my notes)
- Lecture 22: SVDs II: Fast SVDs via sampling
(my notes)
- Lecture 23: SVDs III: Misra-Gries, Deterministic
Streaming SVDs
(my notes)
- Lecture 24: Fixed-Parameter and Exact Algorithms I
(my notes)
- Lecture 25: Fixed-Parameter and Exact Algorithms II
- See the handwritten notes and links for Lecture 24.
- Chandra
Chekuri's survey
talk on treewidth.
- Treewidth notes from Ryan's Theorist's Toolkit class
- Lecture 26: Online Algorithms: Rent-or-Buy and Paging,
Online Primal-Dual
(my notes)
- No Lectures March 27-April 1. Happy
Spring Break!
Next lecture on Friday, April 3.
- Lecture 27: Semidefinite Programs I: Intro, Examples,
MaxCut, Duality
(my notes)
- Lecture 28: Semidefinite Programs II (Checking SoS) +
Smoothed Analysis I (Definitions)
Sum-of-Squares: (my notes on SoS, Grothendieck which
we did not cover)
Smooth Complexity: (unedited scribe notes joint with lecture 29, my notes)
- Lecture 29: Smoothed Analysis, and Beyond-Worst Case
(unedited scribe notes, my notes)
Maintained by Anupam Gupta