Algorithms in a Nutshell by Heineman, George T. -- Read -- Imperial Library of Trantor

Index

Algorithms in a Nutshell

A Note Regarding Supplemental Files Preface

Principle: Use Real Code, Not Pseudocode Principle: Separate the Algorithm from the Problem Being Solved Principle: Introduce Just Enough Mathematics Principle: Support Mathematical Analysis Empirically Audience Contents of This Book Conventions Used in This Book Using Code Examples Comments and Questions Safari® Books Online Acknowledgments References

I. I

1. Algorithms Matter

1.1. Understand the Problem 1.2. Experiment if Necessary 1.3. Side Story 1.4. The Moral of the Story 1.5. References

2. The Mathematics of Algorithms

2.1. Size of a Problem Instance 2.2. Rate of Growth of Functions 2.3. Analysis in the Best, Average, and Worst Cases 2.4. Performance Families 2.5. Mix of Operations 2.6. Benchmark Operations 2.7. One Final Point 2.8. References

3. Patterns and Domains

3.1. Patterns: A Communication Language 3.2. Algorithm Pattern Format 3.3. Pseudocode Pattern Format 3.4. Design Format 3.5. Empirical Evaluation Format 3.6. Domains and Algorithms 3.7. Floating-Point Computations 3.8. Manual Memory Allocation 3.9. Choosing a Programming Language 3.10. References

II. II

4. Sorting Algorithms

4.1. Overview 4.2. Insertion Sort 4.3. Median Sort 4.4. Quicksort 4.5. Selection Sort 4.6. Heap Sort 4.7. Counting Sort 4.8. Bucket Sort 4.9. Criteria for Choosing a Sorting Algorithm 4.10. References

5. Searching

5.1. Overview 5.2. Sequential Search 5.3. Binary Search 5.4. Hash-based Search 5.5. Binary Tree Search

6. Graph Algorithms

6.1. Overview 6.2. Depth-First Search 6.3. Breadth-First Search 6.4. Single-Source Shortest Path 6.5. All Pairs Shortest Path 6.6. Minimum Spanning Tree Algorithms 6.7. References

7. Path Finding in AI

7.1. Overview 7.2. Depth-First Search 7.3. Breadth-First Search 7.4. A*Search 7.5. Comparison 7.6. Minimax 7.7. NegMax 7.8. AlphaBeta 7.9. References

8. Network Flow Algorithms

8.1. Overview 8.2. Maximum Flow 8.3. Bipartite Matching 8.4. Reflections on Augmenting Paths 8.5. Minimum Cost Flow 8.6. Transshipment 8.7. Transportation 8.8. Assignment 8.9. Linear Programming 8.10. References

9. Computational Geometry

9.1. Overview 9.2. Convex Hull Scan 9.3. LineSweep 9.4. Nearest Neighbor Queries 9.5. Range Queries 9.6. References

III. III

10. When All Else Fails

10.1. Variations on a Theme 10.2. Approximation Algorithms 10.3. Offline Algorithms 10.4. Parallel Algorithms 10.5. Randomized Algorithms 10.6. Algorithms That Can Be Wrong, but with Diminishing Probability 10.7. References

11. Epilogue

IV. IV

A. Benchmarking

A.1. Statistical Foundation A.2. Hardware A.3. Reporting A.4. Precision

About the Authors Index About the Authors Colophon