What’s in This Book?

In this volume, I don’t simply cover a laundry list of additional data structures and algorithms. Yes, I cover those too, but the main focus of this book is to help you become more proficient in the analysis and design of algorithms.

Specifically, you’ll find that there are three main themes that are threaded throughout this volume:

Going beyond Big O. While Big O notation is a useful and even crucial tool for algorithmic analysis, it has some significant limitations when applied to the real world. I’ll show you where Big O notation falls short and how to use benchmarking and other forms of analysis to ensure that your code will truly be efficient in real life.
Randomization. There are many components you can integrate into an algorithm you’re designing. One of the most useful but perhaps surprising of these components is randomness. We begin with the basics of randomization algorithms and then see how they can make your code more efficient in a wide variety of scenarios.
Hardware. An all-too-often overlooked factor in algorithm design is how your computer’s hardware setup can impact the efficiency of your code. Sure, in an academic vacuum, how much memory your computer has shouldn’t affect the Big O classification of an algorithm. However, in truth, a computer’s hardware can have a significant impact on how fast your code will perform when you run it.

With regard to specific data structures and algorithms, here’s a list of some of them that you’ll encounter. I’ve listed them in the order in which they’re presented in the book:

Mergesort
Fisher-Yates Shuffle
Load balancing with the power of two choices
LRU caches
Red-black trees
Randomized treaps
External-memory algorithms
B-trees
Merging K sorted lists
M/B-Way Mergesort
Monte Carlo algorithms
Random sampling
Fermat’s Primality Test
Randomized hashing
Hash function families
Rabin-Karp substring search
Sliding-window technique
Boolean arrays
Bit vectors
Bit manipulation
Bloom filters

In addition, each chapter contains exercises that will help you practice everything you’ve learned. Solutions to each exercise can be found at the back of the book.

A handful of exercises are special. You’ll see that I marked some as being a “Puzzle” or “Exploration” or the like. You aren’t expected to know the answer even if you’ve mastered the chapter. Instead, they ask you to apply ingenuity and see if you can stretch yourself even further. Occasionally, I’ll also mark an exercise as a “New Concept” if I’ll be teaching a brand-new idea in the associated solution.