Algorithms in a Nutshell, 2nd Edition
A Practical Guide
Publisher: O'Reilly Media
Release Date: March 2016
Pages: 434
Read on O'Reilly Online Learning with a 10day trial
Start your free trial now Buy on AmazonWhere’s the cart? Now you can get everything with O'Reilly Online Learning. To purchase books, visit Amazon or your favorite retailer. Questions? See our FAQ or contact customer service:
18008898969 / 7078277019
support@oreilly.com
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 Python 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

Chapter 1 Thinking in Algorithms

Understand the Problem

Naïve Solution

Intelligent Approaches

Summary

References


Chapter 2 The Mathematics of Algorithms

Size of a Problem Instance

Rate of Growth of Functions

Analysis in the Best, Average, and Worst Cases

Performance Families

Benchmark Operations

References


Chapter 3 Algorithm Building Blocks

Algorithm Template Format

Pseudocode Template Format

Empirical Evaluation Format

FloatingPoint Computation

Example Algorithm

Common Approaches

References


Chapter 4 Sorting Algorithms

Terminology

Representation

Comparable Elements

Stable Sorting

Criteria for Choosing a Sorting Algorithm

Transposition Sorting

Selection Sort

Heap Sort

PartitionBased Sorting

Sorting without Comparisons

Bucket Sort

Sorting with Extra Storage

String Benchmark Results

Analysis Techniques

References


Chapter 5 Searching

Sequential Search

Binary Search

HashBased Search

Bloom Filter

Binary Search Tree

References


Chapter 6 Graph Algorithms

Graphs

DepthFirst Search

BreadthFirst Search

SingleSource Shortest Path

Dijkstra’s Algorithm for Dense Graphs

Comparing SingleSource ShortestPath Options

AllPairs Shortest Path

Minimum Spanning Tree Algorithms

Final Thoughts on Graphs

References


Chapter 7 Path Finding in AI

Game Trees

PathFinding Concepts

Minimax

NegMax

AlphaBeta

Search Trees

DepthFirst Search

BreadthFirst Search

A*Search

Comparing SearchTree Algorithms

References


Chapter 8 Network Flow Algorithms

Network Flow

Maximum Flow

Bipartite Matching

Reflections on Augmenting Paths

Minimum Cost Flow

Transshipment

Transportation

Assignment

Linear Programming

References


Chapter 9 Computational Geometry

Classifying Problems

Convex Hull

Convex Hull Scan

Computing LineSegment Intersections

LineSweep

Voronoi Diagram

References


Chapter 10 Spatial Tree Structures

Nearest Neighbor Queries

Range Queries

Intersection Queries

Spatial Tree Structures

Nearest Neighbor Queries

Range Query

Quadtrees

RTrees

References


Chapter 11 Emerging Algorithm Categories

Variations on a Theme

Approximation Algorithms

Parallel Algorithms

Probabilistic Algorithms

References


Chapter 12 Epilogue: Principles of Algorithms

Know Your Data

Decompose a Problem into Smaller Problems

Choose the Right Data Structure

Make the Space versus Time TradeOff

Construct a Search

Reduce Your Problem to Another Problem

Writing Algorithms Is Hard—Testing Algorithms Is Harder

Accept Approximate Solutions When Possible

Add Parallelism to Increase Performance


Appendix Benchmarking

Statistical Foundation

Example

Reporting

Precision
