# CS 761 Randomized Algorithmsy

## Objectives

To provide the student with a thorough introduction to the design and analysis
of algorithms that make use of randomization.

Students are expected to have basic knowledge of algorithm design and analysis.

## References

Randomized Algorithms, by Motwani and Raghavan, Cambridge University Press,
1995. This may be supplemented by a package of recent technical papers.

## Schedule

Three hours of lecture per week.

## Outline

### Review of Basic Probability and Introduction to Randomized Algorithms

Expectation, conditional probability. Simple examples of randomized algorithms
and their analysis.

### Game Theoretic Techniques (3 hrs)

Evaluating game trees probabilistically. Minmax principle for lower bounds.
Derandomization.

### Uses of Markov and Chebyshev Inequalities (6 hrs)

Balls into boxes. Randomized selection and sorting. Pairwise independence.
Stable marriage and "co-op" situations. The coupon-collector's problem and its
uses.

### Tail Inequalities (6 hrs)

Chernoff bounds. Applications to routing and wiring. Martingales and their
applications.

### Markov Chains and Random Walks (6 hrs)

2-satisfiability. Random walks on graphs and applications to connectivity.

### Algebraic Techniques (3 hrs)

Verifying polynomial identities. Fingerprinting and perfect matchings in graphs.

### Data Structures and Graph Algorithms (6 hrs)

Random treaps. Universal hash functions. Shortest paths. Improving min-cut.
Minimum spanning trees.