Algorithms in a Nutshell
by George T. Heineman , Gary Pollice , and Stanley Selkow
Copyright 2016 George Heineman, Gary Pollice and Stanley Selkow. All rights reserved.
Printed in the United States of America.
Published by OReilly Media, Inc. , 1005 Gravenstein Highway North, Sebastopol, CA 95472.
OReilly books may be purchased for educational, business, or sales promotional use. Online editions are also available for most titles (http://safaribooksonline.com). For more information, contact our corporate/institutional sales department: 800-998-9938 or corporate@oreilly.com .
- Editors: Andy Oram and Mary Treseler
- Production Editor: Colleen Lobner
- Copyeditor: Christina Edwards
- Proofreader: Jasmine Kwityn
- Indexer: Judy McConville
- Interior Designer: David Futato
- Cover Designer: Karen Montgomery
- Illustrator: Rebecca Demarest
- October 2008: First Edition
- March 2016: Second Edition
Revision History for the Second Edition
- 2016-03-09: First Release
See http://oreilly.com/catalog/errata.csp?isbn=9781491948927 for release details.
Nutshell Handbook, the Nutshell Handbook logo, and the OReilly logo are registered trademarks of OReilly Media, Inc. Algorithms in a Nutshell, the cover image of a hermit crab, and related trade dress are trademarks of OReilly Media, Inc.
While the publisher and the authors have used good faith efforts to ensure that the information and instructions contained in this work are accurate, the publisher and the authors disclaim all responsibility for errors or omissions, including without limitation responsibility for damages resulting from the use of or reliance on this work. Use of the information and instructions contained in this work is at your own risk. If any code samples or other technology this work contains or describes is subject to open source licenses or the intellectual property rights of others, it is your responsibility to ensure that your use thereof complies with such licenses and/or rights.
978-1-491-94892-7
[LSI]
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 didnt you cover Fast Fourier Transform (FFT)? It was impossible to satisfy all of these requests, but we were able to add the following algorithms:
Fortunes algorithm, to compute the Voronoi Diagram for a set of points ()
Merge Sort, for both internal memory data as well as external files ()
Multithreaded Quicksort ()
AVL Balanced Binary Tree implementation ()
A new Spatial Algorithms chapter () contains R-Trees and Quadtrees
In total, the book covers nearly 40 essential algorithms.
Streamline Presentation
To make room for the new material, we revised nearly every aspect of the first edition. We simplified the template used to describe each algorithm and reduced the accompanying descriptions.
Add Python Implementations
Rather than reimplement existing algorithms in Python, we intentionally used Python to implement most of the new algorithms added.
Manage Code Resources
The code for the first edition was made available as a ZIP file. We have since transitioned to a GitHub repository. Over the years we improved the quality of the code and its documentation. We have incorporated a number of blog entries that were written after the publication of the first edition. There are over 500 unit test cases and we use code coverage tools to ensure coverage of 99% of our Java code. In total, the code repository consists of over 110 KLOC.
Audience
We intend this book to be your primary reference when seeking practical information on how to implement or use an algorithm. We cover a range of existing algorithms for solving a large number of problems and adhere to the following principles:
When describing each algorithm, we use a stylized template to properly frame each discussion and explain the essential points of each algorithm
We use a variety of languages to implement each algorithm (including C, C++, Java, and Python). In doing so, we make concrete the discussion of algorithms and speak using languages you are already familiar with
We describe the expected performance of each algorithm and empirically provide evidence to support these claims
We intend this book to be most useful to software practitioners, programmers, and designers. To meet your objectives, you need access to a quality resource that explains real solutions to practical algorithms you need to solve real problems. You already know how to program in a variety of programming languages. You know about the essential computer science data structures, such as arrays, linked lists, stacks, queues, hash tables, binary trees, and undirected and directed graphs. You dont need to implement these data structures, since they are typically provided by code libraries.
We expect you will use this book to learn about tried and tested solutions to solve problems efficiently. You will learn some advanced data structures and novel ways to apply standard data structures to improve the efficiency of algorithms. Your problem-solving abilities will improve when you see the key decision for each algorithm that make for efficient solutions.
Conventions Used in This Book
The following typographical conventions are used in this book:
Code
All code examples appear in this typeface
.
This code is replicated directly from the code repository and reflects real code. All code listings are pretty-printed to highlight
the appropriate syntax of the programming language.
ItalicIndicates key terms used to describe algorithms and data structures. Also used when referring to variables within a pseudocode description of an example.
Constant width
Indicates the name of actual software elements within an implementation, such as a Java class, the name of an array within a C implementation, and constants such as true
or false
.
We cite numerous books, articles, and websites throughout the book. These citations appear in text using parentheses, such as (Cormen et al., 2009), and each chapter closes with a listing of references used within that chapter. When the reference citation immediately follows the name of the author in the text, we do not duplicate the name in the reference. Thus, we refer to the