Introduction to the Design and Analysis of Algorithms

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 EditionPreface Introduction 1.1 What Is an Algorithm? Exercises 1.11.2 Fundamentals of Algorithmic Problem Solving Understanding the ProblemAscertaining the Capabilities of the Computational DeviceChoosing between Exact and Approximate Problem SolvingAlgorithm Design TechniquesDesigning an Algorithm and Data StructuresMethods of Specifying an AlgorithmProving an Algorithm’s CorrectnessAnalyzing an AlgorithmCoding an AlgorithmExercises 1.21.3 Important Problem Types SortingSearchingString ProcessingGraph ProblemsCombinatorial ProblemsGeometric ProblemsNumerical ProblemsExercises 1.31.4 Fundamental Data Structures Linear Data StructuresGraphsTreesSets and DictionariesExercises 1.4 SummaryFundamentals of the Analysis of Algorithm Efficiency 2.1 The Analysis Framework Measuring an Input’s SizeUnits for Measuring Running TimeOrders of GrowthWorst-Case, Best-Case, and Average-Case EfficienciesRecapitulation of the Analysis FrameworkExercises 2.12.2 Asymptotic Notations and Basic Efficiency Classes Informal IntroductionO-notation-notation-notationUseful Property Involving the Asymptotic NotationsUsing Limits for Comparing Orders of GrowthBasic Efficiency ClassesExercises 2.22.3 Mathematical Analysis of Nonrecursive Algorithms Exercises 2.32.4 Mathematical Analysis of Recursive Algorithms Exercises 2.42.5 Example: Computing the nth Fibonacci Number Exercises 2.52.6 Empirical Analysis of Algorithms Exercises 2.62.7 Algorithm Visualization SummaryBrute Force and Exhaustive Search 3.1 Selection Sort and Bubble Sort Selection SortBubble SortExercises 3.13.2 Sequential Search and Brute-Force String Matching Sequential SearchBrute-Force String MatchingExercises 3.23.3 Closest-Pair and Convex-Hull Problems by Brute Force Closest-Pair ProblemConvex-Hull ProblemExercises 3.33.4 Exhaustive Search Traveling Salesman ProblemKnapsack ProblemAssignment ProblemExercises 3.43.5 Depth-First Search and Breadth-First Search Depth-First SearchBreadth-First SearchExercises 3.5 SummaryDecrease-and-Conquer 4.1 Insertion Sort Exercises 4.14.2 Topological Sorting Exercises 4.24.3 Algorithms for Generating Combinatorial Objects Generating PermutationsGenerating SubsetsExercises 4.34.4 Decrease-by-a-Constant-Factor Algorithms Binary SearchFake-Coin ProblemRussian Peasant MultiplicationJosephus ProblemExercises 4.44.5 Variable-Size-Decrease Algorithms Computing a Median and the Selection ProblemInterpolation SearchSearching and Insertion in a Binary Search TreeThe Game of NimExercises 4.5 SummaryDivide-and-Conquer 5.1 Mergesort Exercises 5.15.2 Quicksort Exercises 5.25.3 Binary Tree Traversals and Related Properties Exercises 5.35.4 Multiplication of Large Integers and Strassen’s Matrix Multiplication Multiplication of Large IntegersStrassen’s Matrix MultiplicationExercises 5.45.5 The Closest-Pair and Convex-Hull Problems by Divide-and-ConquerThe Closest-Pair ProblemConvex-Hull ProblemExercises 5.5 SummaryTransform-and-Conquer 6.1 Presorting Exercises 6.16.2 Gaussian Elimination LU DecompositionComputing a Matrix InverseComputing a DeterminantExercises 6.26.3 Balanced Search Trees AVL Trees2-3 TreesExercises 6.36.4 Heaps and Heapsort Notion of the HeapHeapsortExercises 6.46.5 Horner’s Rule and Binary Exponentiation Horner’s RuleBinary ExponentiationExercises 6.56.6 Problem Reduction Computing the Least Common MultipleCounting Paths in a GraphReduction of Optimization ProblemsLinear ProgrammingReduction to Graph ProblemsExercises 6.6 SummarySpace and Time Trade-Offs 7.1 Sorting by Counting Exercises 7.17.2 Input Enhancement in String Matching Horspool’s AlgorithmBoyer-Moore AlgorithmExercises 7.27.3 Hashing Open Hashing (Separate Chaining)Closed Hashing (Open Addressing)Exercises 7.37.4 B-Trees Exercises 7.4 SummaryDynamic Programming 8.1 Three Basic Examples Exercises 8.18.2 The Knapsack Problem and Memory Functions Memory FunctionsExercises 8.28.3 Optimal Binary Search Trees Exercises 8.38.4 Warshall’s and Floyd’s Algorithms Warshall’s AlgorithmFloyd’s Algorithm for the All-Pairs Shortest-Paths ProblemExercises 8.4 SummaryGreedy Technique 9.1 Prim’s Algorithm Exercises 9.19.2 Kruskal’s Algorithm Disjoint Subsets and Union-Find AlgorithmsExercises 9.29.3 Dijkstra’s Algorithm Exercises 9.39.4 Huffman Trees and Codes Exercises 9.4 SummaryIterative Improvement 10.1 The Simplex Method Geometric Interpretation of Linear ProgrammingAn Outline of the Simplex MethodFurther Notes on the Simplex MethodExercises 10.110.2 The Maximum-Flow Problem Exercises 10.210.3 Maximum Matching in Bipartite Graphs Exercises 10.310.4 The Stable Marriage Problem Exercises 10.4 SummaryLimitations of Algorithm Power 11.1 Lower-Bound Arguments Trivial Lower BoundsInformation-Theoretic ArgumentsAdversary ArgumentsProblem ReductionExercises 11.111.2 Decision Trees Decision Trees for SortingDecision Trees for Searching a Sorted ArrayExercises 11.211.3 P, NP, and NP-Complete Problems P and NP ProblemsNP-Complete ProblemsExercises 11.311.4 Challenges of Numerical Algorithms Exercises 11.4 SummaryCoping with the Limitations of Algorithm Power 12.1 Backtracking n-Queens ProblemHamiltonian Circuit ProblemSubset-Sum ProblemGeneral RemarksExercises 12.112.2 Branch-and-Bound Assignment ProblemKnapsack ProblemTraveling Salesman ProblemExercises 12.212.3 Approximation Algorithms for NP-Hard Problems Approximation Algorithms for the Traveling Salesman ProblemApproximation Algorithms for the Knapsack ProblemExercises 12.312.4 Algorithms for Solving Nonlinear Equations Bisection MethodMethod of False PositionNewton’s MethodExercises 12.4 SummaryEpilogueAPPENDIX A Useful Formulas for the Analysis of AlgorithmsProperties of LogarithmsCombinatoricsImportant Summation FormulasSum Manipulation RulesApproximation of a Sum by a Definite IntegralFloor and Ceiling FormulasMiscellaneousAPPENDIX B Short Tutorial on Recurrence RelationsSequences and Recurrence RelationsMethods for Solving Recurrence RelationsCommon Recurrence Types in Algorithm AnalysisReferences Hints to Exercises Index