Algorithms in a Nutshell: A Desktop Quick Reference

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 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 Cover 1 Copyright 3 Table of Contents 4 Chapter聽1.聽Thinking Algorithmically 12 Understand the Problem 12 Naive Solution 14 Intelligent Approaches 15 Greedy 15 Divide and Conquer 16 Parallel 16 Approximation 17 Generalization 18 Summary 19 Chapter聽2.聽The Mathematics of Algorithms 20 Size of a Problem Instance 20 Rate of Growth of Functions 21 Analysis in the Best, Average, and Worst Cases 26 Worst Case 29 Average Case 29 Best Case 30 Performance Families 31 Constant Behavior 31 Log n Behavior 32 Sublinear O(nd) Behavior for d < 1 34 Linear Performance 34 n log n Performance 38 Quadratic Performance 39 Less Obvious Performance Computations 41 Exponential Performance 44 Benchmark Operations 44 Lower and Upper Bounds 47 References 47 Chapter聽3.聽Algorithm Building Blocks 48 Algorithm Template Format 48 Name 49 Input/Output 49 Context 49 Solution 49 Analysis 49 Variations 50 Pseudocode Template Format 50 Empirical Evaluation Format 51 Floating-Point Computation 51 Performance 52 Rounding Error 52 Comparing Floating Point Values 54 Special Quantities 55 Example Algorithm 56 Name and Synopsis 56 Input/Output 57 Context 57 Solution 57 Analysis 60 Common Approaches 60 Greedy 60 Divide and Conquer 61 Dynamic Programming 62 References 67 Chapter聽4.聽Sorting Algorithms 68 Overview 68 Terminology 68 Representation 69 Comparable Elements 70 Stable Sorting 71 Criteria for Choosing a Sorting Algorithm 72 Transposition Sorting 72 Insertion Sort 72 Context 74 Solution 74 Analysis 76 Selection Sort 77 Heap Sort 78 Context 83 Solution 84 Analysis 85 Variations 85 Partition-based Sorting 85 Context 91 Solution 91 Analysis 92 Variations 92 Sorting Without Comparisons 94 Bucket Sort 94 Solution 97 Analysis 99 Variations 100 Sorting with Extra Storage 101 Merge Sort 101 Input/Output 103 Solution 103 Analysis 104 Variations 105 String Benchmark Results 106 Analysis Techniques 109 References 110 Chapter聽5.聽Searching 112 Sequential Search 113 Input/Output 114 Context 114 Solution 115 Analysis 116 Binary Search 117 Input/Output 117 Context 118 Solution 118 Analysis 119 Variations 121 Hash-based Search 122 Input/Output 124 Context 125 Solution 128 Analysis 130 Variations 133 Bloom Filter 138 Input/Output 140 Context 140 Solution 140 Analysis 142 Binary Search Tree 143 Input/Output 144 Context 144 Solution 146 Analysis 157 Variations 157 References 157 Chapter聽6.聽Graph Algorithms 160 Graphs 162 Data Structure Design 165 Depth-First Search 166 Input/Output 171 Context 172 Solution 172 Analysis 174 Variations 175 Breadth-First Search 175 Input/Output 178 Context 179 Solution 179 Analysis 180 Single-Source Shortest Path 180 Input/Output 183 Solution 183 Analysis 185 Dijkstra鈥檚 Algorithm For Dense Graphs 185 Variations 188 Comparing Single Source Shortest Path Options 191 Benchmark data 192 Dense graphs 192 Sparse graphs 193 All Pairs Shortest Path 194 Input/Output 197 Solution 197 Analysis 199 Minimum Spanning Tree Algorithms 199 Solution 202 Analysis 203 Variations 203 Final Thoughts on Graphs 203 Storage Issues 203 Graph Analysis 204 References 205 Chapter聽7.聽Path Finding in AI 206 Game Trees 207 Minimax 210 Input/Output 213 Context 213 Solution 214 Analysis 216 NegMax 217 Solution 219 Analysis 221 AlphaBeta 221 Solution 225 Analysis 226 Search Trees 228 Representing State 231 Calculate available moves 232 Using Heuristic Information 232 Maximum Expansion Depth 234 Depth-First Search 234 Input/Output 236 Context 236 Solution 236 Analysis 238 Breadth-First Search 241 Input/Output 243 Context 243 Solution 244 Analysis 245 A*Search 245 Input/Output 247 Context 247 Solution 250 Analysis 254 Variations 257 Comparing Search Tree Algorithms 258 References 262 Chapter聽8.聽Network Flow Algorithms 266 Network Flow 268 Maximum Flow 270 Input/Output 272 Solution 273 Analysis 278 Optimization 279 Related Algorithms 281 Bipartite Matching 281 Input/Output 282 Solution 282 Analysis 285 Reflections on Augmenting Paths 285 Minimum Cost Flow 290 Transshipment 291 Solution 291 Transportation 294 Solution 294 Assignment 294 Solution 294 Linear Programming 294 References 296 Chapter聽9.聽Computational Geometry 298 Classifying Problems 299 Input data 299 Computation 301 Nature of the task 302 Assumptions 302 Convex Hull 302 Convex Hull Scan 304 Input/Output 306 Context 306 Solution 306 Analysis 308 Variations 310 Computing Line Segment Intersections 313 LineSweep 314 Input/Output 317 Context 317 Solution 318 Analysis 321 Variations 324 Voronoi Diagram 324 Input/Output 332 Solution 333 Analysis 338 References 339 Chapter聽10.聽Spatial Tree Structures 340 Nearest Neighbor queries 341 Range Queries 342 Intersection Queries 342 Spatial Tree Structures 343 KD-Tree 343 Quad Tree 344 R-Tree 345 Nearest Neighbor 346 Input/Output 348 Context 349 Solution 349 Analysis 351 Variations 358 Range Query 358 Input/Output 360 Context 361 Solution 361 Analysis 362 QuadTrees 366 Input/Output 369 Solution 370 Analysis 373 Variations 374 R-Trees 374 Input/Output 379 Context 379 Solution 380 Analysis 385 References 387 Chapter聽11.聽Emerging Algorithm Categories 390 Variations on a Theme 390 Approximation Algorithms 391 Input/Output 392 Context 393 Solution 393 Analysis 395 Parallel Algorithms 397 Probabilistic Algorithms 403 Estimating the Size of a Set 403 Estimating the Size of a Search Tree 405 References 411 Chapter聽12.聽Epilogue 412 Principle: Know Your Data 412 Principle: Decompose the Problem into Smaller Problems 413 Principle: Choose the Right Data Structure 415 Principle: Make the Space versus Time Trade-off 417 Principle: If No Solution Is Evident, Construct a Search 418 Principle: If No Solution Is Evident, Reduce Your Problem to Another Problem That Has a Solution 419 Principle: Writing Algorithms Is Hard鈥擳esting Algorithms Is Harder 420 Principle: Accept Approximate Solution When Possible 421 Principle: Add Parallelism to Increase Performance 422 Appendix聽A.聽Benchmarking 424 Statistical Foundation 424 Example 426 Java benchmarking solutions 426 Linux benchmarking solutions 427 Python benchmarking solutions 431 Reporting 432 Precision 434 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-- Source other than Library of Congress