Randomized and Approximation Algorithms

Catalog description

Introduces two important areas of algorithm design for graduate students. A randomized algorithm is allowed to rely on the outcome of a random experiment in deciding on its next step. In may applications, randomized algorithms are simpler than any deterministic algorithms known, but in several cases, they are in fact more powerful or more efficient than any deterministic algorithms. Covers basic paradigms for randomized algorithm design and analysis, as well as for derandomization.