CPS237 |
|||
|
Spring
2002 |
|
RANDOMIZED ALGORITHMS |
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.
Derandomization. k-wise
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
Two of
the following three days per week (see schedule; the updated times start
1/16/2002):
Monday 3:45PM-5:00PM (officially listed as 3:55PM-5:10PM)
Wednesday
10:25AM-11:40AM (officially listed
as 10:30AM-11:45AM)
Friday 10:25AM-11:40AM (officially
listed as 10:30AM-11:45AM)
Place:
Levine Science Research Center(LSRC) Building D243
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: