|
Introduction to the Design & Analysis of Algorithms 2nd Edition
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
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
|
