O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

Algorithms in a Nutshell, 2nd Edition

Algorithms in a Nutshell, 2nd Edition

4 reviews
by Stanley Selkow, Gary Pollice, George T. Heineman
Publisher: O'Reilly Media, Inc.
Release Date: December 2015
ISBN: 9781491912973
View table of contents
Start reading

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

Table of Contents

  1. Preface to the Second Edition
    1. Changes to the Second Edition
    2. Audience
    3. Conventions Used in This Book
    4. Using Code Examples
    5. Safari® Books Online
    6. How to Contact Us
    7. Acknowledgments
  2. 1. Thinking in Algorithms
    1. Understand the Problem
    2. Naïve Solution
    3. Intelligent Approaches
      1. Greedy
      2. Divide and Conquer
      3. Parallel
      4. Approximation
      5. Generalization
    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
      1. Worst Case
      2. Average Case
      3. Best Case
      4. Lower and Upper Bounds
    4. Performance Families
      1. Constant Behavior
      2. Log n Behavior
      3. Sublinear O(nd) Behavior for d < 1
      4. Linear Performance
      5. Linearithmic Performance
      6. Quadratic Performance
      7. Less Obvious Performance Computations
      8. Exponential Performance
      9. Summary of Asymptotic Growth
    5. Benchmark Operations
    6. References
  4. 3. Algorithm Building Blocks
    1. Algorithm Template Format
      1. Name
      2. Input/Output
      3. Context
      4. Solution
      5. Analysis
      6. Variations
    2. Pseudocode Template Format
    3. Empirical Evaluation Format
    4. Floating-Point Computation
      1. Performance
      2. Rounding Error
      3. Comparing Floating-Point Values
      4. Special Quantities
    5. Example Algorithm
      1. Name and Synopsis
      2. Input/Output
      3. Context
      4. Solution
      5. Analysis
    6. Common Approaches
      1. Greedy
      2. Divide and Conquer
      3. Dynamic Programming
    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
      1. Insertion Sort
      2. Context
      3. Solution
      4. Analysis
    7. Selection Sort
    8. Heap Sort
      1. Context
      2. Solution
      3. Analysis
      4. Variations
    9. Partition-Based Sorting
      1. Context
      2. Solution
      3. Analysis
      4. Variations
    10. Sorting without Comparisons
    11. Bucket Sort
      1. Solution
      2. Analysis
      3. Variations
    12. Sorting with Extra Storage
      1. Merge Sort
      2. Input/Output
      3. Solution
      4. Analysis
      5. Variations
    13. String Benchmark Results
    14. Analysis Techniques
    15. References
  6. 5. Searching
    1. Sequential Search
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
    2. Binary Search
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
      5. Variations
    3. Hash-Based Search
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
      5. Variations
    4. Bloom Filter
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
    5. Binary Search Tree
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
      5. Variations
    6. References
  7. 6. Graph Algorithms
    1. Graphs
      1. Data Structure Design
    2. Depth-First Search
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
      5. Variations
    3. Breadth-First Search
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
    4. Single-Source Shortest Path
      1. Input/Output
      2. Solution
      3. Analysis
    5. Dijkstra’s Algorithm for Dense Graphs
      1. Variations
    6. Comparing Single-Source Shortest-Path Options
      1. Benchmark Data
      2. Dense Graphs
      3. Sparse graphs
    7. All-Pairs Shortest Path
      1. Input/Output
      2. Solution
      3. Analysis
    8. Minimum Spanning Tree Algorithms
      1. Input/Output
      2. Solution
      3. Analysis
      4. Variations
    9. Final Thoughts on Graphs
      1. Storage Issues
      2. Graph Analysis
    10. References
  8. 7. Path Finding in AI
    1. Game Trees
      1. Static Evaluation Functions
    2. Path-Finding Concepts
      1. Representing State
      2. Calculating Available Moves
      3. Maximum Expansion Depth
    3. Minimax
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
    4. NegMax
      1. Solution
      2. Analysis
    5. AlphaBeta
      1. Solution
      2. Analysis
    6. Search Trees
      1. Path-Length Heuristic Functions
    7. Depth-First Search
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
    8. Breadth-First Search
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
    9. A*Search
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
      5. Variations
    10. Comparing Search-Tree Algorithms
    11. References
  9. 8. Network Flow Algorithms
    1. Network Flow
    2. Maximum Flow
      1. Input/Output
      2. Solution
      3. Analysis
      4. Optimization
      5. Related Algorithms
    3. Bipartite Matching
      1. Input/Output
      2. Solution
      3. Analysis
    4. Reflections on Augmenting Paths
    5. Minimum Cost Flow
    6. Transshipment
      1. Solution
    7. Transportation
      1. Solution
    8. Assignment
      1. Solution
    9. Linear Programming
    10. References
  10. 9. Computational Geometry
    1. Classifying Problems
      1. Input Data
      2. Computation
      3. Nature of the Task
      4. Assumptions
    2. Convex Hull
    3. Convex Hull Scan
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
      5. Variations
    4. Computing Line-Segment Intersections
    5. LineSweep
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
      5. Variations
    6. Voronoi Diagram
      1. Input/Output
      2. Solution
      3. Analysis
    7. References
  11. 10. Spatial Tree Structures
    1. Nearest Neighbor Queries
    2. Range Queries
    3. Intersection Queries
    4. Spatial Tree Structures
      1. k-d Tree
      2. Quadtree
      3. R-Tree
    5. Nearest Neighbor Queries
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
      5. Variations
    6. Range Query
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
    7. Quadtrees
      1. Input/Output
      2. Solution
      3. Analysis
      4. Variations
    8. R-Trees
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
    9. References
  12. 11. Emerging Algorithm Categories
    1. Variations on a Theme
    2. Approximation Algorithms
      1. Input/Output
      2. Context
      3. Solution
      4. Analysis
    3. Parallel Algorithms
    4. Probabilistic Algorithms
      1. Estimating the Size of a Set
      2. Estimating the Size of a Search Tree
    5. References
  13. 12. Epilogue: Principles of Algorithms
    1. Know Your Data
    2. Decompose a Problem into Smaller Problems
    3. Choose the Right Data Structure
    4. Make the Space versus Time Trade-Off
    5. Construct a Search
    6. Reduce Your Problem to Another Problem
    7. Writing Algorithms Is Hard—Testing Algorithms Is Harder
    8. Accept Approximate Solutions When Possible
    9. Add Parallelism to Increase Performance
  14. A. Benchmarking
    1. Statistical Foundation
    2. Example
      1. Java Benchmarking Solutions
      2. Linux Benchmarking Solutions
      3. Python Benchmarking Solutions
    3. Reporting
    4. Precision
  15. Index