TY  - BOOK
AU  - McConnell,Jeffrey J.
TI  - Analysis of algorithms: an active learning approach 
SN  - 9780763707828 :
AV  - QA76.9.A43 M38 2008
PY  - 2008///
CY  - Sudbury, Mass.
PB  - Jones and Bartlett Publishers
KW  - Computer algorithms
N1  - 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
ER  -