CPS237 


Spring
2008 

RANDOMIZED ALGORITHMS 
Randomized Algorithms. Models of
computation, Las Vegas and Monte Carlo algorithms, linearity of expectation,
Markov and Chebyshev inequalities and their applications, Chernoff bound and
its applications, probabilistic methods, expanders,random walks and rapidly
mixing Markov chains. Randomized algorithms for data structures, graph
problems, geometric problems,
online problems, approximation, computational algebra, number theory and
cryptography.
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):
Monday 1:00 PM 2:30 PM
Wednesday 1:00 PM 2:30 PM
Friday 1:00 PM 2:30 PM
Place: North
Building, Room 306
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: