CS 761 Randomized Algorithmsy


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.


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.

Campaign Waterloo

David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x33293
Fax: 519-885-1208

Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics

Valid HTML 4.01!Valid CSS! Last modified: Friday, 01-Jun-2012 11:00:32 EDT