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

Algorithms in a Nutshell

by Gary Pollice, Stanley Selkow, George T. Heineman
Publisher: O'Reilly Media, Inc.
Release Date: October 2008
ISBN: 9780596516246
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. 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.

Table of Contents

  1. Algorithms in a Nutshell
    1. SPECIAL OFFER: Upgrade this ebook with O’Reilly
    2. A Note Regarding Supplemental Files
    3. Preface
      1. Principle: Use Real Code, Not Pseudocode
      2. Principle: Separate the Algorithm from the Problem Being Solved
      3. Principle: Introduce Just Enough Mathematics
      4. Principle: Support Mathematical Analysis Empirically
      5. Audience
      6. Contents of This Book
      7. Conventions Used in This Book
      8. Using Code Examples
      9. Comments and Questions
      10. Safari® Books Online
      11. Acknowledgments
      12. References
    4. I. I
      1. 1. Algorithms Matter
        1. 1.1. Understand the Problem
        2. 1.2. Experiment if Necessary
        3. 1.3. Side Story
        4. 1.4. The Moral of the Story
        5. 1.5. References
      2. 2. The Mathematics of Algorithms
        1. 2.1. Size of a Problem Instance
        2. 2.2. Rate of Growth of Functions
        3. 2.3. Analysis in the Best, Average, and Worst Cases
        4. 2.4. Performance Families
        5. 2.5. Mix of Operations
        6. 2.6. Benchmark Operations
        7. 2.7. One Final Point
        8. 2.8. References
      3. 3. Patterns and Domains
        1. 3.1. Patterns: A Communication Language
        2. 3.2. Algorithm Pattern Format
        3. 3.3. Pseudocode Pattern Format
        4. 3.4. Design Format
        5. 3.5. Empirical Evaluation Format
        6. 3.6. Domains and Algorithms
        7. 3.7. Floating-Point Computations
        8. 3.8. Manual Memory Allocation
        9. 3.9. Choosing a Programming Language
        10. 3.10. References
    5. II. II
      1. 4. Sorting Algorithms
        1. 4.1. Overview
        2. 4.2. Insertion Sort
        3. 4.3. Median Sort
        4. 4.4. Quicksort
        5. 4.5. Selection Sort
        6. 4.6. Heap Sort
        7. 4.7. Counting Sort
        8. 4.8. Bucket Sort
        9. 4.9. Criteria for Choosing a Sorting Algorithm
        10. 4.10. References
      2. 5. Searching
        1. 5.1. Overview
        2. 5.2. Sequential Search
        3. 5.3. Binary Search
        4. 5.4. Hash-based Search
        5. 5.5. Binary Tree Search
      3. 6. Graph Algorithms
        1. 6.1. Overview
        2. 6.2. Depth-First Search
        3. 6.3. Breadth-First Search
        4. 6.4. Single-Source Shortest Path
        5. 6.5. All Pairs Shortest Path
        6. 6.6. Minimum Spanning Tree Algorithms
        7. 6.7. References
      4. 7. Path Finding in AI
        1. 7.1. Overview
        2. 7.2. Depth-First Search
        3. 7.3. Breadth-First Search
        4. 7.4. A*Search
        5. 7.5. Comparison
        6. 7.6. Minimax
        7. 7.7. NegMax
        8. 7.8. AlphaBeta
        9. 7.9. References
      5. 8. Network Flow Algorithms
        1. 8.1. Overview
        2. 8.2. Maximum Flow
        3. 8.3. Bipartite Matching
        4. 8.4. Reflections on Augmenting Paths
        5. 8.5. Minimum Cost Flow
        6. 8.6. Transshipment
        7. 8.7. Transportation
        8. 8.8. Assignment
        9. 8.9. Linear Programming
        10. 8.10. References
      6. 9. Computational Geometry
        1. 9.1. Overview
        2. 9.2. Convex Hull Scan
        3. 9.3. LineSweep
        4. 9.4. Nearest Neighbor Queries
        5. 9.5. Range Queries
        6. 9.6. References
    6. III. III
      1. 10. When All Else Fails
        1. 10.1. Variations on a Theme
        2. 10.2. Approximation Algorithms
        3. 10.3. Offline Algorithms
        4. 10.4. Parallel Algorithms
        5. 10.5. Randomized Algorithms
        6. 10.6. Algorithms That Can Be Wrong, but with Diminishing Probability
        7. 10.7. References
      2. 11. Epilogue
        1. 11.1. Overview
        2. 11.2. Principle: Know Your Data
        3. 11.3. Principle: Decompose the Problem into Smaller Problems
        4. 11.4. Principle: Choose the Right Data Structure
        5. 11.5. Principle: Add Storage to Increase Performance
        6. 11.6. Principle: If No Solution Is Evident, Construct a Search
        7. 11.7. Principle: If No Solution Is Evident, Reduce Your Problem to Another Problem That Has a Solution
        8. 11.8. Principle: Writing Algorithms Is Hard—Testing Algorithms Is Harder
    7. IV. IV
      1. A. Benchmarking
        1. A.1. Statistical Foundation
        2. A.2. Hardware
        3. A.3. Reporting
        4. A.4. Precision
    8. About the Authors
    9. Index
    10. About the Authors
    11. Colophon
    12. SPECIAL OFFER: Upgrade this ebook with O’Reilly