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.