Click on the area of interest

Randomized algorithms use a stream of random bits in addition to regular input to make random choices. This randomization plays an integral role in the way the algorithm works. Though in some cases the randomized component may be eliminated, it is with an exponential growth in complexity.

There are two major kinds of randomized algorithms: Monte Carlo and Las Vegas. Randomization is applied in four major ways, depending on the type of algorithm:

• random selection of input (sequential)
• random shunting or routing (distribution)
• random selection of response (sequential)
• controlled random conversion (sequential)

But what if there is an Adversary?

Trade-Offs involved in using randomized algorithms.