Includes bibliographical references (p. [429]-434) and index.

Chapter 1. Analysis Basics -- 1.1. What is Analysis? -- 1.1.1. Input Classes -- 1.1.2. Space Complexity -- 1.1.3. Exercises -- 1.2. What to Count and Consider -- 1.2.1. Cases to Consider -- 1.2.2. Exercises -- 1.3. Mathematical Background -- 1.3.1. Logarithms -- 1.3.2. Binary Trees -- 1.3.3. Probabilities -- 1.3.4. Summations -- 1.3.5. Exercises -- 1.4. Rates of Growth -- 1.4.1. Classification of Growth -- 1.4.2. Exercises -- 1.5. Divide and Conquer Algorithms -- 1.5.1. Tournament Method -- 1.5.2. Lower Bounds -- 1.5.3. Exercises -- 1.6. Recurrence Relations -- 1.6.1. Exercises -- 1.7. Analyzing Programs -- Chapter 2. Searching and Selection Algorithms -- 2.1. Sequential Search -- 2.1.1. Worst-Case Analysis -- 2.1.2. Average-Case Analysis -- 2.1.3. Exercises -- 2.2. Binary Search -- 2.2.1. Worst-Case Analysis -- 2.2.2.

Average-Case Analysis -- 2.2.3. Exercises -- 2.3. Selection -- 2.3.1. Exercises -- 2.4. Programming Exercise -- Chapter 3. Sorting Algorithms -- 3.1. Insertion Sort -- 3.1.1. Worst-Case Analysis -- 3.1.2. Average-Case Analysis -- 3.1.3. Exercises -- 3.2. Bubble Sort -- 3.2.1. Best-Case Analysis -- 3.2.2. Worst-Case Analysis -- 3.2.3. Average-Case Analysis -- 3.2.4. Exercises -- 3.3. Shellsort -- 3.3.1. Algorithm Analysis -- 3.3.2. The Effect of the Increment -- 3.3.3. Exercises -- 3.4. Radix Sort -- 3.4.1. Analysis -- 3.4.2. Exercises -- 3.5. Heapsort -- 3.5.1. Worst-Case Analysis -- 3.5.2. Average-Case Analysis -- 3.5.3. Exercises -- 3.6. Merge Sort -- 3.6.1. MergeLists Analysis -- 3.6.2. MergeSort Analysis -- 3.6.3. Exercises -- 3.7. Quicksort -- 3.7.1. Worst-Case Analysis -- 3.7.2. Average-Case Analysis -- 3.7.3.

Exercises -- 3.8. External Polyphase Merge Sort -- 3.8.1. Number of Comparisons in Run Construction --

3.8.2. Number of Comparisons in Run Merge -- 3.8.3. Number of Block Reads -- 3.8.4. Exercises -- 3.9. Additional Exercises -- 3.10. Programming Exercises -- Chapter 4. Numeric Algorithms -- 4.1. Calculating Polynomials -- 4.1.1. Horner's Method -- 4.1.2. Preprocessed Coefficients -- 4.1.3. Exercises -- 4.2. Matrix Multiplication -- 4.2.1. Winograd's Matrix Multiplication -- 4.2.2. Strassen's Matrix Multiplication -- 4.2.3. Exercises -- 4.3. Linear Equations -- 4.3.1. Gauss-Jordan Method -- 4.3.2. Exercises -- Chapter 5. Matching Algorithms -- 5.1. String Matching -- 5.1.1. Finite Automata -- 5.1.2. Knuth-Morris-Pratt Algorithm -- 5.1.3. Boyer-Moore Algorithm -- 5.1.4. Exercises -- 5.2. Approximate String Matching -- 5.2.1. Analysis -- 5.2.2. Exercises -- 5.3. Programming Exercises -- Chapter 6. Graph Algorithms -- 6.1.

