Home Bookmarks Papers Blog
CS 497, Fall 2000
Prof. Sariel Har-peled

Randomized Algorithms and Combinatorial Optimization

Section SHP, #08943
3:30 - 4:45 TuTh, 106B3 Engineering Hall

Prerequisite: CS 373
Credit: 3/4 or 1 Unit

Using randomization in the design of algorithms had resulted in a huge
collection of efficient and simple algorithms for various problems. In
the first part of this course, we would present some of those
algorithms: quicksort, Chernoff bounds, Minimum-Cut Algorithm,
Universal and perfect hashing, VC Dim, Clarkson-Shor technique.

In the second (and probably considerably shorter) part of the course,
we would look into the discrepancy method. The discrepancy method aims
to resolve one of the burning issues in theoretical computer science:
Does randomization really help? The discrepancy method may offer an
answer through the study of distribution irregularieties, also knon as
discrepancy theory. By drawing upon a wealth of mathematical
techniques, this approach has met with consdierably success.


  1. Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan.
  2. The Discrepancy Method, Bernard Chazelle.