Algorithms For Dummies

17

---

322

 

   

  PART 5 

 Challenging Difficult Problems

From a historical perspective, randomized algorithms are a recent innovation, 

because the first algorithm of this kind, the closest-pair algorithm (which deter-

mines the pair of points, among many on a geometric plane, with the smallest 

distance between the points without having to compare them all) was developed 

by Michael Rabin in 1976. That first algorithm was followed the next year by the 

randomized primality test (an algorithm for determining whether a number is a 

composite or a probable prime number), by Robert M. Solovay and Volker Stras-

sen.  Soon  after,  applications  in  cryptography  and  distributed  computing  made 

randomization more popular and the subject of intense research, although the 

field is still new and uncharted.

Randomization makes finding a solution simpler, trading time against complex-

ity. Simplifying tasks isn’t its only advantage: Randomization saves resources and 

operates in a distributed way with a reduced need for communication and coordi-

nation. This chapter introduces you to the information needed to understand how 

enriching your algorithms with randomness can help solve problems (the chapter 

uses the term injecting randomness, as if it were a cure). Even more applications 

wait in the following chapters, so this chapter also discusses key topics such as 

probability basics, probability distributions, and Monte Carlo simulations.