Algorithms-1 09

Random/randomized algorithms

An algorithm is a “black box” that receives a collection of bits (input) and yields a collection of bits (output) In addition to that, a randomized algorithm receives an infinite random string of bits that is used to make randomized decisions (random, ) In deterministic case, for the given input, the algorithm will always yield the same output by executing the exact same sequence of operations.

	Deterministic	Random Variable
Deterministic	Deterministic algorithms	Monte-Carlo algorithms
Random Variable	Las Vegas algorithms	Atlantic City algorithms

Las Vegas (LV) algorithms

Monte Carlo (MC) algorithms

Verifying BMM

Input

Output

Naive solution

Monte-Carlo algorithm

Let us first try to solve this problem in with probability of at least

An improvement of this algorithm (an amplification of probability) would be to simply run this algorithm multiple times, independently (why?) How many times is enough?

Paranoid QuickSort (Las Vegas)

Let us augment the classic QuickSort to always choose a “good” pivot, meaning that What is the expected runtime of this algorithm?

Expected runtime of any randomized QuickSort

Bucket sort (Atlantic city)

Input

Output

Atlantic city algorithm