Introduction to the Design and Analysis of Algorithms, 3rd 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