Introduction to the Design and Analysis of Algorithms

Name: Introduction to the Design and Analysis of Algorithms
Availability: InStock
ISBN: 9780132316811

ISBN-10: 0132316811

ISBN-13: 9780132316811

Edition: 3rd 2012 (Revised)

Authors: Anany Levitin

List price: $193.32

This item qualifies for FREE shipping.

30 day, 100% satisfaction guarantee!

Sell

Get cash fast!

Semester Rental: $63.47 Due date: 8/14/2024

Rental notice: supplementary materials (access codes, CDs, etc.) are not guaranteed with rental orders.

Buy used: $109.11

Marketplace

4 new & used from $27.89

what's this?

Rush Rewards U
Members Receive:

You have reached 400 XP and carrot coins. That is the daily max!

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.

Book details

List price: $193.32
Edition: 3rd
Copyright year: 2012
Publisher: Pearson Education
Publication date: 9/29/2011
Binding: Paperback
Pages: 600
Size: 7.30" wide x 9.00" long x 1.17" tall
Weight: 2.090
Language: English

Anany Levitin is a professor of Computing Sciences at Villanova University. He is the author of a popular textbook on design and analysis of algorithms, which has been translated into Chinese, Greek, Korean, and Russian. He has also published papers on mathematical optimization theory, software engineering, data management, algorithm design techniques, and computer science education. Maria Levitin is an independent consultant specializing in web applications and data compression. She has previously worked for several leading software companies.



New to the Third Edition


Preface



Introduction



What Is an Algorithm?


Exercises 1.1



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



Important Problem Types


Sorting


Searching


String Processing


Graph Problems


Combinatorial Problems


Geometric Problems


Numerical Problems


Exercises 1.3



Fundamental Data Structures


Linear Data Structures


Graphs


Trees


Sets and Dictionaries


Exercises 1.4


Summary



Fundamentals of the Analysis of Algorithm Efficiency



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



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



Mathematical Analysis of Nonrecursive Algorithms


Exercises 2.3



Mathematical Analysis of Recursive Algorithms


Exercises 2.4



Example: Computing the nth Fibonacci Number


Exercises 2.5



Empirical Analysis of Algorithms


Exercises 2.6



Algorithm Visualization


Summary



Brute Force and Exhaustive Search



Selection Sort and Bubble Sort


Selection Sort


Bubble Sort


Exercises 3.1



Sequential Search and Brute-Force String Matching


Sequential Search


Brute-Force String Matching


Exercises 3.2



Closest-Pair and Convex-Hull Problems by Brute Force


Closest-Pair Problem


Convex-Hull Problem


Exercises 3.3



Exhaustive Search


Traveling Salesman Problem


Knapsack Problem


Assignment Problem


Exercises 3.4



Depth-First Search and Breadth-First Search


Depth-First Search


Breadth-First Search


Exercises 3.5


Summary



Decrease-and-Conquer



Insertion Sort


Exercises 4.1



Topological Sorting


Exercises 4.2



Algorithms for Generating Combinatorial Objects


Generating Permutations


Generating Subsets


Exercises 4.3



Decrease-by-a-Constant-Factor Algorithms


Binary Search


Fake-Coin Problem


Russian Peasant Multiplication


Josephus Problem


Exercises 4.4



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



Divide-and-Conquer



Mergesort


Exercises 5.1



Quicksort


Exercises 5.2



Binary Tree Traversals and Related Properties


Exercises 5.3



Multiplication of Large Integers and Strassen's Matrix Multiplication


Multiplication of Large Integers


Strassen's Matrix Multiplication


Exercises 5.4



The Closest-Pair and Convex-Hull Problems by Divide-and-Conquer


The Closest-Pair Problem


Convex-Hull Problem


Exercises 5.5


Summary



Transform-and-Conquer



Presorting


Exercises 6.1



Gaussian Elimination


LU Decomposition


Computing a Matrix Inverse


Computing a Determinant


Exercises 6.2



Balanced Search Trees


AVL Trees



Trees


Exercises 6.3



Heaps and Heapsort


Notion of the Heap


Heapsort


Exercises 6.4



Horner's Rule and Binary Exponentiation


Horner's Rule


Binary Exponentiation


Exercises 6.5



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



Space and Time Trade-Offs



Sorting by Counting


Exercises 7.1



Input Enhancement in String Matching


Horspool's Algorithm


Boyer-Moore Algorithm


Exercises 7.2



Hashing


Open Hashing (Separate Chaining)


Closed Hashing (Open Addressing)


Exercises 7.3



B-Trees


Exercises 7.4


Summary



Dynamic Programming



Three Basic Examples


Exercises 8.1



The Knapsack Problem and Memory Functions


Memory Functions


Exercises 8.2



Optimal Binary Search Trees


Exercises 8.3



Warshall's and Floyd's Algorithms


Warshall's Algorithm


Floyd's Algorithm for the All-Pairs Shortest-Paths Problem


Exercises 8.4


Summary



Greedy Technique



Prim's Algorithm


Exercises 9.1



Kruskal's Algorithm


Disjoint Subsets and Union-Find Algorithms


Exercises 9.2



Dijkstra's Algorithm


Exercises 9.3



Huffman Trees and Codes


Exercises 9.4


Summary



Iterative Improvement



The Simplex Method


Geometric Interpretation of Linear Programming


An Outline of the Simplex Method


Further Notes on the Simplex Method


Exercises 10.1



The Maximum-Flow Problem


Exercises 10.2



Maximum Matching in Bipartite Graphs


Exercises 10.3



The Stable Marriage Problem


Exercises 10.4


Summary



Limitations of Algorithm Power



Lower-Bound Arguments


Trivial Lower Bounds


Information-Theoretic Arguments


Adversary Arguments


Problem Reduction


Exercises 11.1



Decision Trees


Decision Trees for Sorting


Decision Trees for Searching a Sorted Array


Exercises 11.2



P, NP, and NP-Complete Problems


P and NP Problems


NP-Complete Problems


Exercises 11.3



Challenges of Numerical Algorithms


Exercises 11.4


Summary



Coping with the Limitations of Algorithm Power



Backtracking


n-Queens Problem


Hamiltonian Circuit Problem


Subset-Sum Problem


General Remarks


Exercises 12.1



Branch-and-Bound


Assignment Problem


Knapsack Problem


Traveling Salesman Problem


Exercises 12.2



Approximation Algorithms for NP-Hard Problems


Approximation Algorithms for the Traveling Salesman Problem


Approximation Algorithms for the Knapsack Problem


Exercises 12.3



Algorithms for Solving Nonlinear Equations


Bisection Method


Method of False Position


Newton's Method


Exercises 12.4


Summary


Epilogue





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





Short Tutorial on Recurrence Relations


Sequences and Recurrence Relations