CS 263, Winter 2012: Analysis of Algorithms

This course meets Monday, Wednesday, and Friday, 11:00 - 11:50 in Bren 1429. Coursework will consist of weekly homeworks, graded during the class period on which they are due, and a final exam.

The course textbook is Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal; in addition we will use readings from the internet.

Tentative list of topics:

• Week 1: Monte Carlo algorithms and the probabilistic method. Basic concepts of probability theory. Program checking, Freivalds' algorithm for checking matrix multiplication, the Schwarz-Zippel-de Millo-Lipton method for testing polynomial identities, and its application to bipartite matching. The Valiant-Vazirani theorem on the hardness of search problems with unique solutions. Primality testing. Suggested reading: Mitzenmacher and Upfal, chapter 1.
• Week 2: Las Vegas algorithms. Quicksort and quickselect. Backwards analysis. Expected time analysis.
Suggested reading: Mitzenmacher and Upfal, chapter 2.
• Week 3: High probability time analysis. Variance, linearity of variance for independent variables. Probabilistic inequalities: Markov, Chebyshev, Chernoff. Suggested reading: Mitzenmacher and Upfal, chapters 3 and 4.
• Week 4: Balls and bins. Maximum bin size for hash chaining and load balancing. Birthday paradox and Pollard rho. Bucket sort, coupon collector, and Bloom filters. The power of two choices. Random graphs and cuckoo hashing. Suggested reading: Mitzenmacher and Upfal, chapters 5 and 14.
• Week 5: Linear programming. Strongly polynomial algorithms for low dimensional linear programming. Quasiconvex programming and LP-type problems. Smoothed analysis of the shadow vertex simplex method.
• Week 6: Approximation algorithms. Set cover and its greedy approximation. Linear programming relaxation, randomized rounding, the method of conditional probabilities for derandomization, and the equivalence of the derandomized relaxation with the greedy algorithm. Maximum cut, randomized 1/2-approximation, semidefinite programming 0.878-approximation, and connection to the unique games conjecture. Probabilistically checkable proofs and hardness of approximation.
• Week 7: Markov chains, stationary distributions, total variation distance, and mixing time. PageRank, random walks on graphs, and approximate random sampling using rapidly mixing Markov chains. Equivalence between approximate sampling and approximate counting. Approximating the volume of convex bodies. Suggested reading: Mitzenmacher and Upfal, chapters 7, 10, and 11.
• Week 8: Exponential time algorithms. Brute force search, backtracking algorithms, 3-coloring, and constraint satisfaction. Random walks for 3-satisfiability. Dynamic programming for the traveling salesman problem. Suggested reading: Mitzenmacher and Upfal, Chapter 10.
• Week 9: Inclusion-exclusion for graph coloring and bin packing. Measure and conquer, quasiconvex optimization of backtracking recurrences, and local central limits.
• Weeks 9-10: Parameterized complexity and fixed parameter tractability. The importance of choosing the right parameter: the clique problem parameterized by clique size and by degree. Kernelization and vertex cover. Longest paths, shallow backtracking, graph minors, pathwidth, treewidth, bidimensionality, and color coding.

• Homework 1, due in class Friday, January 20.
• Homework 2, due in class Friday, January 27.
• Homework 3, due in class Friday, February 3.
• Homework 4, due in class Friday, February 10.
• Homework 5, due in class Friday, February 17.
• Homework 6, due in class Friday, March 2.
• Homework 7, due in class Friday, March 8.

David Eppstein, ICS, UC Irvine.