Algorithms For Dummies, 2nd Edition

Chapter 17

Using Randomized Algorithms

IN THIS CHAPTER

Understanding how randomness can prove smarter than more reasoned ways

Introducing key ideas about probability and its distributions

Discovering how a Monte Carlo simulation works

Learning about quick select and revisiting quick sort algorithms

Random number generators are a key function in computing and play an important role in the algorithmic techniques discussed in this part of the book. As described in the first part of the chapter, randomization isn’t just for gaming or gambling; people also employ it to solve a large variety of problems. Randomization sometimes proves more effective during optimization than other techniques, and in obtaining the right solution than more reasoned ways. It helps different techniques work better, for example local search, simulated annealing to heuristics, cryptography, and distributed computing (with cryptography for concealing information being the most critical).

The “Understanding how probability works” section illustrates the basic principles of probability and then explains how probability ...