Algorithms in a Nutshell (In a Nutshell (O'Reilly)) [Paperback]

George T. Heineman (Author), Gary Pollice (Author), Stanley Selkow (Author)

Book Description

Series: In a Nutshell (O'Reilly) | Publication Date: October 21, 2008

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.

Editorial Reviews

About the Author

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.

Product Details

• Paperback: 368 pages
• Publisher: O'Reilly Media; 1 edition (October 21, 2008)
• Language: English
• ISBN-10: 059651624X
• ISBN-13: 978-0596516246
• Product Dimensions: 8.9 x 5.9 x 0.9 inches
• Shipping Weight: 1.2 pounds (View shipping rates and policies)
• Average Customer Review: 4.0 out of 5 stars  See all reviews (16 customer reviews)
• Amazon Best Sellers Rank: #170,601 in Books (See Top 100 in Books)

Customer Reviews

Most Helpful Customer Reviews

91 of 98 people found the following review helpful:

5.0 out of 5 stars A great supplemental book on Algorithms, October 25, 2008

By 

calvinnme - See all my reviews
(HALL OF FAME REVIEWER)    (VINE VOICE)    (TOP 50 REVIEWER)   

This review is from: Algorithms in a Nutshell (In a Nutshell (O'Reilly)) (Paperback)

This new book on algorithms from O'Reilly is a breath of fresh air. Most books on the subject fall into two categories: very dense tomes full of math and heavy on sometime unintelligible pseudocode, or books that basically just give you recipes without much understanding. The second category is the "give a man a fish" type, the first type is the "teach a man to fish, but use ALGOL to do it". Even the author, in his preface, recognizes that this is not the one book on algorithms you'd need if you were on a desert island. On a desert island you have plenty of time and you can carefully digest Cormen's Introduction to Algorithms. However, you're not on a desert island, are you? Thus this book is the link between Cormen's careful theoretical approach that takes time, and books that amount to code dumps.

The first six chapters amount to supplements on the basics of Theory of Algorithm courses: mathematics foundations, sorting, searching, and graphing algorithms. The mathematics here is somewhat lacking, but then the author is assuming you have other books on the subject - this is a book for ramping up quickly. The rest of the book is rather specialized, considering specific families of algorithms that are topical in these times such as path finding in AI, computational geometry, and network flow. They fill in the blanks missing in the standard textbooks. Plus there is plenty of code - real code, not pseudocode - that you can put to work quickly. The product description lacks the table of contents, so I list that next:

Part I: I
Chapter 1. Algorithms Matter
Section 1.1. Understand the Problem
Section 1.2. Experiment if Necessary
Section 1.3. Side Story
Section 1.4. The Moral of the Story
Section 1.5. References
Chapter 2. The Mathematics of Algorithms
Section 2.1. Size of a Problem Instance
Section 2.2. Rate of Growth of Functions
Section 2.3. Analysis in the Best, Average, and Worst Cases
Section 2.4. Performance Families
Section 2.5. Mix of Operations
Section 2.6. Benchmark Operations
Section 2.7. One Final Point
Section 2.8. References
Chapter 3. Patterns and Domains
Section 3.1. Patterns: A Communication Language
Section 3.2. Algorithm Pattern Format
Section 3.3. Pseudocode Pattern Format
Section 3.4. Design Format
Section 3.5. Empirical Evaluation Format
Section 3.6. Domains and Algorithms
Section 3.7. Floating-Point Computations
Section 3.8. Manual Memory Allocation
Section 3.9. Choosing a Programming Language
Section 3.10. References
Part II: II
Chapter 4. Sorting Algorithms
Section 4.1. Overview
Section 4.2. Insertion Sort
Section 4.3. Median Sort
Section 4.4. Quicksort
Section 4.5. Selection Sort
Section 4.6. Heap Sort
Section 4.7. Counting Sort
Section 4.8. Bucket Sort
Section 4.9. Criteria for Choosing a Sorting Algorithm
Section 4.10. References
Chapter 5. Searching
Section 5.1. Overview
Section 5.2. Sequential Search
Section 5.3. Binary Search
Section 5.4. Hash-based Search
Section 5.5. Binary Tree Search
Chapter 6. Graph Algorithms
Section 6.1. Overview
Section 6.2. Depth-First Search
Section 6.3. Breadth-First Search
Section 6.4. Single-Source Shortest Path
Section 6.5. All Pairs Shortest Path
Section 6.6. Minimum Spanning Tree Algorithms
Section 6.7. References
Chapter 7. Path Finding in AI
Section 7.1. Overview
Section 7.2. Depth-First Search
Section 7.3. Breadth-First Search
Section 7.4. A*Search
Section 7.5. Comparison
Section 7.6. Minimax
Section 7.7. NegMax
Section 7.8. AlphaBeta
Section 7.9. References
Chapter 8. Network Flow Algorithms
Section 8.1. Overview
Section 8.2. Maximum Flow
Section 8.3. Bipartite Matching
Section 8.4. Reflections on Augmenting Paths
Section 8.5. Minimum Cost Flow
Section 8.6. Transshipment
Section 8.7. Transportation
Section 8.8. Assignment
Section 8.9. Linear Programming
Section 8.10. References
Chapter 9. Computational Geometry
Section 9.1. Overview
Section 9.2. Convex Hull Scan
Section 9.3. LineSweep
Section 9.4. Nearest Neighbor Queries
Section 9.5. Range Queries
Section 9.6. References
Part III: III
Chapter 10. When All Else Fails
Section 10.1. Variations on a Theme
Section 10.2. Approximation Algorithms
Section 10.3. Offline Algorithms
Section 10.4. Parallel Algorithms
Section 10.5. Randomized Algorithms
Section 10.6. Algorithms That Can Be Wrong, but with Diminishing Probability
Section 10.7. References
Chapter 11. Epilogue
Section 11.1. Overview
Section 11.2. Principle: Know Your Data
Section 11.3. Principle: Decompose the Problem into Smaller Problems
Section 11.4. Principle: Choose the Right Data Structure
Section 11.5. Principle: Add Storage to Increase Performance
Section 11.6. Principle: If No Solution Is Evident, Construct a Search
Section 11.7. Principle: If No Solution Is Evident, Reduce Your Problem to Another Problem That Has a Solution
Section 11.8. Principle: Writing Algorithms Is Hard--Testing Algorithms Is Harder
Part IV: IV
Appendix A. Benchmarking
Section A.1. Statistical Foundation
Section A.2. Hardware
Section A.3. Reporting
Section A.4. Precision

66 of 70 people found the following review helpful:

5.0 out of 5 stars Its pedestrian title gives a very wrong first-impression!, December 12, 2008

By 

K. Jazayeri (San Jose, CA United States) - See all my reviews
(REAL NAME)   

This review is from: Algorithms in a Nutshell (In a Nutshell (O'Reilly)) (Paperback)

In recent years I have found most other non-textbooks on algorithms to be uninteresting mainly for two reasons. First, there are books that are re-released periodically in a new "programming language du jour" without adding real value (some moving from Pascal to C/C++ to Python, Java or C#). The second group are books that are rather unimaginative collections of elementary information, often augmenting their bulk with lengthy pages of source code (touted as "ready-to-use", but never actually usable).

I almost didn't pay any attention to this book because its title struck me as rather mundane and pedestrian .... what an uncommonly false first-impression that turned out to be!

The is a well-written book and a great practical and usable one for working software developers at any skill or experience level. It starts with a condensed set of introductory material. It then covers the gamut of common and some not-so-common algorithms grouped by problems/tasks that do come up in a variety of real-world applications.

I particularly appreciate the concise and thoughtful - and concise - descriptions -- chock-full of notes on applicability and usability -- with absolutely no fluff! If nothing else, this book can be a good quick index or a chit sheet before culling through more standard textbooks (many of which, in fact, mentioned as further references in each section).

I believe the authors have identified a valid "hole" in the technical bookshelves - and plugged it quite well! Regarding the book's title, ... now I feel it's just appropriately simple, honest, and down-to-earth.

24 of 24 people found the following review helpful:

4.0 out of 5 stars Delivers as advertised, March 23, 2009

By 

J. Pease (Odessa, TX United States) - See all my reviews
(REAL NAME)   

This review is from: Algorithms in a Nutshell (In a Nutshell (O'Reilly)) (Paperback)

The book does not aim to be an introduction to, nor the definitive encyclopedia on, the subject of algorithms.

It is intended, as advertised on the cover, as "A Desktop Quick Reference". In the Preface it states that the goal is to provide a useful tool for working programmers to find good solutions to the problems they solve.

As a self-taught programmer I am finding this book interesting to better understand the various ways that the same problem can be solved, and the pros and cons of each. While the book is mainly intended to help programmers review and select appropriate algorithms for a problem at hand, I am using it as a study guide and have enjoyed it as such thus far. While it doesn't exactly make for light reading, each algorithm is considered individually, which makes for a decent size chunk of information which can be considered independently.

Multiple languages (C, C++, Java, Ruby) are used throughout the book in demonstrating the algorithms, solutions are not provided in each language for each algorithm. However, if you are using this as a study guide, this can provide a good exercise to translate the solution into the language of your liking.