CS 263, Spring 2014: Analysis of Algorithms

This course meets Tuesdays and Thursdays, 12:30 - 1:50 in ICS 180. Coursework will consist of weekly homeworks, graded during the class period on which they are due, and a final exam. Group work on homeworks is permitted and encouraged. The course is primarily aimed at graduate students doing research in discrete algorithms, but other CS graduate students are also welcome.

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 isolation lemma for reducing search problems to problems with unique solutions. Primality testing.
  Homework 1, due April 10.
• Week 2: Balls and bins. Maximum bin size for hash chaining and load balancing. The power of two choices and cuckoo hashing. The birthday paradox and Pollard rho. The coupon collector's problem, the Chernoff bound, and random graphs.
  Homework 2, due April 17.
• Week 3: 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.
  Homework 3, due April 24.
• Week 4: Hardness of approximation. Probabilistically checkable proofs. The unique games conjecture.
  Homework 4, due May 1.
• Week 5: 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.
  Homework 5, due May 8.
• Weeks 6-7: 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. Inclusion-exclusion for graph coloring and bin packing. Measure and conquer, and quasiconvex optimization of backtracking recurrences
  Homework 6, due May 15.
  Homework 7, due May 22.
• Week 8: 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, and color coding.
  Homework 8, due May 29.
• Week 9-10: graph minors, pathwidth, treewidth, bidimensionality, well-quasi-ordering, Courcelle's theorem.
  Homework 9, due June 5
  Homework 10, due June 12.

David Eppstein, ICS, UC Irvine.