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

  • Anany Levitin

Your access includes:

  • Search, highlight, notes, and more
  • Easily create flashcards
  • Use the app for access anywhere
  • 14-day refund guarantee

$10.99per month

Minimum 4-month term, pay monthly or pay $43.96 upfront

Learn more, spend less

  • Find it fast

    Quickly navigate your eTextbook with search

  • Stay organized

    Access all your eTextbooks in one place

  • Easily continue access

    Keep learning with auto-renew

Overview

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.

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

ISBN-13: 9780137541133

Subject: General Engineering

Category: Engineering Math

Overview

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

Pearson+ is your 1-stop shop with eTextbooks, study tools and exam prep features designed to help students get better grades in college. eTextbooks come with built-in tools that simplify studying, like flashcards, audiobook and search. Pearson+ also features Channels, which includes practice problems, study guides, Q&A with experts, video lessons that help you understand tricky topics and more—all in one place. Channels can be purchased separately or added on to your eTextbook at the time of purchase as part of the Study & Exam Prep Pack.

A Pearson eTextbook is an easy-to-use digital version of your book for class that includes upgraded study tools to help you learn how you learn best. Use enhanced search to find what you need within your eTextbook, highlight and make notes to mark important info, generate flashcards to test your knowledge, and use audio to listen to the text. Every feature is designed to help you learn more efficiently and get results. Plus, you can learn on the go with the Pearson+ app. Find this and more in your eTextbook, available in Pearson+.

The Study & Exam Prep Pack includes practice problems, study guides, Q&A with experts, Channels video lessons that help you understand tricky topics and more. It can be added on to your eTextbook or your MyLab and Mastering learning platform at the time of purchase.

Your eTextbook subscription gives you access for 4 months. You can 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 ends. You can turn on auto‑renew in My account at any time to continue your subscription before your 4‑month term ends.

When you purchase an eTextbook subscription, it will last 4 months. You can renew your subscription by selecting Extend subscription on the Manage subscription page in My account before your initial term ends.

If you extend your subscription, we'll automatically charge you every month. If you made a one‑time payment for your initial 4‑month term, you'll now pay monthly. To make sure your learning is uninterrupted, please check your card details.

To avoid the next payment charge, select Cancel subscription on the Manage subscription page in My account before the renewal date. You can subscribe again in the future by purchasing another eTextbook subscription.

Channels is a video platform with thousands of explanations, solutions and practice problems to help you do homework and prep for exams. Videos are personalized to your course, and tutors walk you through solutions. Plus, interactive AI‑powered summaries and a social community help you better understand lessons from class.

Channels is an additional tool to help you with your studies. This means you can use Channels even if your course uses a non‑Pearson textbook.

When you choose a Channels subscription, you're signing up for a 1‑month, 3‑month or 12‑month term and you make an upfront payment for your subscription. By default, these subscriptions auto‑renew at the frequency you select during checkout.

When you purchase a Channels subscription it will last 1 month, 3 months or 12 months, depending on the plan you chose. Your subscription will automatically renew at the end of your term unless you cancel it.

We use your credit card to renew your subscription automatically. To make sure your learning is uninterrupted, please check your card details.