Algorithms in a Nutshell
Publisher: O'Reilly Media
Release Date: June 2009
Pages: 364
Read on Safari with a 10day trial
Start your free trial now Buy on AmazonWhere’s the cart? Now you can get everything on Safari. To purchase books, visit Amazon or your favorite retailer. Questions? See our FAQ or contact customer service:
18008898969 / 7078277019
support@oreilly.com
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.
Table of Contents

I

Chapter 1 Algorithms Matter
 Understand the Problem
 Experiment if Necessary
 Side Story
 The Moral of the Story
 References

Chapter 2 The Mathematics of Algorithms
 Size of a Problem Instance
 Rate of Growth of Functions
 Analysis in the Best, Average, and Worst Cases
 Performance Families
 Mix of Operations
 Benchmark Operations
 One Final Point
 References

Chapter 3 Patterns and Domains
 Patterns: A Communication Language
 Algorithm Pattern Format
 Pseudocode Pattern Format
 Design Format
 Empirical Evaluation Format
 Domains and Algorithms
 FloatingPoint Computations
 Manual Memory Allocation
 Choosing a Programming Language
 References


II

Chapter 4 Sorting Algorithms
 Overview
 Insertion Sort
 Median Sort
 Quicksort
 Selection Sort
 Heap Sort
 Counting Sort
 Bucket Sort
 Criteria for Choosing a Sorting Algorithm
 References

Chapter 5 Searching
 Overview
 Sequential Search
 Binary Search
 Hashbased Search
 Binary Tree Search

Chapter 6 Graph Algorithms
 Overview
 DepthFirst Search
 BreadthFirst Search
 SingleSource Shortest Path
 All Pairs Shortest Path
 Minimum Spanning Tree Algorithms
 References

Chapter 7 Path Finding in AI
 Overview
 DepthFirst Search
 BreadthFirst Search
 A*Search
 Comparison
 Minimax
 NegMax
 AlphaBeta
 References

Chapter 8 Network Flow Algorithms
 Overview
 Maximum Flow
 Bipartite Matching
 Reflections on Augmenting Paths
 Minimum Cost Flow
 Transshipment
 Transportation
 Assignment
 Linear Programming
 References

Chapter 9 Computational Geometry
 Overview
 Convex Hull Scan
 LineSweep
 Nearest Neighbor Queries
 Range Queries
 References


III

Chapter 10 When All Else Fails
 Variations on a Theme
 Approximation Algorithms
 Offline Algorithms
 Parallel Algorithms
 Randomized Algorithms
 Algorithms That Can Be Wrong, but with Diminishing Probability
 References

Chapter 11 Epilogue
 Overview
 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


IV

Appendix A Benchmarking
 Statistical Foundation
 Hardware
 Reporting
 Precision


About the Authors

Colophon