Always Learning

Introduction to the Design and Analysis of Algorithms, 2/E
Anany Levitin, Villanova University

ISBN-10: 0321358287
ISBN-13:  9780321358288

Publisher:  Addison-Wesley
Copyright:  2007
Format:  Paper; 592 pp
Published:  02/14/2006


Print this content

In this section:


Description

Based on a

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.

 

 


Features

  • 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
  • New chapter! Iterative improvement algorithms: the simplex method, maximum network flows, maximum matching in bipartite graphs, and the stable marriage problem
  • New! Revised section on approximation algorithms for TSP
  • New! Over sixty new exercises and engaging puzzles

 


New To This Edition

  • New chapter! Iterative improvement algorithms: the simplex method, maximum network flows, maximum matching in bipartite graphs, and the stable marriage problem
  • New! Revised section on approximation algorithms for TSP
  • New! Over sixty new exercises and engaging puzzles

 


Table of Contents

Contents

 

Preface

1Introduction

1.1 What is an Algorithm?

1.2 Fundamentals of Algorithmic Problem Solving

1.3 Important Problem Types

1.4 Fundamental Data Structures

 

2 Fundamentals of the Analysis of Algorithm Efficiency

2.1 Analysis Framework

2.2 Asymptotic Notations and Basic Efficiency Classes

2.3 Mathematical Analysis of Nonrecursive Algorithms

2.4 Mathematical Analysis of Recursive Algorithms

2.5 Example: Fibonacci Numbers

2.6 Empirical Analysis of Algorithms

2.7 Algorithm Visualization

 

3 Brute Force

3.1 Selection Sort and Bubble Sort

3.2 Sequential Search and Brute-Force String Matching

3.3 Closest-Pair and Convex-Hull Problems by Brute Force

3.4 Exhaustive Search

 

4 Divide-and-Conquer

4.1 Mergesort

4.2 Quicksort

4.3 Binary Search

4.4 Binary Tree Traversals and Related Properties

4.5 Multiplication of Large Integers and Strassen’s Matrix Multiplication

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

 

5 Decrease-and-Conquer

5.1 Insertion Sort

5.2 Depth-First Search and Breadth-First Search

5.3 Topological Sorting

5.4 Algorithms for Generating Combinatorial Objects

5.5 Decrease-by-a-Constant-Factor Algorithms

5.6 Variable-Size-Decrease Algorithms

 

6 Transform-and-Conquer

6.1 Presorting

6.2 Gaussian Elimination

6.3 Balanced Search Trees

6.4 Heaps and Heapsort

6.5 Horner’s Rule and Binary Exponentiation

6.6 Problem Reduction

 

7 Space and Time Tradeoffs

7.1 Sorting by Counting

7.2 Input Enhancement in String Matching

7.3 Hashing

7.4 B-Trees

 

8 Dynamic Programming

8.1 Computing a Binomial Coefficient

8.2 Warshall’s and Floyd’s Algorithms

8.3 Optimal Binary Search Trees

8.4 The Knapsack Problem and Memory Functions

 

9 Greedy Technique

9.1 Prim’s Algorithm

9.2 Kruskal’s Algorithm

9.3 Dijkstra’s Algorithm

9.4 Huffman Trees

 

10 Iterative Improvement

10.1 The Simplex Method

10.2 The Maximum-Flow Problem

10.3 Maximum Matching in Bipartite Graphs

10.4 The Stable Marriage Problem

 

11 Limitations of Algorithm Power

11.1 Lower-Bound Arguments

11.2 Decision Trees

11.3 P, NP, and NP-complete Problems

11.4 Challenges of Numerical Algorithms 4

 

12 Coping with the Limitations of Algorithm Power

12.1 Backtracking

12.2 Branch-and-Bound

12.3 Approximation Algorithms for NP-hard Problems

12.4 Algorithms for Solving Nonlinear Equations

 

Epilogue

 

APPENDIX A

Useful Formulas for the Analysis of Algorithms

 

APPENDIX B

Short Tutorial on Recurrence Relations

 

Bibliography

 

Hints to Exercises

 

Index


Next Edition(s)

  • Introduction to the Design and Analysis of Algorithms, 3/E
    Levitin
    ©2012  |  Addison-Wesley  |  Paper; 592 pp  |  Instock
    ISBN-10: 0132316811  |  ISBN-13: 9780132316811
    Brief Description  |  More Info



Back to top

Print this content

In this section:


Backcover Copy

Algorithms

 

Introduction to The Design & Analysis of Algorithms, 2nd Edition

Anany Levitin, Villanova University

 

Valued by students and trusted by instructors, Introduction to the Design and Analysis of Algorithms employs a comprehensive taxonomy of algorithm design techniques that is more powerful and intuitive than the traditional approach.

 

It provides a coherent and pedagogically sound framework for learning and teaching algorithms. An extensive, detailed solutions manual is available online for the benefit of students and instructors. Student learning is further supported by exercise hints and chapter summaries. Popular puzzles and games provide motivation for students, and rhetorical questioning serves as an effective learning device.

 

Ideal for a basic course in the design and analysis of algorithms, this Second Edition features 80 new puzzles and exercises, as well as:

• Separate sections on the analysis of nonrecursive and recursive algorithms

• Coverage of empirical analysis and algorithm visualization

• Revised section on approximation algorithms

• Brand-new chapter on iterative improvement algorithms covering the simplex method, network flows, maximum matching in bipartite graphs, and the stable marriage problem

Back to top

Print this content

In this section:

Online Code, 2/E
Levitin
©2007  |  Addison-Wesley  |  On-line Supplement  |  Live
ISBN-10: 032142199X  |  ISBN-13: 9780321421999

Show Downloadable Files
 | More Info

Online Figures, 2/E
Levitin
©2007  |  Addison-Wesley  |  On-line Supplement  |  Live
ISBN-10: 0321429389  |  ISBN-13: 9780321429384

Show Downloadable Files
 | More Info

Online PowerPoint Slides, 2/E
Levitin
©2007  |  Addison-Wesley  |  On-line Supplement  |  Live
ISBN-10: 0321429370  |  ISBN-13: 9780321429377

Show Downloadable Files
 | More Info

Online Solutions Manual, 2/E
Levitin
©2007  |  Addison-Wesley  |  On-line Supplement  |  Live
ISBN-10: 0321428102  |  ISBN-13: 9780321428103

Show Downloadable Files
 | More Info

Back to top


Websites and online courses

CS Support-Student Support Material
Addison-Wesley
©2008  |  Addison-Wesley  |  On-line Supplement  |  Live
ISBN-10: 0321446852  |  ISBN-13: 9780321446855
More Info

Log in to the Instructor Resource Center

Login name: 

  Password: 

Forgot login/password?  |  Need to redeem an access code?

        

Instructor Resource Center File Download

This work is protected by local and international copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning. Dissemination or sale of any part of this work (including on the World Wide Web) will destroy the integrity of the work and is not permitted. The work and materials from this site should never be made available to students except by instructors using the accompanying text in their classes. All recipients of this work are expected to abide by these restrictions and to honor the intended pedagogical purposes and the needs of other instructors who rely on these materials.

Cancel     I accept, proceed with download

Print this content

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students contact your Pearson Higher Education representative.

Back to top