Wrapping Up

In this chapter, you learned what randomization algorithms are and how they can optimize various algorithms, such as Quicksort and building binary search trees. You looked at the fundamentals of how computers generate random numbers and the right way to use random numbers to shuffle an array. You also discovered how the power of two choices uses randomization to achieve an ideal load-balancing algorithm.

But even with all this, we’ve only begun to scratch the surface of randomization algorithms. In fact, randomization algorithms will play an important role throughout many of the remaining chapters of this book.

In the next chapter, we’re going to explore a fundamental set of data structures and algorithms surrounding the idea of caching, which can drastically improve the speed of your code. And we’ll extend the ideas of this chapter to explore how randomization can be used to optimize caching.