Algorithms in a Nutshell

Algorithms in a Nutshell

Algorithms in a Nutshell

Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:

9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]

• Copyright.....................................................................................................


• Preface........................................................................................................


• Part I: I.......................................................................................................
  
  
  • Chapter 1. Algorithms Matter.......................................................................................................................................................
    
    
    • Section 1.1. Understand the Problem.........................................................................................................................................
    
    
    • Section 1.2. Experiment if Necessary........................................................................................................................................
    
    
    • Section 1.3. Side Story................................................................................................................................................................
    
    
    • Section 1.4. The Moral of the Story............................................................................................................................................
    
    
    • Section 1.5. References..............................................................................................................................................................
    
    
    
    
  
  
  • Chapter 2. The Mathematics of Algorithms..................................................................................................................................
    
    
    • Section 2.1. Size of a Problem Instance.....................................................................................................................................
    
    
    • Section 2.2. Rate of Growth of Functions..................................................................................................................................
    
    
    • Section 2.3. Analysis in the Best, Average, and Worst Cases...................................................................................................
    
    
    • Section 2.4. Performance Families...........................................................................................................................................
    
    
    • Section 2.5. Mix of Operations..................................................................................................................................................
    
    
    • Section 2.6. Benchmark Operations.........................................................................................................................................
    
    
    • Section 2.7. One Final Point......................................................................................................................................................
    
    
    • Section 2.8. References.............................................................................................................................................................
    
    
    
    
  
  
  • Chapter 3. Patterns and Domains.................................................................................................................................................
    
    
    • Section 3.1. Patterns: A Communication Language.................................................................................................................
    
    
    • Section 3.2. Algorithm Pattern Format....................................................................................................................................
    
    
    • Section 3.3. Pseudocode Pattern Format..................................................................................................................................
    
    
    • Section 3.4. Design Format.......................................................................................................................................................
    
    
    • Section 3.5. Empirical Evaluation Format................................................................................................................................
    
    
    • Section 3.6. Domains and Algorithms......................................................................................................................................
    
    
    • Section 3.7. Floating-Point Computations................................................................................................................................
    
    
    • Section 3.8. Manual Memory Allocation...................................................................................................................................
    
    
    • Section 3.9. Choosing a Programming Language.....................................................................................................................
    
    
    • Section 3.10. References............................................................................................................................................................
    
    
    
    
  
  
  
  


• Part II: II...................................................................................................
  
  
  • Chapter 4. Sorting Algorithms......................................................................................................................................................
    
    
    • Section 4.1. Overview................................................................................................................................................................
    
    
    • Section 4.2. Insertion Sort........................................................................................................................................................
    
    
    • Section 4.3. Median Sort...........................................................................................................................................................
    
    
    • Section 4.4. Quicksort...............................................................................................................................................................
    
    
    • Section 4.5. Selection Sort.........................................................................................................................................................
    
    
    • Section 4.6. Heap Sort...............................................................................................................................................................
    
    
    • Section 4.7. Counting Sort.........................................................................................................................................................
    
    
    • Section 4.8. Bucket Sort............................................................................................................................................................
    
    
    • Section 4.9. Criteria for Choosing a Sorting Algorithm..........................................................................................................
    
    
    • Section 4.10. References..........................................................................................................................................................
    
    
    
    
  
  
  • Chapter 5. Searching....................................................................................................................................................................
    
    
    • Section 5.1. Overview................................................................................................................................................................
    
    
    • Section 5.2. Sequential Search.................................................................................................................................................
    
    
    • Section 5.3. Binary Search.......................................................................................................................................................
    
    
    • Section 5.4. Hash-based Search..............................................................................................................................................
    
    
    • Section 5.5. Binary Tree Search...............................................................................................................................................
    
    
    
    
  
  
  • Chapter 6. Graph Algorithms......................................................................................................................................................
    
    
    • Section 6.1. Overview...............................................................................................................................................................
    
    
    • Section 6.2. Depth-First Search..............................................................................................................................................
    
    
    • Section 6.3. Breadth-First Search............................................................................................................................................
    
    
    • Section 6.4. Single-Source Shortest Path................................................................................................................................
    
    
    • Section 6.5. All Pairs Shortest Path..........................................................................................................................................
    
    
    • Section 6.6. Minimum Spanning Tree Algorithms.................................................................................................................
    
    
    • Section 6.7. References............................................................................................................................................................
    
    
    
    
  
  
  • Chapter 7. Path Finding in AI......................................................................................................................................................
  
  
  
  


