| |

| |

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 | |