Note: Supplemental materials are not guaranteed with Rental or Used book purchases.
Purchase Benefits
Free Shipping On Orders Over $59!
Your order must be $59 or more to qualify for free economy shipping. Bulk sales, PO's, Marketplace items, eBooks and apparel do not qualify for this offer.
Get Rewarded for Ordering Your Textbooks!Enroll Now
The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
The Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.
Summary
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.
Author Biography
Dr. Anany Levitin graduated from the Moscow State University with an MS degree in Mathematics. He holds a Ph.D. degree in Mathematics from the Hebrew University of Jerusalem and an MS degree in Computer Science from the University of Kentucky. Introduction to the Design and Analysis of Algorithms has been translated into Chinese, Russian, Greek, and Korean and is used in hundreds of schools all over the world. Dr. Levitin is also the author of Algorithmic Puzzles, publishing in Fall 2011.
Dr. Levitin teaches courses in the Design and Analysis of Algorithms at Villanova University.
Table of Contents
New to the Third Edition xvii Preface xix 1Introduction 1 1.1 What Is an Algorithm? 3 Exercises 1.1 7 1.2 Fundamentals of Algorithmic Problem Solving 9 Understanding the Problem 9 Ascertaining the Capabilities of the Computational Device 9 Choosing between Exact and Approximate Problem Solving 11 Algorithm Design Techniques 11 Designing an Algorithm and Data Structures 12 Methods of Specifying an Algorithm 12 Proving an Algorithm’s Correctness 13 Analyzing an Algorithm 14 Coding an Algorithm 15 Exercises 1.2 17 1.3 Important Problem Types 18 Sorting 19 Searching 20 String Processing 20 Graph Problems 21 Combinatorial Problems 21 Geometric Problems 22 Numerical Problems 22 Exercises 1.3 23 1.4 Fundamental Data Structures 25 Linear Data Structures 25 Graphs 28 Trees 31 Sets and Dictionaries 35 Exercises 1.4 37 Summary 38
2 Fundamentals of the Analysis of Algorithm Efficiency 41 2.1 The Analysis Framework 42 Measuring an Input’s Size 43 Units for Measuring Running Time 44 Orders of Growth 45 Worst-Case, Best-Case, and Average-Case Efficiencies 47 Recapitulation of the Analysis Framework 50 Exercises 2.1 50 2.2 Asymptotic Notations and Basic Efficiency Classes 52 Informal Introduction 52 O-notation 53 -notation 54 -notation 55 Useful Property Involving the Asymptotic Notations 55 Using Limits for Comparing Orders of Growth 56 Basic Efficiency Classes 58 Exercises 2.2 58 2.3 Mathematical Analysis of Nonrecursive Algorithms 61 Exercises 2.3 67 2.4 Mathematical Analysis of Recursive Algorithms 70 Exercises 2.4 76 2.5 Example: Computing the nth Fibonacci Number 80 Exercises 2.5 83 2.6 Empirical Analysis of Algorithms 84 Exercises 2.6 89 2.7 Algorithm Visualization 91 Summary 94
3 Brute Force and Exhaustive Search 97 3.1 Selection Sort and Bubble Sort 98 Selection Sort 98 Bubble Sort 100 Exercises 3.1 102 3.2 Sequential Search and Brute-Force String Matching 104 Sequential Search 104 Brute-Force String Matching 105 Exercises 3.2 106 3.3 Closest-Pair and Convex-Hull Problems by Brute Force 108 Closest-Pair Problem 108 Convex-Hull Problem 109 Exercises 3.3 113 3.4 Exhaustive Search 115 Traveling Salesman Problem 116 Knapsack Problem 116 Assignment Problem 119 Exercises 3.4 120 3.5 Depth-First Search and Breadth-First Search 122 Depth-First Search 122 Breadth-First Search 125 Exercises 3.5 128 Summary 130
4 Decrease-and-Conquer 131 4.1 Insertion Sort 134 Exercises 4.1 136 4.2 Topological Sorting 138 Exercises 4.2 142 4.3 Algorithms for Generating Combinatorial Objects 144 Generating Permutations 144 Generating Subsets 146 Exercises 4.3 148 4.4 Decrease-by-a-Constant-Factor Algorithms 150 Binary Search 150 Fake-Coin Problem 152 Russian Peasant Multiplication 153 Josephus Problem 154 Exercises 4.4 156 4.5 Variable-Size-Decrease Algorithms 157 Computing a Median and the Selection Problem 158 Interpolation Search 161 Searching and Insertion in a Binary Search Tree 163 The Game of Nim 164 Exercises 4.5 166 Summary 167
5 Divide-and-Conquer 169 5.1 Mergesort 172 Exercises 5.1 174 5.2 Quicksort 176 Exercises 5.2 181 5.3 Binary Tree Traversals and Related Properties 182 Exercises 5.3 185 5.4 Multiplication of Large Integers and Strassen’s Matrix Multiplication 186 Multiplication of Large Integers 187 Strassen’s Matrix Multiplication 189 Exercises 5.4 191 5.5 The Closest-Pair and Convex-Hull Problems by Divide-and-Conquer 192 The Closest-Pair Problem 192 Convex-Hull Problem 195 Exercises 5.5 197 Summary 198
6 Transform-and-Conquer 201 6.1 Presorting 202 Exercises 6.1 205 6.2 Gaussian Elimination 208 LU Decomposition 212 Computing a Matrix Inverse 214 Computing a Determinant 215 Exercises 6.2 216 6.3 Balanced Search Trees 218 AVL Trees 218 2-3 Trees 223 Exercises 6.3 225 6.4 Heaps and Heapsort 226 Notion of the Heap 227 Heapsort 231 Exercises 6.4 233 6.5 Horner’s Rule and Binary Exponentiation 234 Horner’s Rule 234 Binary Exponentiation 236 Exercises 6.5 239 6.6 Problem Reduction 240 Computing the Least Common Multiple 241 Counting Paths in a Graph 242 Reduction of Optimization Problems 243 Linear Programming 244 Reduction to Graph Problems 246 Exercises 6.6 248 Summary 250
7 Space and Time Trade-Offs 253 7.1 Sorting by Counting 254 Exercises 7.1 257 7.2 Input Enhancement in String Matching 258 Horspool’s Algorithm 259 Boyer-Moore Algorithm 263 Exercises 7.2 267 7.3 Hashing 269 Open Hashing (Separate Chaining) 270 Closed Hashing (Open Addressing) 272 Exercises 7.3 274 7.4 B-Trees 276 Exercises 7.4 279 Summary 280
8 Dynamic Programming 283 8.1 Three Basic Examples 285 Exercises 8.1 290 8.2 The Knapsack Problem and Memory Functions 292 Memory Functions 294 Exercises 8.2 296 8.3 Optimal Binary Search Trees 297 Exercises 8.3 303 8.4 Warshall’s and Floyd’s Algorithms 304 Warshall’s Algorithm 304 Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem 308 Exercises 8.4 311 Summary 312
10 Iterative Improvement 345 10.1 The Simplex Method 346 Geometric Interpretation of Linear Programming 347 An Outline of the Simplex Method 351 Further Notes on the Simplex Method 357 Exercises 10.1 359 10.2 The Maximum-Flow Problem 361 Exercises 10.2 371 10.3 Maximum Matching in Bipartite Graphs 372 Exercises 10.3 378 10.4 The Stable Marriage Problem 380 Exercises 10.4 383 Summary 384
11 Limitations of Algorithm Power 387 11.1 Lower-Bound Arguments 388 Trivial Lower Bounds 389 Information-Theoretic Arguments 390 Adversary Arguments 390 Problem Reduction 391 Exercises 11.1 393 11.2 Decision Trees 394 Decision Trees for Sorting 395 Decision Trees for Searching a Sorted Array 397 Exercises 11.2 399 11.3 P, NP, and NP-Complete Problems 401 P and NP Problems 402 NP-Complete Problems 406 Exercises 11.3 409 11.4 Challenges of Numerical Algorithms 412 Exercises 11.4 419 Summary 420
12 Coping with the Limitations of Algorithm Power 423 12.1 Backtracking 424 n-Queens Problem 425 Hamiltonian Circuit Problem 426 Subset-Sum Problem 427 General Remarks 428 Exercises 12.1 430 12.2 Branch-and-Bound 432 Assignment Problem 433 Knapsack Problem 436 Traveling Salesman Problem 438 Exercises 12.2 440 12.3 Approximation Algorithms for NP-Hard Problems 441 Approximation Algorithms for the Traveling Salesman Problem 443 Approximation Algorithms for the Knapsack Problem 453 Exercises 12.3 457 12.4 Algorithms for Solving Nonlinear Equations 459 Bisection Method 460 Method of False Position 464 Newton’s Method 464 Exercises 12.4 467 Summary 468 Epilogue 471
APPENDIX A Useful Formulas for the Analysis of Algorithms 475 Properties of Logarithms 475 Combinatorics 475 Important Summation Formulas 476 Sum Manipulation Rules 476 Approximation of a Sum by a Definite Integral 477 Floor and Ceiling Formulas 477 Miscellaneous 477
APPENDIX B Short Tutorial on Recurrence Relations 479 Sequences and Recurrence Relations 479 Methods for Solving Recurrence Relations 480 Common Recurrence Types in Algorithm Analysis 485 References 493 Hints to Exercises 503 Index 547