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, k-wise 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. Game-Theoretic Models of Computation, min-max 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, k-server 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
[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: