Fall 2003



Class Schedule and Class Notes

Course Synopsis

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

Class Meetings

The following two days per week (see schedule):

         Tuesday 3:50 PM-5:05 PM

        Thursday 3:50 PM-5:05 PM


Place: Levine Science Research Center(LSRC) Building Room D243 (changed from assigned room LSRC A158)


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


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: