**Introduction.**Examples of randomized algorithms, models of computation, Las Vegas and Monte Carlo algorithms, complexity classes, min-max principle.**Moment and deviation.**Linearity of expectation, Markov and Chebyshev inequalities, occupancy problem, randomized selection, coupon collector's problem**Tail inequalities.**The Chernoff bound, routing and wiring problems**Probabilistic methods.**Deletion methods, random graphs, expanders, Lov\'{a}sz local lemma**Markov Chains and Random Walks.**Markov chains, random walks, electric networks, rapidly mixing Markov chains, random walks on expanders**Data structures.**Randomized search trees, hashing, skip lists;**Graph algorithms.**Shortest paths, minimum spanning trees, Min cut, independent sets, dynamic graph algorithms**Geometric algorithms.**Random sampling, randomized incremental algorithms, linear programming**Approximate counting.**Monte Carlo methods, approximating the permanent, volume estimation**Online algorithms.**Paging problem, $k$-server problem, adversary models**Number theoretic algorithms.**Groups and fields, quadratic residues, RSA cryptosystem, polynomial roots and factoring, primality testing**Derandomization.**k-wise independence, probabilistic methods, discrepancy, derandomization in parallel

Agarwal's Home Page

CPS 296 Homepage.

Tues Jan. 13 1998