Algorithms in a NutshellCreating 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. |
Contents
Chapter 1 Thinking in Algorithms | 1 |
Chapter 2 The Mathematics of Algorithms | 9 |
Chapter 3 Algorithm Building Blocks | 35 |
Chapter 4 Sorting Algorithms | 53 |
Chapter 5 Searching | 91 |
Chapter 6 Graph Algorithms | 133 |
Chapter 7 Path Finding in AI | 169 |
Chapter 8 Network Flow Algorithms | 217 |
Common terms and phrases
A*Search AlphaBeta array augmenting path average beach line behavior Binary Search binary tree Bloom Filter Breadth-First Search chapter collection compute contains convex hull Convex Hull Scan cost delete dense graphs Depth-First Search Dijkstra’s Algorithm dist[v edges efficient evaluation execution floating-point flow network Ford–Fulkerson foreach game tree goal graph hash function hash table Heap Sort heuristic implementation initial input set Insertion Sort integer intersections iteration Java k-d tree leaf node line segments LineSweep linked list locate Merge Sort Minimax move NegMax neighboring newLen null O(log O(n log operation performance player points priority queue problem instance Python quadtree Quicksort R-Tree random Range Query rectangle recursive region return false score search tree self.root Sequential Search shortest path shown in Example shown in Figure solution solve sorting algorithm subarray subproblems subtree Summary Best target trials vertices void Voronoi diagram Worst