CPS 296: Course Synopsis
- 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.
Pankaj Kumar Agarwal
Tues Jan. 13 1998