Request full copy

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

Published by Unknown (September 29, 2011) © 2012

  • Anany Levitin Villanova University

eTextbook

per month

  • Anytime, anywhere learning with the Pearson+ app
  • Easy-to-use search, navigation and notebook
  • Simpler studying with flashcards
$165.32

  • Hardcover, paperback or looseleaf edition
  • Affordable rental option for select titles
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.
  • Employs an innovative and more comprehensive taxonomy of algorithm design techniques
  • Covers mathematical analysis of both nonrecursive and recursive algorithms, as well as empirical analysis and algorithm visualization
  • Discusses limitations of algorithms and ways to overcome them
  • Treats algorithms as problem-solving tools and develops algorithmic thinking by using puzzles and games
  • Contains over 600 exercises with hints for students and detailed solutions for instructors
  • Exercises and engaging puzzles
  • The most important change in this edition is the new order of the chapters on decrease-and-conquer and divide-and-conquer. There are several advantages in introducing decrease-and-conquer before divide-and-conquer:
    • Decrease-and-conquer is a simpler strategy than divide-and-conquer.
    • Decrease-and-conquer is applicable to more problems than divide-and-conquer.
    • The new order makes it possible to discuss insertion sort before mergesort and quicksort.
  • The idea of array partitioning is now introduced in conjunction with the selection problem. The author took advantage of an opportunity to do this via the one-directional scan employed by Lomuto’s algorithm, leaving the two-directional scan used by Hoare’s partitioning to a later discussion in conjunction with quicksort.
  • Binary search is now considered in the section devoted to decrease-by-aconstant-factor algorithms, where it belongs.
  • The second important change is restructuring of Chapter 8 on dynamic programming. Specifically:
    • The introductory section is completely new. It contains three basic examples that provide a much better introduction to this important technique than computing a binomial coefficient, the example used in the first two editions.
    • All the exercises for Section 8.1 are new as well; they include well-known applications not available in the previous editions.
    • The author also changed the order of the other sections in this chapter to get a smoother progression from the simpler applications to the more advanced ones.
  • More applications of the algorithms discussed are included.
  • The section on the graph-traversal algorithms is moved from the decrease-and-conquer chapter to the brute-force and exhaustive-search chapter.
  • The Gray code algorithm is added to the section dealing with algorithms for generating combinatorial objects.
  • The divide-and-conquer algorithm for the closest-pair problem is discussed in more detail.
  • Updates include the section on algorithm visualization, approximation algorithms for the traveling salesman problem, and the bibliography.
  • The author added about 70 new problems to the exercises. Some of them are algorithmic puzzles and questions asked during job interviews.

Table of Contents

  • 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
      • Breadth-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. Space and Time Trade-Offs
    • 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)
      • Closed Hashing (Open Addressing)
      • 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
      • Adversary 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

References

Hints to Exercises

Index

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.

Need help? Get in touch

Pearson+

All in one place. Pearson+ offers instant access to eTextbooks, videos and study tools in one intuitive interface. Students choose how they learn best with enhanced search, audio and flashcards. The Pearson+ app lets them read where life takes them, no wi-fi needed. Students can access Pearson+ through a subscription or their MyLab or Mastering course.

Video
Play
Privacy and cookies
By watching, you agree Pearson can share your viewership data for marketing and analytics for one year, revocable upon changing cookie preferences. Disabling cookies may affect video functionality. More info...

Video transcript (PDF | 16KB) 

Pearson eTextbook: What’s on the inside just might surprise you

They say you can’t judge a book by its cover. It’s the same with your students. Meet each one right where they are with an engaging, interactive, personalized learning experience that goes beyond the textbook to fit any schedule, any budget, and any lifestyle. 

Digital Learning NOW

Extend your professional development and meet your students where they are with free weekly Digital Learning NOW webinars. Attend live, watch on-demand, or listen at your leisure to expand your teaching strategies. Earn digital professional development badges for attending a live session.

Explore webinars