| |
| |
Preface | |
| |
| |
| |
Analysis Basics | |
| |
| |
| |
What is Analysis? | |
| |
| |
| |
Input Classes | |
| |
| |
| |
Space Complexity | |
| |
| |
| |
Exercises | |
| |
| |
| |
What to Count and Consider | |
| |
| |
| |
Cases to Consider | |
| |
| |
| |
Exercises | |
| |
| |
| |
Mathematical Background | |
| |
| |
| |
Logarithms | |
| |
| |
| |
Binary Trees | |
| |
| |
| |
Probabilities | |
| |
| |
| |
Summations | |
| |
| |
| |
Exercises | |
| |
| |
| |
Rates of Growth | |
| |
| |
| |
Classification of Growth | |
| |
| |
| |
Exercises | |
| |
| |
| |
Divide and Conquer Algorithms | |
| |
| |
| |
Tournament Method | |
| |
| |
| |
Lower Bounds | |
| |
| |
| |
Exercises | |
| |
| |
| |
Recurrence Relations | |
| |
| |
| |
Exercises | |
| |
| |
| |
Analyzing Programs | |
| |
| |
| |
Searching and Selection Algorithms | |
| |
| |
| |
Sequential Search | |
| |
| |
| |
Worst-Case Analysis | |
| |
| |
| |
Average-Case Analysis | |
| |
| |
| |
Exercises | |
| |
| |
| |
Binary Search | |
| |
| |
| |
Worst-Case Analysis | |
| |
| |
| |
Average-Case Analysis | |
| |
| |
| |
Exercises | |
| |
| |
| |
Selection | |
| |
| |
| |
Exercises | |
| |
| |
| |
Programming Exercise | |
| |
| |
| |
Sorting Algorithms | |
| |
| |
| |
Insertion Sort | |
| |
| |
| |
Worst-Case Analysis | |
| |
| |
| |
Average-Case Analysis | |
| |
| |
| |
Exercises | |
| |
| |
| |
Bubble Sort | |
| |
| |
| |
Best-Case Analysis | |
| |
| |
| |
Worst-Case Analysis | |
| |
| |
| |
Average-Case Analysis | |
| |
| |
| |
Exercises | |
| |
| |
| |
Shellsort | |
| |
| |
| |
Algorithm Analysis | |
| |
| |
| |
The Effect of the Increment | |
| |
| |
| |
Exercises | |
| |
| |
| |
Radix Sort | |
| |
| |
| |
Analysis | |
| |
| |
| |
Exercises | |
| |
| |
| |
Heapsort | |
| |
| |
| |
Worst-Case Analysis | |
| |
| |
| |
Average-Case Analysis | |
| |
| |
| |
Exercises | |
| |
| |
| |
Merge Sort | |
| |
| |
| |
MergeLists Analysis | |
| |
| |
| |
MergeSort Analysis | |
| |
| |
| |
Exercises | |
| |
| |
| |
Quicksort | |
| |
| |
| |
Worst-Case Analysis | |
| |
| |
| |
Average-Case Analysis | |
| |
| |
| |
Exercises | |
| |
| |
| |
External Polyphase Merge Sort | |
| |
| |
| |
Number of Comparisons in Run Construction | |
| |
| |
| |
Number of Comparisons in Run Merge | |
| |
| |
| |
Number of Block Reads | |
| |
| |
| |
Exercises | |
| |
| |
| |
Additional Exercises | |
| |
| |
| |
Programming Exercises | |
| |
| |
| |
Numeric Algorithms | |
| |
| |
| |
Calculating Polynomials | |
| |
| |
| |
Horner's Method | |
| |
| |
| |
Preprocessed Coefficients | |
| |
| |
| |
Exercises | |
| |
| |
| |
Matrix Multiplication | |
| |
| |
| |
Winograd's Matrix Multiplication | |
| |
| |
| |
Strassen's Matrix Multiplication | |
| |
| |
| |
Exercises | |
| |
| |
| |
Linear Equations | |
| |
| |
| |
Gauss-Jordan Method | |
| |
| |
| |
Exercises | |
| |
| |
| |
Matching Algorithms | |
| |
| |
| |
String Matching | |
| |
| |
| |
Finite Automata | |
| |
| |
| |
Knuth-Morris-Pratt Algorithm | |
| |
| |
| |
Boyer-Moore Algorithm | |
| |
| |
| |
Exercises | |
| |
| |
| |
Approximate String Matching | |
| |
| |
| |
Analysis | |
| |
| |
| |
Exercises | |
| |
| |
| |
Programming Exercises | |
| |
| |
| |
Graph Algorithms | |
| |
| |
| |
Graph Background and Terminology | |
| |
| |
| |
Terminology | |
| |
| |
| |
Exercises | |
| |
| |
| |
Data Structure Methods for Graphs | |
| |
| |
| |
The Adjacency Matrix | |
| |
| |
| |
The Adjacency List | |
| |
| |
| |
Exercises | |
| |
| |
| |
Depth-First and Breadth-First Traversal Algorithms | |
| |
| |
| |
Depth-First Traversal | |
| |
| |
| |
Breadth-First Traversal | |
| |
| |
| |
Traversal Analysis | |
| |
| |
| |
Exercises | |
| |
| |
| |
Minimum Spanning Tree Algorithm | |
| |
| |
| |
The Dijkstra-Prim Algorithm | |
| |
| |
| |
The Kruskal Algorithm | |
| |
| |
| |
Exercises | |
| |
| |
| |
Shortest-Path Algorithm | |
| |
| |
| |
Dijkstra's Algorithm | |
| |
| |
| |
Exercises | |
| |
| |
| |
Biconnected Component Algorithm | |
| |
| |
| |
Exercises | |
| |
| |
| |
Partitioning Sets | |
| |
| |
| |
Programming Exercises | |
| |
| |
| |
Parallel Algorithms | |
| |
| |
| |
Parallelism Introduction | |
| |
| |
| |
Computer System Categories | |
| |
| |
| |
Parallel Architectures | |
| |
| |
| |
Principles for Parallelism Analysis | |
| |
| |
| |
Exercises | |
| |
| |
| |
The PRAM Model | |
| |
| |
| |
Exercises | |
| |
| |
| |
Simple Parallel Operations | |
| |
| |
| |
Broadcasting Data in a CREW PRAM Model | |
| |
| |
| |
Broadcasting Data in a EREW PRAM Model | |
| |
| |
| |
Finding the Maximum Value in a List | |
| |
| |
| |
Exercises | |
| |
| |
| |
Parallel Searching | |
| |
| |
| |
Exercises | |
| |
| |
| |
Parallel Sorting | |
| |
| |
| |
Linear Network Sort | |
| |
| |
| |
Odd-Even Swap Sort | |
| |
| |
| |
Other Parallel Sorts | |
| |
| |
| |
Exercises | |
| |
| |
| |
Parallel Numerical Algorithms | |
| |
| |
| |
Matrix Multiplication on a Parallel Mesh | |
| |
| |
| |
Matrix Multiplication in a CRCW PRAM Model | |
| |
| |
| |
Solving Systems of Linear Equations with an SIMD Algorithm | |
| |
| |
| |
Exercises | |
| |
| |
| |
Parallel Graph Algorithms | |
| |
| |
| |
Shortest-Path Parallel Algorithm | |
| |
| |
| |
Minimum Spanning Tree Parallel Algorithm | |
| |
| |
| |
Exercises | |
| |
| |
| |
Nondeterministic Algorithms | |
| |
| |
| |
What is NP? | |
| |
| |
| |
Problem Reductions | |
| |
| |
| |
NP-Complete Problems | |
| |
| |
| |
Typical NP Problems | |
| |
| |
| |
Graph Coloring | |
| |
| |
| |
Bin Packing | |
| |
| |
| |
Backpack Problem | |
| |
| |
| |
Subset Sum Problem | |
| |
| |
| |
CNF-Satisfiability Problem | |
| |
| |
| |
Job Scheduling Problem | |
| |
| |
| |
Exercises | |
| |
| |
| |
What Makes Something NP? | |
| |
| |
| |
Is P = NP? | |
| |
| |
| |
Exercises | |
| |
| |
| |
Testing Possible Solutions | |
| |
| |
| |
Job Scheduling | |
| |
| |
| |
Graph Coloring | |
| |
| |
| |
Exercises | |
| |
| |
| |
Other Algorithmic Techniques | |
| |
| |
| |
Greedy Approximation Algorithms | |
| |
| |
| |
Traveling Salesperson Approximations | |
| |
| |
| |
Bin Packing Approximations | |
| |
| |
| |
Backpack Approximation | |
| |
| |
| |
Subset Sum Approximation | |
| |
| |
| |
Graph Coloring Approximation | |
| |
| |
| |
Exercises | |
| |
| |
| |
Probabilistic Algorithms | |
| |
| |
| |
Numerical Probabilistic Algorithms | |
| |
| |
| |
Monte Carlo Algorithms | |
| |
| |
| |
Las Vegas Algorithms | |
| |
| |
| |
Sherwood Algorithms | |
| |
| |
| |
Probabilistic Algorithm Comparison | |
| |
| |
| |
Exercises | |
| |
| |
| |
Dynamic Programming | |
| |
| |
| |
Array-Based Methods | |
| |
| |
| |
Dynamic Matrix Multiplication | |
| |
| |
| |
Exercises | |
| |
| |
| |
Programming Exercises | |
| |
| |
| |
Random Number Table | |
| |
| |
| |
Pseudorandom Number Generation | |
| |
| |
| |
Results of Chapter Study Suggestion | |
| |
| |
| |
References | |
| |
| |
Index | |