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
鄂公网安备 42010302001612号 