Randomization

The history of mankind using the notion of random is widely reflected in gambling or insurance and in the fields of computer science as well through a number of analytic examples.

In the algorithm design, randomization plays a pivot role in probabilistic algorithm designs in two ways of which we care about:

• Classic algoritm is feeded with randomly generated inputs, in other words, the average inputs are studied to offer average-case analysis

• Worst-case inputs are provided as always to the algorithm in the classical way, but processed in a random manner. The internal execution model dealing with randomization is a typical randomized algorithm.

Table of Contents

• Discrete Probability - probability analysis, indicator random variable and several statistics definitions covered.

• Randomized Algorithms - median-finding problem, ith order statistic finding problem are analyzed and solved randomly and deterministic.

• Reservoir Sampling - an introduction to a common technique in data processing.