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
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:
reading: Mitzenmacher and Upfal, chapters 3 and 4.
- Week 4: Balls and
bins. Maximum bin size for hash
chaining and load
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.
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
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,
and constraint satisfaction.
walks for 3-satisfiability. Dynamic programming for the
traveling salesman problem. Suggested reading: Mitzenmacher and Upfal,
9: Inclusion-exclusion for graph coloring and bin packing.
optimization of backtracking recurrences, and local central limits.
- Weeks 9-10: Parameterized complexity and fixed parameter tractability.
The importance of choosing the right
clique problem parameterized by clique size and by degree.
and vertex cover.
paths, shallow backtracking,
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.
ICS, UC Irvine.