CPS237 


Spring
2006 

RANDOMIZED ALGORITHMS 
1.
Introduction: Examples of
randomized algorithms: quicksort, BSP, mincut, partitioning, secretly computing
an average, verifying matrix product, kwise independence.
2.
Randomized
Complexity Theory. models of randomized computation, Las Vegas and Monte
Carlo algorithms, complexity classes, derandomization, discrepancy
3.
Randomized
Games: Introduction to Game Theory and
Equilibria. GameTheoretic Models of Computation, minmax
principle, and applications.
4.
Probability Moments
and Tail Bounds: Linearity of expectation, Markov and Chebyshev
inequalities, occupancy problem, randomized selection, coupon collector's
problem
5.
Probabilistic
methods: random graphs, expanders, and Lovasz local lemma.
6.
Randomized Data
structures. Randomized search trees, universal hashing, and skip
lists.
7.
Randomized
Algebraic Methods: Hashing and Fingerprinting Polynomials.
Applications to perfect matching and string searching.
8.
Randomized Graph
algorithms. Shortest paths, minimum spanning trees, Min cut,
independent sets, dynamic graph algorithms
9.
Randomized Geometric
algorithms. Applications of random sampling of geometric objects,
randomized incremental algorithms, and linear programming
10. Markov Chains and Random Walks. Markov chains,
random walks, electric networks, rapidly mixing Markov chains, random walks on
expanders. Applications to Approximate counting, approximating
the permanent, and volume estimation
11. Randomized Online algorithms. Paging problem,
kserver problem, adversary models
12. Randomized Parallel and
Distributed Algorithms: Parallel Sorting, randomized distributed
communication
13. Randomized Number Theory
Algorithms: Number Theoretic rings and fields, integer factoring
and primality testing.
14. Quantum Computation: Brief
overview of quantum computing, quantum gates, and quantum algorithms.
John H. Reif, Professor of Computer Science
The
following two days per week (see schedule):
Tuesday 11:40 AM12:55 PM
Thursday 11:40 AM12:55 PM
Place:
Levine Science Research Center(LSRC) Building Room D243
Textbooks
[MR] Rajeev Motwani and
Prabhakar Raghavan, Randomized Algorithms, Published by Cambridge University Press, ISBN: 0521474655, 492
pages, June 1995.
[MU]
Michael Mitzenmacher and Eli Upfal, Probability and Computing:
Randomized Algorithms and Probabilistic Analysis, Published by Cambridge
University Press, ISBN: 0521835402, Paperback, 352 pages, December 2004.
CPS 230 or equivalent.
Class
grade will be based on: