Creating robust software requires the use of efficient algorithms, but programmers seldom think about them until a problem occurs. 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 Ruby 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
With Algorithms in a Nutshell, you'll learn how to improve the performance of key algorithms essential for the success of your software applications.
Chapter 1 Algorithms Matter
Understand the Problem
Experiment if Necessary
The Moral of the Story
Chapter 2 The Mathematics of Algorithms
Size of a Problem Instance
Rate of Growth of Functions
Analysis in the Best, Average, and Worst Cases
Mix of Operations
One Final Point
Chapter 3 Patterns and Domains
Patterns: A Communication Language
Algorithm Pattern Format
Pseudocode Pattern Format
Empirical Evaluation Format
Domains and Algorithms
Manual Memory Allocation
Choosing a Programming Language
Chapter 4 Sorting Algorithms
Criteria for Choosing a Sorting Algorithm
Chapter 5 Searching
Binary Tree Search
Chapter 6 Graph Algorithms
Single-Source Shortest Path
All Pairs Shortest Path
Minimum Spanning Tree Algorithms
Chapter 7 Path Finding in AI
Chapter 8 Network Flow Algorithms
Reflections on Augmenting Paths
Minimum Cost Flow
Chapter 9 Computational Geometry
Convex Hull Scan
Nearest Neighbor Queries
Chapter 10 When All Else Fails
Variations on a Theme
Algorithms That Can Be Wrong, but with Diminishing Probability
Chapter 11 Epilogue
Principle: Know Your Data
Principle: Decompose the Problem into Smaller Problems
Principle: Choose the Right Data Structure
Principle: Add Storage to Increase Performance
Principle: If No Solution Is Evident, Construct a Search
Principle: If No Solution Is Evident, Reduce Your Problem to Another Problem That Has a Solution
Principle: 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 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 (Pagurusbernhardus). More than 500 species of hermit crabs exist. Mostly aquatic, theylive in saltwater in shallow coral reefs and tide pools. Some hermit crabs,however, especially in the tropics, are terrestrial. The robber crab, which can growas large as a coconut, is one such example. Even terrestrial hermit crabs carry asmall amount of water in their shells to help them breathe and keep their abdomensmoist.
Unlike true crabs, hermit crabs do not have a hard shell of their own and mustseek refuge from predators in the abandoned shells of gastropods (snails). Theyare particularly fond of the discarded shells of periwinkles and whelks. As theygrow bigger, they have to find a new shell to inhabit. Leaving any part of themselvesexposed would make them more susceptible to predators; in addition, not having a well-fitted shell stunts their growth. Because intact gastropod shells arelimited, shell competition is an issue.
Hermit crabs are decapod (which literally means "ten footed") crustaceans. Oftheir five pairs of legs, the first two are pincers, or grasping claws, the larger one ofwhich they use to defend themselves and shred food. The smaller claw is used foreating. The second and third pairs of legs help them walk, and the final two pairshelp keep them in their shells.
Characteristic of crustaceans, hermit crabs do not have an internal skeleton but rather ahard exoskeleton of calcium. They also have two compound eyes, two pairs ofantennae (which they use to sense smells and vibration), and three pairs ofmouthparts. Near the base of the their antennae is a pair of green glands thatexcretes waste.
Sea anemones (water-dwelling, predatory animals) are often found attached tohermit crabs' shells. In exchange for transportation and a helping of the hermitcrab'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, andsome mammals (man included).
Known as the "garbage collectors of the sea," hermit crabs will eat mostlyanything, including dead and rotting material on the seashore, and thus they playan important role in seashore cleanup. As omnivores, their diet is varied andincludes everything from worms to organic debris, such as grass and leaves.
I liked this book tremendously, because its small and covers some complex material in an easy to read and comprehend manner. Best of all - the book writing style stays focussed and on point which is great! It goes into sufficient detail for an implementer, and gracefully points out limitations and shortcomings. The authors are especially helpful and provide code and pointers to other references if deeper insight is sought. I even had an email exchange with one of the authors in which they were extremely helpful. I keep this book on my close reach shelf!
Bottom Line Yes, I would recommend this to a friend
When I first encountered algorithms as a student, I was convinced that I would never "get" them. The textbooks that I had been assigned just didn't treat the subject in a way that made sense -- everything was very lofty and theoretical, and it was hard to make the leap from all that theory into code that I could use. I decided to take a chance on revisiting the subject, and I'm glad that "Algorithms in a Nutshell" was the book I chose.
The examples in this book make sense. The game tree discussion in Chapter 7 really locked things in for me -- the example is useful, realistic, and interesting. It's refreshing. I pulled out my old data structures and algorithms textbook and compared their treatments of quicksort, and I still can't make much sense of the overly-theoretical descriptions in the other book. The neat and tidy quicksort fact sheet? Totally resonates with me. The code samples match up well to the analysis, and I'm pleased with my level of understanding now.
In the "not so great" column: this isn't a book for novices. As much as I didn't feel like an expert on algorithms before picking up this book, I was at least aware of the basics. The book is great as a refresher, or for filling in the gaps that an overly-theoretical treatment can cause, but it would probably be overwhelming for a novice programmer or a young student.
Bottom Line Yes, I would recommend this to a friend
This excellent book fills a long unmet need for a practical "how-to" manual on the efficient use of algorithms. This text will be helpful to recent graduates as well as anyone who is faced with the problem of selecting from many potential algorithms as they write their software program. The lead author is a respected professor who writes in a clear easy to understand style. The algorithms can be downloaded from the web. There is also a blog site which explores additional areas not covered in the book. O'Reilly has certainly published a worthwhile and needed text.
Bottom Line Yes, I would recommend this to a friend
Strongest in its disciplined presentation of pseudo-code
Comments about oreilly Algorithms in a Nutshell:
The short history of computer science has sparkled with some extraordinary insights into getting jobs done efficiently. In some ways those jobs are familiar, such as moving the maximum volume of stock from factories through distribution channels to shops. Or sorting a directory of names into alphabetical order. But the solutions that have been found in recent years are genuinely new, and interesting to read about.
This book takes us through the development of several classes of algorithms, such as from "sequential search", through "binary search" to "binary tree search" and a "hash based search". Similarly, it explores sorting into order, finding connected nodes in a graph, planning winning moves in a game, allowing a maximum flow through a network, and geometric problems like the closest points in a set to a new point. The algorithms are presented in order of complexity, building up each topic and explaining both the method and performance of each. Each one covers several pages, including a pseudo-code listing, an actual listing in a language like C++ or Java (supported by the full source code in an archive somewhere), performance statistics and a discussion. The building-up means that many of the algorithms presented are of little interest to practical implementors, however.
The authors are rightly proud of each page that summarises an algorithm. The pseudo code, although variable in style, is mostly very clear and easy to follow. Each algorithm is presented with a diagram demonstrating its progress in an example highlighting the key lines of code. The actual source code can be used if you're implementing it, but since most of the algorithms are presented to teach an approach, using them directly is not necessary. A few lines of pseudo code are too abstract, such as "find median value" or "find augmenting path".
One of the most interesting things about efficient algorithms is the way that they make simplifying assumptions about the data; perhaps that no two items in a set can be unique, or perhaps that data is stored in a balanced structure. Indeed the book begins with a case study of a memory leak analysis tool which was terribly slow to run. It used a tree to store the allocated blocks, but unfortunately the sequence in which blocks were assigned from the heap meant that this tree turned out more like a linked list!
That question of using the right data structures is hinted at repeatedly, and often enforced within the algorithms, but I felt that a programmer working with such problems could benefit from some further guidance through the initial steps of considering "what kind of operations will I want to perform on my data?". Getting the right structure, or caching intermediate results is often vital to efficient performance. The authors recognised this, but didn't help much with the decisions.
Performance is always discussed in terms of run-time and has been measured on just a desktop PC, and a really big PC. There are more embedded devices with relatively tiny resources in use, and a few important data-centre mainframes, which the authors disregard.
The balance of topics in the book seems to be aimed at a student revising algorithm design. But the lectures on floating point inequality, pointers, and the importance of freeing allocated memory, seem out of place. The statistics are not built on the strongest foundations (the methods and explanations are a bit suspect, and some graphs are difficult to read). Some terms are defined in detail, such as "secondary storage" whereas others are not, such as "median".
There are a few errors in diagrams, and an extraordinary non-sequiteur over the turn of a page, from user authentication to graph-spanning paths, which had be flipping the page several times to see if I had missed something. Although locally confusing, they didn't put me off my stride.
The key question that the book sets out to answer, of how to choose the best algorithm for a problem that needs to be delivered on Friday, remains somewhat elusive. There are few real-world examples of data sets that fit the algorithms described, and I felt that more space could have been given to a wider range of algorithms instead of the academic development of a single type of algorithm.
The book ends with an excellent couple of chapters; on the kind of assumptions you can make to convert your data into a well known case, and the "principles" that all software engineering with heavy duty algorithms should consider.
In summary, the book is strongest in its disciplined presentation of pseudo-code and structured sections answering the same questions about each topic. However, the ideal target audience for it would seem to be limited to students, rather than real software engineers.