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 Quickselect and revisiting Quicksort 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. Randomization isn’t just for gaming or for gambling, but people 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, from local search and simulated annealing to heuristics, cryptography, and distributed computing (with cryptography for concealing information being the most critical).
You can find randomization embedded into unexpected everyday tools. The robot vacuum cleaner Roomba (designed by a company founded by the Massachusetts Institute of Technology ...