## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## Book Description

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

1. Preface to the Second Edition
2. 1. Thinking in Algorithms
1. Understand the Problem
2. Naïve Solution
3. Intelligent Approaches
4. Summary
5. References
3. 2. The Mathematics of Algorithms
1. Size of a Problem Instance
2. Rate of Growth of Functions
3. Analysis in the Best, Average, and Worst Cases
4. Performance Families
5. Benchmark Operations
6. References
4. 3. Algorithm Building Blocks
1. Algorithm Template Format
2. Pseudocode Template Format
3. Empirical Evaluation Format
4. Floating-Point Computation
5. Example Algorithm
6. Common Approaches
7. References
5. 4. Sorting Algorithms
1. Terminology
2. Representation
3. Comparable Elements
4. Stable Sorting
5. Criteria for Choosing a Sorting Algorithm
6. Transposition Sorting
7. Selection Sort
8. Heap Sort
9. Partition-Based Sorting
10. Sorting without Comparisons
11. Bucket Sort
12. Sorting with Extra Storage
13. String Benchmark Results
14. Analysis Techniques
15. References
6. 5. Searching
1. Sequential Search
2. Binary Search
3. Hash-Based Search
4. Bloom Filter
5. Binary Search Tree
6. References
7. 6. Graph Algorithms
1. Graphs
2. Depth-First Search
4. Single-Source Shortest Path
5. Dijkstra’s Algorithm for Dense Graphs
6. Comparing Single-Source Shortest-Path Options
7. All-Pairs Shortest Path
8. Minimum Spanning Tree Algorithms
9. Final Thoughts on Graphs
10. References
8. 7. Path Finding in AI
1. Game Trees
2. Path-Finding Concepts
3. Minimax
4. NegMax
5. AlphaBeta
6. Search Trees
7. Depth-First Search
9. A*Search
10. Comparing Search-Tree Algorithms
11. References
9. 8. Network Flow Algorithms
1. Network Flow
2. Maximum Flow
3. Bipartite Matching
4. Reflections on Augmenting Paths
5. Minimum Cost Flow
6. Transshipment
7. Transportation
8. Assignment
9. Linear Programming
10. References
10. 9. Computational Geometry
1. Classifying Problems
2. Convex Hull
3. Convex Hull Scan
4. Computing Line-Segment Intersections
5. LineSweep
6. Voronoi Diagram
7. References
11. 10. Spatial Tree Structures
1. Nearest Neighbor Queries
2. Range Queries
3. Intersection Queries
4. Spatial Tree Structures
5. Nearest Neighbor Queries
6. Range Query
8. R-Trees
9. References
12. 11. Emerging Algorithm Categories
1. Variations on a Theme
2. Approximation Algorithms
3. Parallel Algorithms
4. Probabilistic Algorithms
5. References
13. 12. Epilogue: Principles of Algorithms
14. A. Benchmarking
1. Statistical Foundation
2. Example
3. Reporting
4. Precision
15. Index