Algorithms in a nutshell Title from title screen

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. Copyright......Page 4 Preface......Page 5 I......Page 12 Algorithms Matter......Page 13 Understand the Problem......Page 14 Experiment if Necessary......Page 15 Side Story......Page 19 The Moral of the Story......Page 20 References......Page 21 Size of a Problem Instance......Page 22 Rate of Growth of Functions......Page 24 Analysis in the Best, Average, and Worst Cases......Page 28 Performance Families......Page 32 Mix of Operations......Page 45 Benchmark Operations......Page 46 References......Page 48 Patterns: A Communication Language......Page 49 Algorithm Pattern Format......Page 51 Pseudocode Pattern Format......Page 52 Design Format......Page 53 Empirical Evaluation Format......Page 54 Domains and Algorithms......Page 56 Floating-Point Computations......Page 57 Manual Memory Allocation......Page 60 Choosing a Programming Language......Page 63 References......Page 64 II......Page 65 Overview......Page 66 Insertion Sort......Page 72 Median Sort......Page 76 Quicksort......Page 87 Selection Sort......Page 94 Heap Sort......Page 95 Counting Sort......Page 100 Bucket Sort......Page 102 Criteria for Choosing a Sorting Algorithm......Page 108 References......Page 112 Overview......Page 114 Sequential Search......Page 115 Binary Search......Page 121 Hash-based Search......Page 125 Binary Tree Search......Page 138 Overview......Page 145 Depth-First Search......Page 151 Breadth-First Search......Page 158 Single-Source Shortest Path......Page 162 All Pairs Shortest Path......Page 174 Minimum Spanning Tree Algorithms......Page 178 References......Page 180 Overview......Page 181 Depth-First Search......Page 190 Breadth-First Search......Page 199 A*Search......Page 203 Comparison......Page 213 Minimax......Page 216 NegMax......Page 222 AlphaBeta......Page 226 References......Page 233 Overview......Page 235 Maximum Flow......Page 238 Bipartite Matching......Page 248 Reflections on Augmenting Paths......Page 251 Transshipment......Page 255 Transportation......Page 256 Assignment......Page 257 Linear Programming......Page 258 References......Page 259 Overview......Page 260 Convex Hull Scan......Page 269 LineSweep......Page 277 Nearest Neighbor Queries......Page 289 Range Queries......Page 301 References......Page 307 III......Page 308 Variations on a Theme......Page 309 Offline Algorithms......Page 310 Randomized Algorithms......Page 311 Algorithms That Can Be Wrong, but with Diminishing Probability......Page 318 References......Page 321 Principle: Know Your Data......Page 322 Principle: Decompose the Problem into Smaller Problems......Page 323 Principle: Choose the Right Data Structure......Page 324 Principle: Add Storage to Increase Performance......Page 325 Principle: If No Solution Is Evident, Reduce Your Problem to Another Problem That Has a Solution......Page 326 Principle: Writing Algorithms Is Hard—Testing Algorithms Is Harder......Page 327 IV......Page 329 Statistical Foundation......Page 330 Hardware......Page 331 Reporting......Page 340 Precision......Page 341 Colophon......Page 343 Algorithms in a Nutshell Copyright 4 Preface 5 I 12 Algorithms Matter 13 Understand the Problem 14 Experiment if Necessary 15 Side Story 19 The Moral of the Story 20 References 21 The Mathematics of Algorithms 22 Size of a Problem Instance 22 Rate of Growth of Functions 24 Analysis in the Best, Average, and Worst Cases 28 Performance Families 32 Mix of Operations 45 Benchmark Operations 46 One Final Point 48 References 48 Patterns and Domains 49 Patterns: A Communication Language 49 Algorithm Pattern Format 51 Pseudocode Pattern Format 52 Design Format 53 Empirical Evaluation Format 54 Domains and Algorithms 56 Floating-Point Computations 57 Manual Memory Allocation 60 Choosing a Programming Language 63 References 64 II 65 Sorting Algorithms 66 Overview 66 Insertion Sort 72 Median Sort 76 Quicksort 87 Selection Sort 94 Heap Sort 95 Counting Sort 100 Bucket Sort 102 Criteria for Choosing a Sorting Algorithm 108 References 112 Searching 114 Overview 114 Sequential Search 115 Binary Search 121 Hash-based Search 125 Binary Tree Search 138 Graph Algorithms 145 Overview 145 Depth-First Search 151 Breadth-First Search 158 Single-Source Shortest Path 162 All Pairs Shortest Path 174 Minimum Spanning Tree Algorithms 178 References 180 Path Finding in AI 181 Overview 181 Depth-First Search 190 Breadth-First Search 199 A*Search 203 Comparison 213 Minimax 216 NegMax 222 AlphaBeta 226 References 233 Network Flow Algorithms 235 Overview 235 Maximum Flow 238 Bipartite Matching 248 Reflections on Augmenting Paths 251 Minimum Cost Flow 255 Transshipment 255 Transportation 256 Assignment 257 Linear Programming 258 References 259 Computational Geometry 260 Overview 260 Convex Hull Scan 269 LineSweep 277 Nearest Neighbor Queries 289 Range Queries 301 References 307 III 308 When All Else Fails 309 Variations on a Theme 309 Approximation Algorithms 310 Offline Algorithms 310 Parallel Algorithms 311 Randomized Algorithms 311 Algorithms That Can Be Wrong, but with Diminishing Probability 318 References 321 Epilogue 322 Overview 322 Principle: Know Your Data 322 Principle: Decompose the Problem into Smaller Problems 323 Principle: Choose the Right Data Structure 324 Principle: Add Storage to Increase Performance 325 Principle: If No Solution Is Evident, Construct a Search 326 Principle: If No Solution Is Evident, Reduce Your Problem to Another Problem That Has a Solution 326 Principle: Writing Algorithms Is Hard鈥擳esting Algorithms Is Harder 327 IV 329 Benchmarking 330 Statistical Foundation 330 Hardware 331 Reporting 340 Precision 341 About the Authors 343 Colophon 343 Creating software systems involves more than simply writing a program. It requires creativity and technical excellence. Technical excellence includes the ability to make programs robust and efficient. Efficient algorithms are at the heart of all but the most trivial programs. Programmers, however, seldom think about the algorithms in their programs until they encounter problems. Many programmers do not have a background in algorithm analysis and design and if they do, they don't take the time to find the right algorithm for their needs. Algorithms in a Nutshell helps programmers select, analyze, and implement the right algorithms for their particular needs. It provides just enough mathematics to let the reader understand and analyze algorithm performance. The algorithms in the book are based upon the type of problems they address. Each algorithm is presented in the style of a design pattern - an approach, or plan for how to solve the problem accompanied by the information needed to understand why the algorithm is appropriate, how one might determine why the algorithm is the right one, and implementation tips. This is a major benefit to the reader. Just as design patterns for object-oriented design enable developers to use a common language to describe their designs, we believe that providing a pattern language for algorithms can enable similar communication benefits. Efficient algorithms are at the heart of all but the most trivial programs. 'Algorithms in a Nutshell' helps programmers select, analyze, and implement the right algorithms for their particular needs, providing just enough mathematics to let the reader understand and analyze algorithm performance