Algorithm Design: Randomized Algorithms

Randomized algorithms

Suppose you hear your phone ringing somewhere in your house. If you happen to have a coin, then before even starting to search for the phone, you could toss it to decide whether you want to start your search on the first floor if the coin comes up heads, or on the second floor if the coin comes up tails. If you also happen to have a die, then after deciding on the second floor of your mansion, you could roll it to decide in which of the six rooms on the second floor to start your search.

Although tossing coins and rolling dice may be a fun way to search for the phone, it is certainly not the intuitive thing to do, nor is it at all clear whether it gives you any algorithmic advantage over a deterministic algorithm.

Our programming challenges will help you learn why randomized algorithms are useful and why some of them have a competitive advantage over deterministic algorithms.

QuickSort algorithm

To give an example of a randomized algorithm, we will first discuss a fast sorting technique called $QuickSort.$ It selects an element $m$ (typically the first) from an array $c$ and simply partitions the array into two subarrays: $c_{small}$, containing all elements from $c$ that are smaller than $m$; and $c_{large}$ containing all elements larger than $m$.

This partitioning can be done in linear time, and by following a divide-and-conquer strategy, $QuickSort$ recursively sorts each subarray in the same way. The sorted list is easily created by simply concatenating the sorted $c_{small}$, element $m$, and the sorted $c_{large}$.

---

 $QuickSort(c)$:
if $c$ consists of a single element:
        return $c$
 $m \leftarrow c[1]$
 determine the set of elements $c_{small}$ smaller than $m$
 determine the set of elements $c_{large}$ larger than $m$
 $QuickSort(c_{small})$ ...