CPS237 


Fall
2003 

RANDOMIZED ALGORITHMS 
1.
Introduction. Examples of
randomized algorithms, models of computation, Las Vegas and Monte Carlo
algorithms, complexity classes, minmax 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.
Derandomization. kwise
independence, probabilistic methods, discrepancy, derandomization in parallel
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.
Markov Chains and
Random Walks. Markov chains, random walks, electric networks,
rapidly mixing Markov chains, random walks on expanders
10. Approximate counting. Monte Carlo
methods, approximating the permanent, volume estimation
11. Online algorithms. Paging problem,
$k$server problem, adversary models
12. Number theoretic algorithms. Groups and
fields, quadratic residues, RSA cryptosystem, polynomial roots and factoring,
primality testing
John H. Reif, Professor of Computer Science
The
following two days per week (see schedule):
Tuesday 3:50 PM5:05 PM
Thursday
3:50 PM5:05 PM
Place:
Levine Science Research Center(LSRC) Building Room D243 (changed from assigned
room LSRC A158)
Textbook
Rajeev Motwani Prabhakar Raghavan, Randomized
Algorithms, Published by
Cambridge University Press, ISBN:
0521474655, 492 pages. June 1995.
CPS 230 or equivalent.
Class
grade will probably be based on: