Algorithms in a Nutshell, 2nd Edition

Preface to the Second Edition

Revising a book for a new edition is always an arduous task. We wanted to make sure that we retained all the good qualities of the first edition, published in 2009, while fixing some of its shortcomings and adding additional material. We continue to follow the principles outlined in the first edition:

• Use real code, not just pseudocode to describe algorithms

• Separate the algorithm from the problem being solved

• Introduce just enough mathematics

• Support mathematical analysis empirically

As we updated this second edition, we reduced the length of our text descriptions and simplified the layout to make room for new algorithms and additional material. We believe we continue to offer a Nutshell perspective on an important area of computer science that has significant impact on practical software systems.

Changes to the Second Edition

In updating this book for the second edition, we followed these principles:

Select New Algorithms

After the publication of the first edition, we often received comments such as “Why was Merge Sort left out?” or “Why didn’t you cover Fast Fourier Transform (FFT)?” It was impossible to satisfy all of these requests, but we were able to add the following algorithms:

• Fortune’s algorithm, to compute the Voronoi Diagram for a set of points (“Voronoi Diagram”)

• Merge Sort, for both internal memory data as well as external files (“Merge Sort”)

• Multithreaded Quicksort (“Parallel Algorithms”)

• AVL Balanced Binary ...