CPS 296: Course Synopsis

  1. Introduction. Examples of randomized algorithms, models of computation, Las Vegas and Monte Carlo algorithms, complexity classes, min-max principle.

  2. Moment and deviation. Linearity of expectation, Markov and Chebyshev inequalities, occupancy problem, randomized selection, coupon collector's problem

  3. Tail inequalities. The Chernoff bound, routing and wiring problems

  4. Probabilistic methods. Deletion methods, random graphs, expanders, Lov\'{a}sz local lemma

  5. Markov Chains and Random Walks. Markov chains, random walks, electric networks, rapidly mixing Markov chains, random walks on expanders

  6. Data structures. Randomized search trees, hashing, skip lists;

  7. Graph algorithms. Shortest paths, minimum spanning trees, Min cut, independent sets, dynamic graph algorithms

  8. Geometric algorithms. Random sampling, randomized incremental algorithms, linear programming

  9. Approximate counting. Monte Carlo methods, approximating the permanent, volume estimation

  10. Online algorithms. Paging problem, $k$-server problem, adversary models

  11. Number theoretic algorithms. Groups and fields, quadratic residues, RSA cryptosystem, polynomial roots and factoring, primality testing

  12. Derandomization. k-wise independence, probabilistic methods, discrepancy, derandomization in parallel

Agarwal's Home Page

CPS 296 Homepage.

Pankaj Kumar Agarwal
Tues Jan. 13 1998