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.
Randomized Algorithms, by Motwani and Raghavan, Cambridge University Press,
1995. This may be supplemented by a package of recent technical papers.
Three hours of lecture per week.
Expectation, conditional probability. Simple examples of randomized algorithms and their analysis.
Evaluating game trees probabilistically. Minmax principle for lower bounds. Derandomization.
Balls into boxes. Randomized selection and sorting. Pairwise independence. Stable marriage and "co-op" situations. The coupon-collector's problem and its uses.
Chernoff bounds. Applications to routing and wiring. Martingales and their applications.
2-satisfiability. Random walks on graphs and applications to connectivity.
Verifying polynomial identities. Fingerprinting and perfect matchings in graphs.
Random treaps. Universal hash functions. Shortest paths. Improving min-cut. Minimum spanning trees.