As we have introduced the general methods used in the design of randomized algorithms, next we will give several examples that illustrates the advantages of using randomization in certain algorithms. The two classic examples discussed below represent the sequential and distributed algorithms respectively. More importantly, their randomized solutions have made use of some of the techniques introduced before, such as input randomization and breaking symmetry. We will soon see how randomization helps to solve problems more efficiently and more powerfully.

Sequential Algorithms - The Sock Sorting Problem

Distributed Algorithms - The Dining Philosopher Problem

From these examples, we have seen in the sequential case of sock selection that randomization is used to obtain faster algorithms (sometimes at the expense of absolute accuracy) or to guarantee that the worst-case performance of an algorithm is no worse than the algorithm's expected performance. However, there still exists a feasible deterministic algorithm solution. But in the latter example, there is no deterministic solution at all. We have no choice but to toss coins. Randomization becomes the only way to approach those problems which need a strategy to break the symmetry.