[Please remove <h1>]

---

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.