Introduction to the Design and Analysis of Algorithms (2nd Edition)

Based on a new classification of algorithm design techniques and a clear delineation of analysis methods, Introduction to the Design and Analysis of Algorithms presents the subject in a coherent and innovative manner. Written in a student-friendly style, the book emphasizes the understanding of ideas over excessively formal treatment while thoroughly covering the material required in an introductory algorithms course. Popular puzzles are used to motivate students' interest and strengthen their skills in algorithmic problem solving. Other learning-enhancement features include chapter summaries, hints to the exercises, and a detailed solution manual. Cover......Page 1 Copyright Page......Page 4 Title Page......Page 5 Brief Contents......Page 7 Contents......Page 9 New to the Third Edition......Page 19 Preface......Page 21 Acknowledgments......Page 26 1 Introduction......Page 29 1.1 What Is an Algorithm?......Page 31 Exercises 1.1......Page 35 Ascertaining the Capabilities of the Computational Device......Page 37 Algorithm Design Techniques......Page 39 Methods of Specifying an Algorithm......Page 40 Proving an Algorithm’s Correctness......Page 41 Analyzing an Algorithm......Page 42 Coding an Algorithm......Page 43 Exercises 1.2......Page 45 1.3 Important Problem Types......Page 46 Sorting......Page 47 String Processing......Page 48 Combinatorial Problems......Page 49 Numerical Problems......Page 50 Exercises 1.3......Page 51 Linear Data Structures......Page 53 Graphs......Page 56 Trees......Page 59 Sets and Dictionaries......Page 63 Exercises 1.4......Page 65 Summary......Page 66 2 Fundamentals of the Analysis of Algorithm Efficiency......Page 69 2.1 The Analysis Framework......Page 70 Measuring an Input’s Size......Page 71 Units for Measuring Running Time......Page 72 Orders of Growth......Page 73 Worst-Case, Best-Case, and Average-Case Efficiencies......Page 75 Exercises 2.1......Page 78 Informal Introduction......Page 80 O-notation......Page 81 Ω-notation......Page 82 Useful Property Involving the Asymptotic Notations......Page 83 Using Limits for Comparing Orders of Growth......Page 84 Exercises 2.2......Page 86 2.3 Mathematical Analysis of Nonrecursive Algorithms......Page 89 Exercises 2.3......Page 95 2.4 Mathematical Analysis of Recursive Algorithms......Page 98 Exercises 2.4......Page 104 2.5 Example: Computing the nth Fibonacci Number......Page 108 Exercises 2.5......Page 111 2.6 Empirical Analysis of Algorithms......Page 112 Exercises 2.6......Page 117 2.7 Algorithm Visualization......Page 119 Summary......Page 122 3 Brute Force and Exhaustive Search......Page 125 Selection Sort......Page 126 Bubble Sort......Page 128 Exercises 3.1......Page 130 Sequential Search......Page 132 Brute-Force String Matching......Page 133 Exercises 3.2......Page 134 Closest-Pair Problem......Page 136 Convex-Hull Problem......Page 137 Exercises 3.3......Page 141 3.4 Exhaustive Search......Page 143 Knapsack Problem......Page 144 Assignment Problem......Page 147 Exercises 3.4......Page 148 Depth-First Search......Page 150 Breadth-First Search......Page 153 Exercises 3.5......Page 156 Summary......Page 158 4 Decrease-and-Conquer......Page 159 4.1 Insertion Sort......Page 162 Exercises 4.1......Page 164 4.2 Topological Sorting......Page 166 Exercises 4.2......Page 170 Generating Permutations......Page 172 Generating Subsets......Page 174 Exercises 4.3......Page 176 Binary Search......Page 178 Fake-Coin Problem......Page 180 Russian Peasant Multiplication......Page 181 Josephus Problem......Page 182 Exercises 4.4......Page 184 4.5 Variable-Size-Decrease Algorithms......Page 185 Computing a Median and the Selection Problem......Page 186 Interpolation Search......Page 189 Searching and Insertion in a Binary Search Tree......Page 191 The Game of Nim......Page 192 Exercises 4.5......Page 194 Summary......Page 195 5 Divide-and-Conquer......Page 197 5.1 Mergesort......Page 200 Exercises 5.1......Page 202 5.2 Quicksort......Page 204 Exercises 5.2......Page 209 5.3 Binary Tree Traversals and Related Properties......Page 210 Exercises 5.3......Page 213 5.4 Multiplication of Large Integers and Strassen’s Matrix Multiplication......Page 214 Multiplication of Large Integers......Page 215 Strassen’s Matrix Multiplication......Page 217 Exercises 5.4......Page 219 The Closest-Pair Problem......Page 220 Convex-Hull Problem......Page 223 Exercises 5.5......Page 225 Summary......Page 226 6 Transform-and-Conquer......Page 229 6.1 Presorting......Page 230 Exercises 6.1......Page 233 6.2 Gaussian Elimination......Page 236 LU Decomposition......Page 240 Computing a Matrix Inverse......Page 242 Computing a Determinant......Page 243 Exercises 6.2......Page 244 AVL Trees......Page 246 2-3 Trees......Page 251 Exercises 6.3......Page 253 6.4 Heaps and Heapsort......Page 254 Notion of the Heap......Page 255 Heapsort......Page 259 Exercises 6.4......Page 261 Horner’s Rule......Page 262 Binary Exponentiation......Page 264 Exercises 6.5......Page 267 6.6 Problem Reduction......Page 268 Computing the Least Common Multiple......Page 269 Counting Paths in a Graph......Page 270 Reduction of Optimization Problems......Page 271 Linear Programming......Page 272 Reduction to Graph Problems......Page 274 Exercises 6.6......Page 276 Summary......Page 278 7 Space and Time Trade-Offs......Page 281 7.1 Sorting by Counting......Page 282 Exercises 7.1......Page 285 7.2 Input Enhancement in String Matching......Page 286 Horspool’s Algorithm......Page 287 Boyer-Moore Algorithm......Page 291 Exercises 7.2......Page 295 7.3 Hashing......Page 297 Open Hashing (Separate Chaining)......Page 298 Closed Hashing (Open Addressing)......Page 300 Exercises 7.3......Page 302 7.4 B-Trees......Page 304 Exercises 7.4......Page 307 Summary......Page 308 8 Dynamic Programming......Page 311 8.1 Three Basic Examples......Page 313 Exercises 8.1......Page 318 8.2 The Knapsack Problem and Memory Functions......Page 320 Memory Functions......Page 322 Exercises 8.2......Page 324 8.3 Optimal Binary Search Trees......Page 325 Exercises 8.3......Page 331 Warshall’s Algorithm......Page 332 Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem......Page 336 Exercises 8.4......Page 339 Summary......Page 340 9 Greedy Technique......Page 343 9.1 Prim’s Algorithm......Page 346 Exercises 9.1......Page 350 9.2 Kruskal’s Algorithm......Page 353 Disjoint Subsets and Union-Find Algorithms......Page 355 Exercises 9.2......Page 359 9.3 Dijkstra’s Algorithm......Page 361 Exercises 9.3......Page 365 9.4 Huffman Trees and Codes......Page 366 Exercises 9.4......Page 370 Summary......Page 372 10 Iterative Improvement......Page 373 10.1 The Simplex Method......Page 374 Geometric Interpretation of Linear Programming......Page 375 An Outline of the Simplex Method......Page 379 Further Notes on the Simplex Method......Page 385 Exercises 10.1......Page 387 10.2 The Maximum-Flow Problem......Page 389 Exercises 10.2......Page 399 10.3 Maximum Matching in Bipartite Graphs......Page 400 Exercises 10.3......Page 406 10.4 The Stable Marriage Problem......Page 408 Exercises 10.4......Page 411 Summary......Page 412 11 Limitations of Algorithm Power......Page 415 11.1 Lower-Bound Arguments......Page 416 Trivial Lower Bounds......Page 417 Adversary Arguments......Page 418 Problem Reduction......Page 419 Exercises 11.1......Page 421 11.2 Decision Trees......Page 422 Decision Trees for Sorting......Page 423 Decision Trees for Searching a Sorted Array......Page 425 Exercises 11.2......Page 427 11.3 P, NP, and NP-Complete Problems......Page 429 P and NP Problems......Page 430 NP-Complete Problems......Page 434 Exercises 11.3......Page 437 11.4 Challenges of Numerical Algorithms......Page 440 Exercises 11.4......Page 447 Summary......Page 448 12 Coping with the Limitations of Algorithm Power......Page 451 12.1 Backtracking......Page 452 n-Queens Problem......Page 453 Hamiltonian Circuit Problem......Page 454 Subset-Sum Problem......Page 455 General Remarks......Page 456 Exercises 12.1......Page 458 12.2 Branch-and-Bound......Page 460 Assignment Problem......Page 461 Knapsack Problem......Page 464 Traveling Salesman Problem......Page 466 Exercises 12.2......Page 468 12.3 Approximation Algorithms for NP-Hard Problems......Page 469 Approximation Algorithms for the Traveling Salesman Problem......Page 471 Approximation Algorithms for the Knapsack Problem......Page 481 Exercises 12.3......Page 485 12.4 Algorithms for Solving Nonlinear Equations......Page 487 Bisection Method......Page 488 Newton’s Method......Page 492 Exercises 12.4......Page 495 Summary......Page 496 Epilogue......Page 499 Combinatorics......Page 503 Sum Manipulation Rules......Page 504 Miscellaneous......Page 505 Sequences and Recurrence Relations......Page 507 Methods for Solving Recurrence Relations......Page 508 Common Recurrence Types in Algorithm Analysis......Page 513 References......Page 521 Hints to Exercises......Page 531 A......Page 575 B......Page 576 C......Page 578 D......Page 579 E......Page 580 F......Page 581 G......Page 582 I......Page 583 L......Page 584 M......Page 586 P......Page 587 S......Page 590 U......Page 592 W......Page 593 Cover 1 Copyright Page 4 Title Page 5 Brief Contents 7 Contents 9 New to the Third Edition 19 Preface 21 Acknowledgments 26 1 Introduction 29 1.1 What Is an Algorithm? 31 Exercises 1.1 35 1.2 Fundamentals of Algorithmic Problem Solving 37 Understanding the Problem 37 Ascertaining the Capabilities of the Computational Device 37 Choosing between Exact and Approximate Problem Solving 39 Algorithm Design Techniques 39 Designing an Algorithm and Data Structures 40 Methods of Specifying an Algorithm 40 Proving an Algorithm鈥檚 Correctness 41 Analyzing an Algorithm 42 Coding an Algorithm 43 Exercises 1.2 45 1.3 Important Problem Types 46 Sorting 47 Searching 48 String Processing 48 Graph Problems 49 Combinatorial Problems 49 Geometric Problems 50 Numerical Problems 50 Exercises 1.3 51 1.4 Fundamental Data Structures 53 Linear Data Structures 53 Graphs 56 Trees 59 Sets and Dictionaries 63 Exercises 1.4 65 Summary 66 2 Fundamentals of the Analysis of Algorithm Efficiency 69 2.1 The Analysis Framework 70 Measuring an Input鈥檚 Size 71 Units for Measuring Running Time 72 Orders of Growth 73 Worst-Case, Best-Case, and Average-Case Efficiencies 75 Recapitulation of the Analysis Framework 78 Exercises 2.1 78 2.2 Asymptotic Notations and Basic Efficiency Classes 80 Informal Introduction 80 O-notation 81 惟-notation 82 螛-notation 83 Useful Property Involving the Asymptotic Notations 83 Using Limits for Comparing Orders of Growth 84 Basic Efficiency Classes 86 Exercises 2.2 86 2.3 Mathematical Analysis of Nonrecursive Algorithms 89 Exercises 2.3 95 2.4 Mathematical Analysis of Recursive Algorithms 98 Exercises 2.4 104 2.5 Example: Computing the nth Fibonacci Number 108 Exercises 2.5 111 2.6 Empirical Analysis of Algorithms 112 Exercises 2.6 117 2.7 Algorithm Visualization 119 Summary 122 3 Brute Force and Exhaustive Search 125 3.1 Selection Sort and Bubble Sort 126 Selection Sort 126 Bubble Sort 128 Exercises 3.1 130 3.2 Sequential Search and Brute-Force String Matching 132 Sequential Search 132 Brute-Force String Matching 133 Exercises 3.2 134 3.3 Closest-Pair and Convex-Hull Problems by Brute Force 136 Closest-Pair Problem 136 Convex-Hull Problem 137 Exercises 3.3 141 3.4 Exhaustive Search 143 Traveling Salesman Problem 144 Knapsack Problem 144 Assignment Problem 147 Exercises 3.4 148 3.5 Depth-First Search and Breadth-First Search 150 Depth-First Search 150 Breadth-First Search 153 Exercises 3.5 156 Summary 158 4 Decrease-and-Conquer 159 4.1 Insertion Sort 162 Exercises 4.1 164 4.2 Topological Sorting 166 Exercises 4.2 170 4.3 Algorithms for Generating Combinatorial Objects 172 Generating Permutations 172 Generating Subsets 174 Exercises 4.3 176 4.4 Decrease-by-a-Constant-Factor Algorithms 178 Binary Search 178 Fake-Coin Problem 180 Russian Peasant Multiplication 181 Josephus Problem 182 Exercises 4.4 184 4.5 Variable-Size-Decrease Algorithms 185 Computing a Median and the Selection Problem 186 Interpolation Search 189 Searching and Insertion in a Binary Search Tree 191 The Game of Nim 192 Exercises 4.5 194 Summary 195 5 Divide-and-Conquer 197 5.1 Mergesort 200 Exercises 5.1 202 5.2 Quicksort 204 Exercises 5.2 209 5.3 Binary Tree Traversals and Related Properties 210 Exercises 5.3 213 5.4 Multiplication of Large Integers and Strassen鈥檚 Matrix Multiplication 214 Multiplication of Large Integers 215 Strassen鈥檚 Matrix Multiplication 217 Exercises 5.4 219 5.5 The Closest-Pair and Convex-Hull Problems by Divide-and-Conquer 220 The Closest-Pair Problem 220 Convex-Hull Problem 223 Exercises 5.5 225 Summary 226 6 Transform-and-Conquer 229 6.1 Presorting 230 Exercises 6.1 233 6.2 Gaussian Elimination 236 LU Decomposition 240 Computing a Matrix Inverse 242 Computing a Determinant 243 Exercises 6.2 244 6.3 Balanced Search Trees 246 AVL Trees 246 2-3 Trees 251 Exercises 6.3 253 6.4 Heaps and Heapsort 254 Notion of the Heap 255 Heapsort 259 Exercises 6.4 261 6.5 Horner鈥檚 Rule and Binary Exponentiation 262 Horner鈥檚 Rule 262 Binary Exponentiation 264 Exercises 6.5 267 6.6 Problem Reduction 268 Computing the Least Common Multiple 269 Counting Paths in a Graph 270 Reduction of Optimization Problems 271 Linear Programming 272 Reduction to Graph Problems 274 Exercises 6.6 276 Summary 278 7 Space and Time Trade-Offs 281 7.1 Sorting by Counting 282 Exercises 7.1 285 7.2 Input Enhancement in String Matching 286 Horspool鈥檚 Algorithm 287 Boyer-Moore Algorithm 291 Exercises 7.2 295 7.3 Hashing 297 Open Hashing (Separate Chaining) 298 Closed Hashing (Open Addressing) 300 Exercises 7.3 302 7.4 B-Trees 304 Exercises 7.4 307 Summary 308 8 Dynamic Programming 311 8.1 Three Basic Examples 313 Exercises 8.1 318 8.2 The Knapsack Problem and Memory Functions 320 Memory Functions 322 Exercises 8.2 324 8.3 Optimal Binary Search Trees 325 Exercises 8.3 331 8.4 Warshall鈥檚 and Floyd鈥檚 Algorithms 332 Warshall鈥檚 Algorithm 332 Floyd鈥檚 Algorithm for the All-Pairs Shortest-Paths Problem 336 Exercises 8.4 339 Summary 340 9 Greedy Technique 343 9.1 Prim鈥檚 Algorithm 346 Exercises 9.1 350 9.2 Kruskal鈥檚 Algorithm 353 Disjoint Subsets and Union-Find Algorithms 355 Exercises 9.2 359 9.3 Dijkstra鈥檚 Algorithm 361 Exercises 9.3 365 9.4 Huffman Trees and Codes 366 Exercises 9.4 370 Summary 372 10 Iterative Improvement 373 10.1 The Simplex Method 374 Geometric Interpretation of Linear Programming 375 An Outline of the Simplex Method 379 Further Notes on the Simplex Method 385 Exercises 10.1 387 10.2 The Maximum-Flow Problem 389 Exercises 10.2 399 10.3 Maximum Matching in Bipartite Graphs 400 Exercises 10.3 406 10.4 The Stable Marriage Problem 408 Exercises 10.4 411 Summary 412 11 Limitations of Algorithm Power 415 11.1 Lower-Bound Arguments 416 Trivial Lower Bounds 417 Information-Theoretic Arguments 418 Adversary Arguments 418 Problem Reduction 419 Exercises 11.1 421 11.2 Decision Trees 422 Decision Trees for Sorting 423 Decision Trees for Searching a Sorted Array 425 Exercises 11.2 427 11.3 P, NP, and NP-Complete Problems 429 P and NP Problems 430 NP-Complete Problems 434 Exercises 11.3 437 11.4 Challenges of Numerical Algorithms 440 Exercises 11.4 447 Summary 448 12 Coping with the Limitations of Algorithm Power 451 12.1 Backtracking 452 n-Queens Problem 453 Hamiltonian Circuit Problem 454 Subset-Sum Problem 455 General Remarks 456 Exercises 12.1 458 12.2 Branch-and-Bound 460 Assignment Problem 461 Knapsack Problem 464 Traveling Salesman Problem 466 Exercises 12.2 468 12.3 Approximation Algorithms for NP-Hard Problems 469 Approximation Algorithms for the Traveling Salesman Problem 471 Approximation Algorithms for the Knapsack Problem 481 Exercises 12.3 485 12.4 Algorithms for Solving Nonlinear Equations 487 Bisection Method 488 Method of False Position 492 Newton鈥檚 Method 492 Exercises 12.4 495 Summary 496 Epilogue 499 APPENDIX A: Useful Formulas for the Analysis of Algorithms 503 Properties of Logarithms 503 Combinatorics 503 Important Summation Formulas 504 Sum Manipulation Rules 504 Approximation of a Sum by a Definite Integral 505 Floor and Ceiling Formulas 505 Miscellaneous 505 APPENDIX B: Short Tutorial on Recurrence Relations 507 Sequences and Recurrence Relations 507 Methods for Solving Recurrence Relations 508 Common Recurrence Types in Algorithm Analysis 513 References 521 Hints to Exercises 531 Index 575 A 575 B 576 C 578 D 579 E 580 F 581 G 582 H 583 I 583 J 584 K 584 L 584 M 586 N 587 O 587 P 587 Q 590 R 590 S 590 T 592 U 592 V 593 W 593