# Introduction to the Design and Analysis of Algorithms,3rd edition

• Anany Levitin Villanova University
Products list

### eTextbook features

• Search, highlight, and notes
• Create flashcards
Products list

### Details

• A print text

This product is expected to ship within 3-6 business days for US and 5-10 business days for Canadian customers.

Introduction to the Design and Analysis of Algorithms presents the subject in a coherent and innovative manner. The text examines new algorithm design techniques and methods for analysis and includes puzzles and other learner-focused features to help you strengthen your algorithmic problem-solving skills.

• New to the Third Edition
• Preface
1. Introduction
• 1.1 What Is an Algorithm?
• Exercises 1.1
• 1.2 Fundamentals of Algorithmic Problem Solving
• Understanding the Problem
• Ascertaining the Capabilities of the Computational Device
• Choosing between Exact and Approximate Problem Solving
• Algorithm Design Techniques
• Designing an Algorithm and Data Structures
• Methods of Specifying an Algorithm
• Proving an Algorithmâ€™s Correctness
• Analyzing an Algorithm
• Coding an Algorithm
• Exercises 1.2
• 1.3 Important Problem Types
• Sorting
• Searching
• String Processing
• Graph Problems
• Combinatorial Problems
• Geometric Problems
• Numerical Problems
• Exercises 1.3
• 1.4 Fundamental Data Structures
• Linear Data Structures
• Graphs
• Trees
• Sets and Dictionaries
• Exercises 1.4
• Summary
2. Fundamentals of the Analysis of Algorithm Efficiency
• 2.1 The Analysis Framework
• Measuring an Inputâ€™s Size
• Units for Measuring Running Time
• Orders of Growth
• Worst-Case, Best-Case, and Average-Case Efficiencies
• Recapitulation of the Analysis Framework
• Exercises 2.1
• 2.2 Asymptotic Notations and Basic Efficiency Classes
• Informal Introduction
• O-notation
• -notation
• -notation
• Useful Property Involving the Asymptotic Notations
• Using Limits for Comparing Orders of Growth
• Basic Efficiency Classes
• Exercises 2.2
• 2.3 Mathematical Analysis of Nonrecursive Algorithms
• Exercises 2.3
• 2.4 Mathematical Analysis of Recursive Algorithms
• Exercises 2.4
• 2.5 Example: Computing the nth Fibonacci Number
• Exercises 2.5
• 2.6 Empirical Analysis of Algorithms
• Exercises 2.6
• 2.7 Algorithm Visualization
• Summary
3. Brute Force and Exhaustive Search
• 3.1 Selection Sort and Bubble Sort
• Selection Sort
• Bubble Sort
• Exercises 3.1
• 3.2 Sequential Search and Brute-Force String Matching
• Sequential Search
• Brute-Force String Matching
• Exercises 3.2
• 3.3 Closest-Pair and Convex-Hull Problems by Brute Force
• Closest-Pair Problem
• Convex-Hull Problem
• Exercises 3.3
• 3.4 Exhaustive Search
• Traveling Salesman Problem
• Knapsack Problem
• Assignment Problem
• Exercises 3.4
• 3.5 Depth-First Search and Breadth-First Search
• Depth-First Search
• Exercises 3.5
• Summary
4. Decrease-and-Conquer
• 4.1 Insertion Sort
• Exercises 4.1
• 4.2 Topological Sorting
• Exercises 4.2
• 4.3 Algorithms for Generating Combinatorial Objects
• Generating Permutations
• Generating Subsets
• Exercises 4.3
• 4.4 Decrease-by-a-Constant-Factor Algorithms
• Binary Search
• Fake-Coin Problem
• Russian Peasant Multiplication
• Josephus Problem
• Exercises 4.4
• 4.5 Variable-Size-Decrease Algorithms
• Computing a Median and the Selection Problem
• Interpolation Search
• Searching and Insertion in a Binary Search Tree
• The Game of Nim
• Exercises 4.5
• Summary
5. Divide-and-Conquer
• 5.1 Mergesort
• Exercises 5.1
• 5.2 Quicksort
• Exercises 5.2
• 5.3 Binary Tree Traversals and Related Properties
• Exercises 5.3
• 5.4 Multiplication of Large Integers and Strassenâ€™s Matrix Multiplication
• Multiplication of Large Integers
• Strassenâ€™s Matrix Multiplication
• Exercises 5.4
• 5.5 The Closest-Pair and Convex-Hull Problems
• by Divide-and-Conquer
• The Closest-Pair Problem
• Convex-Hull Problem
• Exercises 5.5
• Summary
6. Transform-and-Conquer
• 6.1 Presorting
• Exercises 6.1
• 6.2 Gaussian Elimination
• LU Decomposition
• Computing a Matrix Inverse
• Computing a Determinant
• Exercises 6.2
• 6.3 Balanced Search Trees
• AVL Trees
• 2-3 Trees
• Exercises 6.3
• 6.4 Heaps and Heapsort
• Notion of the Heap
• Heapsort
• Exercises 6.4
• 6.5 Hornerâ€™s Rule and Binary Exponentiation
• Hornerâ€™s Rule
• Binary Exponentiation
• Exercises 6.5
• 6.6 Problem Reduction
• Computing the Least Common Multiple
• Counting Paths in a Graph
• Reduction of Optimization Problems
• Linear Programming
• Reduction to Graph Problems
• Exercises 6.6
• Summary
• 7.1 Sorting by Counting
• Exercises 7.1
• 7.2 Input Enhancement in String Matching
• Horspoolâ€™s Algorithm
• Boyer-Moore Algorithm
• Exercises 7.2
• 7.3 Hashing
• Open Hashing (Separate Chaining)
• Exercises 7.3
• 7.4 B-Trees
• Exercises 7.4
• Summary
8. Dynamic Programming
• 8.1 Three Basic Examples
• Exercises 8.1
• 8.2 The Knapsack Problem and Memory Functions
• Memory Functions
• Exercises 8.2
• 8.3 Optimal Binary Search Trees
• Exercises 8.3
• 8.4 Warshallâ€™s and Floydâ€™s Algorithms
• Warshallâ€™s Algorithm
• Floydâ€™s Algorithm for the All-Pairs Shortest-Paths Problem
• Exercises 8.4
• Summary
9. Greedy Technique
• 9.1 Primâ€™s Algorithm
• Exercises 9.1
• 9.2 Kruskalâ€™s Algorithm
• Disjoint Subsets and Union-Find Algorithms
• Exercises 9.2
• 9.3 Dijkstraâ€™s Algorithm
• Exercises 9.3
• 9.4 Huffman Trees and Codes
• Exercises 9.4
• Summary
10. Iterative Improvement
• 10.1 The Simplex Method
• Geometric Interpretation of Linear Programming
• An Outline of the Simplex Method
• Further Notes on the Simplex Method
• Exercises 10.1
• 10.2 The Maximum-Flow Problem
• Exercises 10.2
• 10.3 Maximum Matching in Bipartite Graphs
• Exercises 10.3
• 10.4 The Stable Marriage Problem
• Exercises 10.4
• Summary
11. Limitations of Algorithm Power
• 11.1 Lower-Bound Arguments
• Trivial Lower Bounds
• Information-Theoretic Arguments
• Problem Reduction
• Exercises 11.1
• 11.2 Decision Trees
• Decision Trees for Sorting
• Decision Trees for Searching a Sorted Array
• Exercises 11.2
• 11.3 P, NP, and NP-Complete Problems
• P and NP Problems
• NP-Complete Problems
• Exercises 11.3
• 11.4 Challenges of Numerical Algorithms
• Exercises 11.4
• Summary
12. Coping with the Limitations of Algorithm Power
• 12.1 Backtracking
• n-Queens Problem
• Hamiltonian Circuit Problem
• Subset-Sum Problem
• General Remarks
• Exercises 12.1
• 12.2 Branch-and-Bound
• Assignment Problem
• Knapsack Problem
• Traveling Salesman Problem
• Exercises 12.2
• 12.3 Approximation Algorithms for NP-Hard Problems
• Approximation Algorithms for the Traveling Salesman Problem
• Approximation Algorithms for the Knapsack Problem
• Exercises 12.3
• 12.4 Algorithms for Solving Nonlinear Equations
• Bisection Method
• Method of False Position
• Newtonâ€™s Method
• Exercises 12.4
• Summary
• Epilogue

### APPENDIX A

• Useful Formulas for the Analysis of Algorithms
• Properties of Logarithms
• Combinatorics
• Important Summation Formulas
• Sum Manipulation Rules
• Approximation of a Sum by a Definite Integral
• Floor and Ceiling Formulas
• Miscellaneous

### APPENDIX B

• Short Tutorial on Recurrence Relations
• Sequences and Recurrence Relations
• Methods for Solving Recurrence Relations
• Common Recurrence Types in Algorithm Analysis

#### Index

Need help? Get in touch