Visions in Death

Based on a new classification of algorithm design techniques and a clear delineation of analysis methods, Introduction to the Design and Analysis of Algorithms, 3e presents the subject in a truly innovative manner. KEY TOPICS: Written in a reader-friendly style, the book encourages broad problem-solving skills while thoroughly covering the material required for introductory algorithms. The author emphasizes conceptual understanding before the introduction of the formal treatment of each technique. Popular puzzles are used to motivate readers' interest and strengthen their skills in algorithmic problem solving. Other enhancement features include chapter summaries, hints to the exercises, and a solution manual. MARKET: For those interested in learning more about algorithms. Cover 1 Title Page 4 Contents 8 New to the Third Edition 18 Preface 20 1 Introduction 28 1.1 What Is an Algorithm? 30 Exercises 1.1 34 1.2 Fundamentals of Algorithmic Problem Solving 36 Understanding the Problem 36 Ascertaining the Capabilities of the Computational Device 36 Choosing between Exact and Approximate Problem Solving 38 Algorithm Design Techniques 38 Designing an Algorithm and Data Structures 39 Methods of Specifying an Algorithm 39 Proving an Algorithm’s Correctness 40 Analyzing an Algorithm 41 Coding an Algorithm 42 Exercises 1.2 44 1.3 Important Problem Types 45 Sorting 46 Searching 47 String Processing 47 Graph Problems 48 Combinatorial Problems 48 Geometric Problems 49 Numerical Problems 49 Exercises 1.3 50 1.4 Fundamental Data Structures 52 Linear Data Structures 52 Graphs 55 Trees 58 Sets and Dictionaries 62 Exercises 1.4 64 Summary 65 2 Fundamentals of the Analysis of Algorithm Efficiency 68 2.1 The Analysis Framework 68 69 Measuring an Input’s Size 70 Units for Measuring Running Time 71 Orders of Growth 72 Worst-Case, Best-Case, and Average-Case Efficiencies 74 Recapitulation of the Analysis Framework 77 Exercises 2.1 77 2.2 Asymptotic Notations and Basic Efficiency Classes 79 Informal Introduction 79 O-notation 80 Ω-notation 81 Θ-notation 82 Useful Property Involving the Asymptotic Notations 82 Using Limits for Comparing Orders of Growth 83 Basic Efficiency Classes 85 Exercises 2.2 85 2.3 Mathematical Analysis of Nonrecursive Algorithms 88 Exercises 2.3 94 2.4 Mathematical Analysis of Recursive Algorithms 97 Exercises 2.4 103 2.5 Example: Computing the nth Fibonacci Number 107 Exercises 2.5 110 2.6 Empirical Analysis of Algorithms 111 Exercises 2.6 116 2.7 Algorithm Visualization 118 Summary 121 3 Brute Force and Exhaustive Search 124 3.1 Selection Sort and Bubble Sort 125 Selection Sort 125 Bubble Sort 127 Exercises 3.1 129 3.2 Sequential Search and Brute-Force String Matching 131 Sequential Search 131 Brute-Force String Matching 132 Exercises 3.2 133 3.3 Closest-Pair and Convex-Hull Problems by Brute Force 135 Closest-Pair Problem 135 Convex-Hull Problem 136 Exercises 3.3 140 3.4 Exhaustive Search 142 Traveling Salesman Problem 143 Knapsack Problem 143 Assignment Problem 146 Exercises 3.4 147 3.5 Depth-First Search and Breadth-First Search 149 Depth-First Search 149 Breadth-First Search 152 Exercises 3.5 155 Summary 157 4 Decrease-and-Conquer 158 4.1 Insertion Sort 161 Exercises 4.1 163 4.2 Topological Sorting 165 Exercises 4.2 169 4.3 Algorithms for Generating Combinatorial Objects 171 Generating Permutations 171 Generating Subsets 173 Exercises 4.3 175 4.4 Decrease-by-a-Constant-Factor Algorithms 177 Binary Search 177 Fake-Coin Problem 179 Russian Peasant Multiplication 180 Josephus Problem 181 Exercises 4.4 183 4.5 Variable-Size-Decrease Algorithms 184 Computing a Median and the 185 Interpolation Search 188 Searching and Insertion in a Binary Search Tree 190 The Game of Nim 191 Exercises 4.5 193 Summary 194 5 Divide-and-Conquer 196 5.1 Mergesort 199 Exercises 5.1 201 5.2 Quicksort 203 Exercises 5.2 208 5.3 Binary Tree Traversals and Related Properties 209 Exercises 5.3 212 5.4 Multiplication of Large Integers and Strassen’s Matrix Multiplication 213 Multiplication of Large Integers 214 Strassen’s Matrix Multiplication 216 Exercises 5.4 218 5.5 The Closest-Pair and Convex-Hull Problems by Divide-and-Conquer 219 The Closest-Pair Problem 219 Convex-Hull Problem 222 Exercises 5.5 224 Summary 225 6 Transform-and-Conquer 228 6.1 Presorting 229 Exercises 6.1 232 6.2 Gaussian Elimination 235 LU Decomposition 239 Computing a Matrix Inverse 241 Computing a Determinant 242 Exercises 6.2 243 6.3 Balanced Search Trees 245 AVL Trees 245 2-3 Trees 250 Exercises 6.3 252 6.4 Heaps and Heapsort 253 Notion of the Heap 254 Heapsort 258 Exercises 6.4 260 6.5 Horner’s Rule and Binary Exponentiation 261 Horner’s Rule 261 Binary Exponentiation 263 Exercises 6.5 266 6.6 Problem Reduction 267 Computing the Least Common Multiple 268 Counting Paths in a Graph 269 Reduction of Optimization Problems 270 Linear Programming 271 Reduction to Graph Problems 273 Exercises 6.6 275 Summary 277 7 Space and Time Trade-Offs 280 7.1 Sorting by Counting 281 Exercises 7.1 284 7.2 Input Enhancement in String Matching 285 Horspool’s Algorithm 286 Boyer-Moore Algorithm 290 Exercises 7.2 294 7.3 Hashing 296 Open Hashing (Separate Chaining) 297 Closed Hashing (Open Addressing) 299 Exercises 7.3 301 7.4 B-Trees 303 Exercises 7.4 306 Summary 307 8 Dynamic Programming 310 8.1 Three Basic Examples 312 Exercises 8.1 317 8.2 The Knapsack Problem and Memory Functions 319 Memory Functions 319 Exercises 8.2 323 8.3 Optimal Binary Search Trees 324 Exercises 8.3 330 8.4 Warshall’s and Floyd’s Algorithms 331 Warshall’s Algorithm 331 Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem 335 Exercises 8.4 338 Summary 339 9 Greedy Technique 342 9.1 Prim’s Algorithm 345 Exercises 9.1 349 9.2 Kruskal’s Algorithm 352 Disjoint Subsets and Union-Find Algorithms 354 Exercises 9.2 358 9.3 Dijkstra’s Algorithm 360 Exercises 9.3 364 9.4 Huffman Trees and Codes 365 Exercises 9.4 369 Summary 371 10 Iterative Improvement 372 10.1 The Simplex Method 373 Geometric Interpretation of Linear Programming 374 An Outline of the Simplex Method 378 Further Notes on the Simplex Method 384 Exercises 10.1 386 10.2 The Maximum-Flow Problem 388 Exercises 10.2 398 10.3 Maximum Matching in Bipartite Graphs 399 Exercises 10.3 405 10.4 The Stable Marriage Problem 407 Exercises 10.4 410 Summary 411 11 Limitations of Algorithm Power 414 11.1 Lower-Bound Arguments 415 Trivial Lower Bounds 416 Information-Theoretic Arguments 417 Adversary Arguments 417 Problem Reduction 418 Exercises 11.1 420 11.2 Decision Trees 421 Decision Trees for Sorting 422 Decision Trees for Searching a Sorted Array 424 Exercises 11.2 426 11.3 P, NP, and NP-Complete Problems 428 P and NP Problems 429 NP-Complete Problems 433 Exercises 11.3 436 11.4 Challenges of Numerical Algorithms 439 Exercises 11.4 446 Summary 447 12 Coping with the Limitations of Algorithm Power 450 12.1 Backtracking 451 n-Queens Problem 452 Hamiltonian Circuit Problem 453 Subset-Sum Problem 454 General Remarks 455 Exercises 12.1 457 12.2 Branch-and-Bound 459 Assignment Problem 460 Knapsack Problem 463 Traveling Salesman Problem 465 Exercises 12.2 467 12.3 Approximation Algorithms for NP-Hard Problems 468 Approximation Algorithms for the Traveling Salesman Problem 470 Approximation Algorithms for the Knapsack Problem 480 Exercises 12.3 484 12.4 Algorithms for Solving Nonlinear Equations 486 Bisection Method 487 Method of False Position 491 Newton’s Method 491 Exercises 12.4 494 Summary 495 Epilogue 498 APPENDIX A 502 Useful Formulas for the Analysis of Algorithms 502 Properties of Logarithms 502 Combinatorics 502 Important Summation Formulas 503 Sum Manipulation Rules 503 Approximation of a Sum by a Definite Integral 504 Floor and Ceiling Formulas 504 Miscellaneous 504 APPENDIX B 506 Short Tutorial on Recurrence Relations 506 Sequences and Recurrence Relations 506 Methods for Solving Recurrence Relations 507 Common Recurrence Types in Algorithm Analysis 512 References 520 Hints to Exercises 530 Index 572 Numbers and Symbols 572 A 572 B 573 C 575 D 576 E 577 F 578 G 579 H 580 I 581 J 581 K 581 L 581 M 583 N 584 O 584 P 584 Q 587 R 587 S 587 T 589 U 589 V 590 W 590 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 emphasises 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. The full text downloaded to your computer With eBooks you can: search for key concepts, words and phrases make highlights and notes as you study share your notes with friends eBooks are downloaded to your computer and accessible either offline through the Bookshelf (available as a free download), available online and also via the iPad and Android apps. Upon purchase, you'll gain instant access to this eBook. Time limit The eBooks products do not have an expiry date. You will continue to access your digital ebook products whilst you have your Bookshelf installed. 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.