CS 6550  Advanced Algorithms
Fall 2010  Tuesday/Thursday 12:0013:30
Home Assignments
Topics covered
Randomized Algorithms

Lecture 1:
Papadimitriou's random walk algorithm for 2SAT.

Lecture 2:
Schoning's random walk algorithm for 3SAT.

Lecture 3:
Second moment method (Chebyshev's Inequality), higher moment inequalities
and Chernofftype Inequalities.

Lecture 4:
Balls and bins, Birthday paradox, Maximum Load and Coupon collector.
A 1/2approximation algorithm for MaxCut and its derandomization.

Lecture 5:
Contstructions of pairwiseindependent random variables. Application
to Universal hash functions.

Lecture 6:
Construction of Perfect Hash Tables (Fredman, Komlos and Szemeredi). Lower
bound on size of pairwise indepedent sample spaces.

Lecture 7:
Construction of kwise independent random variables using BCH codes.
Lower bound on size of kwise independent sample spaces.

Lecture 8:
The power of two choices.

Lecture 9:
Hardness of finding unique solutions (ValiantVazirani Theorem). Discrepancy of 4wise independent indicators.
CanteliChebyshev Inequality.
Fixed Parameter Algorithms

Lecture 10:
A 2approximation for the vertex cover
problem and a fixed parameter algorithm for it.

Lecture 11:
Fixed parameter algorithm for finding kpaths using ColorCoding
(AlonYusterZwick). An O(logn)approximation for the FeedbackVertexSet
problem and a fixed parameter algorithm for it.
Combinatorial Approximation Algorithms

Lecture 12:
Analysis of the greedy approximation algorithms for SetCover and
MaximumCoverage.

Lecture 13:
A 3approximation algorithm for FeedbackVertexSet. A 2approximation
algorithm for kCenter.

Lecture 14:
2Approximation for SteinerTree problem. 3/2Approximation for metric TSP
(Christofides's Algorithm).

Lecture 15:
O(logn)Approximation for Asymmetric TSP (FriezeGalbiatiMaffioli).
O(log*n)Approximation for
Assymetric kcenter problem (PanigrahyVishwanathan).
Maximum Matching

Lecture 16:
SchwartzZippel Lemma. Computing size of maximum matching in bipartite
graphs.

Lecture 17:
Computing size of Maximum Matching in general graphs using Tutte's
matrix (Lovasz). Augmenting paths (Berge's Theorem). Finding
Maximum Matching and Minimum Vertex Cover in bipartite
graphs. KonigEgervary Theorem.

Lecture 18:
Maximum matching in bipartite graphs (HopcroftKarp Algorithm)

Lecture 19:
Maximum Matching in general graphs (Edmonds' BlossomShrinking Algorithm)
Fast Matrix Multiplication and Shortest Paths

Lecture 20:
Fast Matrix Multiplication (Strassen's Algorithm). Matrix multiplication
and the All Pairs Shortest Paths Problem.

Lecture 21:
All Pairs Shortest Paths using Fast Matrix Multiplication (Seidel's
Algorithm). Finding witnesses for Boolean Matrix Multiplication.
Finding witnesses for APSP.
Eigenvalues and Expansion

Lecture 22:
Graph Laplacian. Relation between second eigenvalue and connectivity.

Lecture 23:
Relation between second eigenvalue and vertex connectivity (Fiedler). The
"easy" direction of Cheeger's Inequality
(AlonMilman/Tanner). Second eigenvalue as a relaxation of SparsestCut.

Lecture 24:
The "hard" direction of Cheeger's Inequality (Alon). The spectral
partition algorithm for finding sparse cuts.

Lecture 25:
dregular expanders and the expander mixing lemma (Alon/Chung).

Lecture 26:
Vertex expansion and Tanner's Theorem. Fast mixing of random walks on expanders.

Lecture 27:
Constructing ErrorCorrecting Codes from Expander Graphs

Lecture 28:
A LinearProgramming relaxation of SparsestCut (LeightonRao). Rounding the LP using Metric Embedding (LinialLondonRabinovich). An integrality gap instance using expanders.