# Randomized Algorithms

## Random sampling

• This is the idea behind opinion polling, where we sample a small number of people as a proxy for the full population. The result should be representative for the full set.

## Randomized hashing

• The worst-case set of keys that all get hashed to the same bucket.
• Suppose we randomly select our hash function from a large family of good ones as the first step of our algorithm.
• Randomization can also be used to drive search tech- niques such as simulated annealing.

## Classification of randomized algorithms

### 1. Las Vegas algorithms

• Guarantee correctness
• Usually (but not always) efficient
• i.e. Quicksort

### 2. Monte Carlo algorithms

• Provably efficient
• Usually (but not always correct)