Spring 2006



Class Schedule and Class Notes

Course Synopsis

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

Class Meetings

The following two days per week (see schedule):

         Tuesday 11:40 AM-12:55 PM

        Thursday 11:40 AM-12:55 PM


Place: Levine Science Research Center(LSRC) Building Room D243


The course provides an introduction to randomized algorithms and probabilistic analysis of algorithms.


[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: