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

  • Anany Levitin

Choose the option that's right for you

$9.99 / mo

4-month term, pay monthly or pay $39.96

Enjoy these features

  • Up to 2 devices
  • Discounted tutor access
  • Exclusive offers

$14.99 / mo

4-month term, pay monthly or pay $59.96

Enjoy these features

  • Up to 2 devices
  • Discounted tutor access
  • Exclusive offers

Learn more, spend less

  • Learn anytime, anywhere

    Get the app to access your eTextbook whenever you need it

  • Make it your own

    Your notes. Your highlights. Your eTextbook

  • Find it fast

    Quickly navigate your eTextbook with search

  • Stay organized

    Access all your eTextbooks in one place

  • Access all your eTextbooks in one place

    Keep learning with auto-renew

Overview

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.

Published by Pearson (July 14th 2021) - Copyright © 2012

ISBN-13: 9780137541133

Subject: General Engineering

Category: Engineering Math

Table of contents

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

Your questions answered

Introducing Pearson+. Reimagined learning, designed for you. Choose from one eTextbook or over 1,500 eTextbooks and study tools, all in one place, for one low monthly subscription. A new way to buy books that fits your budget. Make the most of your study time with offline access, enhanced search, notes and flashcards — to get organized, get the work done quicker and get results. Plus, with the app, put textbooks in your pocket and learn wherever. It's time to upgrade the textbook and simplify learning, so you can have time to live too.

Pearson eTextbook is an easy-to-use digital textbook available from Pearson+. Make it your own by adding notes and highlights. Download the Pearson+ mobile app to learn on the go, even offline. Listen on the go with our new audiobook feature, available for most titles.

When you choose a plan, you're signing up for a 4-month 'term'. You can opt to make a one-time payment for the initial 4-month term or pay monthly. If you opt for monthly payments, we will charge your payment method each month until your 4-month term has ended. You can turn on auto-renew in My account at any time to continue your subscription before your 4-month term has ended.

When you purchase a Pearson+ subscription, it will last 4 months. Before your initial 4-month term ends, you can extend your subscription by turning auto-renew on in My account.

If you turn auto-renew on, we’ll automatically renew your subscription and charge you every month until you turn off auto-renew. If you made a one-time payment for your initial 4-month term, you’ll now pay monthly.

To avoid the next payment charge, make sure you turn auto renewal off 1 day before the auto renewal date. You can subscribe again after auto-renew has been turned off by purchasing another Pearson+ subscription. We use your credit card to renew your subscription automatically. To make sure your learning is uninterrupted, please check your card details before your first monthly payment.

With a Multi Pearson+ subscription plan, you can download up to 10 titles on the Pearson+ app from My list on each of your authorized devices every month.

When you're using your Multi Pearson+ subscription plan in a browser, you can select and read from as many titles as you like.