Randomized Algorithms

In a randomized algorithm you can toss a fair coin as a step of computation. Alternatively

a bit taking values of 0 and 1 with equal probabilities can be chosen in a single step. More

generally, in a single step an element out of n elements can be chosen with equal probalities

(uniformly at random). In such a setting, our goal can be to design an algorithm that

minimizes run time.