Graph Background and Terminology -- 6.1.1. Terminology -- 6.1.2. Exercises -- 6.2. Data Structure Methods for Graphs -- 6.2.1. The Adjacency Matrix -- 6.2.2. The Adjacency List -- 6.2.3. Exercises -- 6.3. Depth-First and Breadth-First Traversal Algorithms -- 6.3.1. Depth-First Traversal -- 6.3.2. Breadth-First Traversal -- 6.3.3. Traversal Analysis -- 6.3.4. Exercises -- 6.4. Minimum Spanning Tree Algorithm -- 6.4.1. The Dijkstra-Prim Algorithm -- 6.4.2. The Kruskal Algorithm -- 6.4.3. Exercises -- 6.5. Shortest-Path Algorithm -- 6.5.1. Dijkstra's Algorithm -- 6.5.2. Exercises -- 6.6. Biconnected Component Algorithm -- 6.6.1. Exercises -- 6.7. Partitioning Sets -- 6.8. Programming Exercises -- Chapter 7. Parallel Algorithms -- 7.1. Parallelism Introduction -- 7.1.1. Computer System Categories -- 7.1.2. Parallel Architectures -- 7.1.3.

Principles for Parallelism Analysis -- 7.1.4. Exercises -- 7.2. The PRAM Model -- 7.2.1. Exercises -- 7.3. Simple Parallel Operations --

7.3.1. Broadcasting Data in a CREW PRAM Model -- 7.3.2. Broadcasting Data in a EREW PRAM Model -- 7.3.3. Finding the Maximum Value in a List -- 7.3.4. Exercises -- 7.4. Parallel Searching -- 7.4.1. Exercises -- 7.5. Parallel Sorting -- 7.5.1. Linear Network Sort -- 7.5.2. Odd-Even Swap Sort -- 7.5.3. Other Parallel Sorts -- 7.5.4. Exercises -- 7.6. Parallel Numerical Algorithms -- 7.6.1. Matrix Multiplication on a Parallel Mesh -- 7.6.2. Matrix Multiplication in a CRCW PRAM Model -- 7.6.3. Solving Systems of Linear Equations with an SIMD Algorithm -- 7.6.4. Exercises -- 7.7. Parallel Graph Algorithms -- 7.7.1. Shortest-Path Parallel Algorithm -- 7.7.2. Minimum Spanning Tree Parallel Algorithm -- 7.7.3. Exercises -- Chapter 8. Nondeterministic Algorithms -- 8.1. What is NP? -- 8.1.1. Problem Reductions -- 8.1.2. NP-Complete Problems -- 8.2. Typical NP Problems --

8.2.1. Graph Coloring -- 8.2.2. Bin Packing -- 8.2.3. Backpack Problem -- 8.2.4. Subset Sum Problem -- 8.2.5. CNF-Satisfiability Problem -- 8.2.6. Job Scheduling Problem -- 8.2.7. Exercises -- 8.3. What Makes Something NP? -- 8.3.1. Is P = NP? -- 8.3.2. Exercises -- 8.4. Testing Possible Solutions -- 8.4.1. Job Scheduling -- 8.4.2. Graph Coloring -- 8.4.3. Exercises -- Chapter 9. Other Algorithmic Techniques -- 9.1. Greedy Approximation Algorithms -- 9.1.1. Traveling Salesperson Approximations -- 9.1.2. Bin Packing Approximations -- 9.1.3. Backpack Approximation -- 9.1.4. Subset Sum Approximation -- 9.1.5. Graph Coloring Approximation -- 9.1.6. Exercises -- 9.2. Probabilistic Algorithms -- 9.2.1. Numerical Probabilistic Algorithms -- 9.2.2. Monte Carlo Algorithms -- 9.2.3. Las Vegas Algorithms -- 9.2.4. Sherwood Algorithms -- 9.2.5.

Probabilistic Algorithm Comparison -- 9.2.6. Exercises -- 9.3. Dynamic Programming --

9.3.1. Array-Based Methods -- 9.3.2. Dynamic Matrix Multiplication -- 9.3.3. Exercises -- 9.4. Programming Exercises -- Appendix A. Random Number Table -- Appendix B. Pseudorandom Number Generation -- Appendix C. Results of Chapter Study Suggestion -- Appendix D. References.