• Print Publication Date: 2008/10/21 User number: Licensed by Ming Yi
  
  
  • Section 7.1. Overview...............................................................................................................................................................
  
  
  • Section 7.2. Depth-First Search...............................................................................................................................................
  
  
  • Section 7.3. Breadth-First Search............................................................................................................................................
  
  
  • Section 7.4. A*Search..............................................................................................................................................................
  
  
  • Section 7.5. Comparison..........................................................................................................................................................
  
  
  • Section 7.6. Minimax...............................................................................................................................................................
  
  
  • Section 7.7. NegMax................................................................................................................................................................
  
  
  • Section 7.8. AlphaBeta............................................................................................................................................................
  
  
  • Section 7.9. References...........................................................................................................................................................
  
  
  • Chapter 8. Network Flow Algorithms.........................................................................................................................................
    
    
    • Section 8.1. Overview..............................................................................................................................................................
    
    
    • Section 8.2. Maximum Flow...................................................................................................................................................
    
    
    • Section 8.3. Bipartite Matching..............................................................................................................................................
    
    
    • Section 8.4. Reflections on Augmenting Paths......................................................................................................................
    
    
    • Section 8.5. Minimum Cost Flow............................................................................................................................................
    
    
    • Section 8.6. Transshipment....................................................................................................................................................
    
    
    • Section 8.7. Transportation.....................................................................................................................................................
    
    
    • Section 8.8. Assignment..........................................................................................................................................................
    
    
    • Section 8.9. Linear Programming...........................................................................................................................................
    
    
    • Section 8.10. References.........................................................................................................................................................
    
    
    
    
  
  
  • Chapter 9. Computational Geometry..........................................................................................................................................
    
    
    • Section 9.1. Overview...............................................................................................................................................................
    
    
    • Section 9.2. Convex Hull Scan................................................................................................................................................
    
    
    • Section 9.3. LineSweep............................................................................................................................................................
    
    
    • Section 9.4. Nearest Neighbor Queries..................................................................................................................................
    
    
    • Section 9.5. Range Queries.....................................................................................................................................................
    
    
    • Section 9.6. References...........................................................................................................................................................
    
    
    
    
  
  
  
  


• Part III: III..............................................................................................
  
  
  • Chapter 10. When All Else Fails.................................................................................................................................................
    
    
    • Section 10.1. Variations on a Theme.......................................................................................................................................
    
    
    • Section 10.2. Approximation Algorithms...............................................................................................................................
    
    
    • Section 10.3. Offline Algorithms.............................................................................................................................................
    
    
    • Section 10.4. Parallel Algorithms...........................................................................................................................................
    
    
    • Section 10.5. Randomized Algorithms...................................................................................................................................
    
    
    • Section 10.6. Algorithms That Can Be Wrong, but with Diminishing Probability.................................................................
    
    
    • Section 10.7. References..........................................................................................................................................................
    
    
    
    
  
  
  • Chapter 11. Epilogue....................................................................................................................................................................
    
    
    • Section 11.1. Overview..............................................................................................................................................................
    
    
    • Section 11.2. Principle: Know Your Data.................................................................................................................................
    
    
    • Section 11.3. Principle: Decompose the Problem into Smaller Problems..............................................................................
    
    
    • Section 11.4. Principle: Choose the Right Data Structure.......................................................................................................
    
    
    • Section 11.5. Principle: Add Storage to Increase Performance..............................................................................................
    
    
    • Section 11.6. Principle: If No Solution Is Evident, Construct a Search..................................................................................
    
    
    • Section 11.7. Principle: If No Solution Is Evident, Reduce Your Problem to Another Problem That Has a Solution..........
    
    
    • Section 11.8. Principle: Writing Algorithms Is Hard—Testing Algorithms Is Harder...........................................................
    
    
    
    
  
  
  
  


• Part IV: IV...............................................................................................
  
  
  • Appendix A. Benchmarking........................................................................................................................................................
    
    
    • Section A.1. Statistical Foundation.........................................................................................................................................
    
    
    • Section A.2. Hardware............................................................................................................................................................
    
    
    • Section A.3. Reporting.............................................................................................................................................................
    
    
    • Section A.4. Precision..............................................................................................................................................................
    
    
    
    
  
  
  
  


• About the Authors...................................................................................


• Colophon................................................................................................


• Print Publication Date: 2008/10/21 User number: Licensed by Ming Yi