Creating robust software requires the use of efficient algorithms, but programmers seldom think about them until a problem occurs. This updated edition of Algorithms in a Nutshell describes a large number of existing algorithms for solving a variety of problems, and helps you select and implement the right algorithm for your needs—with just enough math to let you understand and analyze algorithm performance.
With its focus on application, rather than theory, this book provides efficient code solutions in several programming languages that you can easily adapt to a specific project. Each major algorithm is presented in the style of a design pattern that includes information to help you understand why and when the algorithm is appropriate.
With this book, you will:
Solve a particular coding problem or improve on the performance of an existing solution
Quickly locate algorithms that relate to the problems you want to solve, and determine why a particular algorithm is the right one to use
Get algorithmic solutions in C, C++, Java, and Python with implementation tips
Learn the expected performance of an algorithm, and the conditions it needs to perform at its best
Discover the impact that similar design decisions have on different algorithms
Learn advanced data structures to improve the efficiency of algorithms
Chapter 1Thinking in Algorithms
Understand the Problem
Chapter 2The Mathematics of Algorithms
Size of a Problem Instance
Rate of Growth of Functions
Analysis in the Best, Average, and Worst Cases
Chapter 3Algorithm Building Blocks
Algorithm Template Format
Pseudocode Template Format
Empirical Evaluation Format
Chapter 4Sorting Algorithms
Criteria for Choosing a Sorting Algorithm
Sorting without Comparisons
Sorting with Extra Storage
String Benchmark Results
Binary Search Tree
Chapter 6Graph Algorithms
Single-Source Shortest Path
Dijkstra’s Algorithm for Dense Graphs
Comparing Single-Source Shortest-Path Options
All-Pairs Shortest Path
Minimum Spanning Tree Algorithms
Final Thoughts on Graphs
Chapter 7Path Finding in AI
Comparing Search-Tree Algorithms
Chapter 8Network Flow Algorithms
Reflections on Augmenting Paths
Minimum Cost Flow
Chapter 9Computational Geometry
Convex Hull Scan
Computing Line-Segment Intersections
Chapter 10Spatial Tree Structures
Nearest Neighbor Queries
Spatial Tree Structures
Nearest Neighbor Queries
Chapter 11Emerging Algorithm Categories
Variations on a Theme
Chapter 12Epilogue: Principles of Algorithms
Know Your Data
Decompose a Problem into Smaller Problems
Choose the Right Data Structure
Make the Space versus Time Trade-Off
Construct a Search
Reduce Your Problem to Another Problem
Writing Algorithms Is Hard—Testing Algorithms Is Harder
George Heineman is an Associate Professor of Computer Science at WPI. His research interests are in Software Engineering. He co-edited the 2001 book "Component-Based Software Engineering: Putting the Pieces Together". He was the Program Chair for the 2005 International Symposium on Component-Based Software Engineering.
Gary Pollice is a self-labeled curmudgeon (that's a crusty, ill- tempered, usually old man) who spent over 35 years in industry trying to figure out what he wanted to be when he grew up. Even though he hasn't grown up yet, he did make the move in 2003 to the hallowed halls of academia where he has been corrupting the minds of the next generation of software developers with radical ideas like, "develop software for your customer, learn how to work as part of a team, design and code quality and elegance and correctness counts, and it's okay to be a nerd as long as you are a great one." Gary is also a co-author of Head First Object-Oriented Analysis and Design.Gary is a Professor of Practice (meaning he had a real job before becoming a professor) at Worcester Polytechnic Institute. He went to WPI because he was so impressed with the WPI graduates that he's worked with over the years. He lives in central Massachusetts with his wife, Vikki, and their two dogs, Aloysius and Ignatius. When not working on geeky things he ... well he's always working on geeky things. You can see what he's up to by visiting his WPI home page at http://web.cs.wpi.edu/~gpollice/. Feel free to drop him a note and complain or cheer about the book.
Stanley Selkow received a BS in Electrical Engineering from Carnegie Institute of Technology in 1965, and then a Ph.D. in the same area from the University of Pennsylvania in 1970. From 1968 to 1970 he was in the Public Health Service at the National Institutes of Health at Bethesda Maryland. Since 1970 he has been on the faculty at universities in Knoxville TN and Worcester MA, as well as Montreal, Chonqing, Lausanne and Paris. His major research has been in graph theory and algorithm design.
The animal on the cover of Algorithms in a Nutshell is a hermit crab (Pagurus bernhardus). More than 500 species of hermit crabs exist. Mostly aquatic, they live in saltwater in shallow coral reefs and tide pools. Some hermit crabs, however, especially in the tropics, are terrestrial. The robber crab, which can grow as large as a coconut, is one such example. Even terrestrial hermit crabs carry a small amount of water in their shells to help them breathe and keep their abdomens moist.
Unlike true crabs, hermit crabs do not have a hard shell of their own and must seek refuge from predators in the abandoned shells of gastropods (snails). They are particularly fond of the discarded shells of periwinkles and whelks. As they grow bigger, they have to find a new shell to inhabit. Leaving any part of themselves exposed would make them more susceptible to predators; in addition, not having a well-fitted shell stunts their growth. Because intact gastropod shells are limited, shell competition is an issue.
Hermit crabs are decapod (which literally means "ten footed") crustaceans. Of their five pairs of legs, the first two are pincers, or grasping claws, the larger one of which they use to defend themselves and shred food. The smaller claw is used for eating. The second and third pairs of legs help them walk, and the final two pairs help keep them in their shells.
Characteristic of crustaceans, hermit crabs do not have an internal skeleton but rather a hard exoskeleton of calcium. They also have two compound eyes, two pairs of antennae (which they use to sense smells and vibration), and three pairs of mouthparts. Near the base of their antennae is a pair of green glands that excretes waste.
Sea anemones (water-dwelling, predatory animals) are often found attached to hermit crabs' shells. In exchange for transportation and a helping of the hermit crab's leftovers, sea anemones help to ward off the hermit crab's marine predators, such as fish and octopus. Other predators include birds, other crabs, and some mammals (man included).
Known as the "garbage collectors of the sea," hermit crabs will eat mostly anything, including dead and rotting material on the seashore, and thus they play an important role in seashore cleanup. As omnivores, their diet is varied and includes everything from worms to organic debris, such as grass and leaves.
The cover image is from Johnson's Library of Natural History, Volume 2. The cover font is Adobe ITC Garamond. The text font is Linotype Birka; the heading font is Adobe Myriad Condensed; and the code font is LucasFont's TheSansMonoCondensed.