Preface

Part 1

1. Algorithms Matter

Understand the Problem

Experiment if Necessary

Algorithms to the Rescue

Side Story

The Moral of the Story

References

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

Mix of Operations

Benchmark Operatxons

One Final Point

References

3. Patterns and Domains

Patterns: A Communication Language

Algorithm Pattern Format

Pseudocode Pattern Format

Design Format

Empirical Evaluation Format

Domains and Algorithms

Floating-Point Computations

Manual Memory Allocation

Choosing a Programming Language

References

Part 2

4. Sorting Algorithms

Overview

Insertion Sort

Median Sort

Quicksort

Selection Sort

Heap Sort

Counting Sort

Bucket Sort

Criteria for Choosing a Sorting Algorithm

References

5. Searching

Overview

Sequential Search

Binary Search

Hash-based Search

Binary Tree Search

6. GraphAIgorithms

Overview

Depth-First Search

Breadth-First Search

Single-Source Shortest Path

All Pairs Shortest Path

Minimum Spanning Tree Algorithms

References

7. Path Finding in AI

Overview

Depth-First Search

Breadth-First Search

A'Search

Comparison

Minimax

NegMax

AlphaBeta

References

8. Network Flow Algorithms

Overview

Maximum Flow

Bipartite Matching

Reflections on Augmenting Paths

Minimum Cost Flow

Transshipment

Transportation

Assignment

Linear Programming

References

9. Computational Geometry

Overview

Convex Hull Scan

LineSweep

Nearest Neighbor Queries

Range Queries

References

Part 3

10. When All Else Fails

Variations on a Theme

Approximation Algorithms

Offline Algorithms

Parallel Algorithms

Randomized Algorithms

Algorithms That Can Be Wrong, but with Diminishing Probability References

11. Epilogue

Overview

Principle: Know Your Data

Principle: Decompose the Problem into Smaller Problems

Principle: Choose the Right Data Structure

Principle: Add Storage to Increase Performance

Principle: If No Solution Is Evident, Construct a Search

Principle: If No Solution Is Evident, Reduce Your Problem to

Another Problem That Has a Solution

Principle: Writing Algorithms Is Hard--Testing Algorithms Is Harder

Part 4

Appendix: Benchmarking

Index