About the Book
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 truly
innovative manner. Written in a student-friendly style, the book encourages
broad problem-solving skills while thoroughly covering the material required
in an introductory algorithms course. The author emphasizes conceptual
understanding before the introduction of the formal treatment of each technique.
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 solution
manual.
Features
-
Covers both design and analysis frameworks.
-
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 solutions for instructors.
-
Includes material suggested by ACM Curriculum
2001.
Related
Books
Algorithms/Advanced Data
Structures - Programming Courses (Algorithms/Advanced
Data Structures)
Table of Contents
Preface.
1. Introduction.
The notion of algorithm.
Fundamentals of algorithmic problem
solving.
Important problem types.
Fundamental data structures.
2. Fundamentals of the Analysis
of Algorithm Efficiency.
Analysis framework.
Asymptotic notations and standard
efficiency classes.
Mathematical analysis of nonrecursive
algorithms.
Mathematical analysis of recursive
algorithms.
Example: Fibonacci numbers.
Empirical analysis of algorithms.
Algorithm visualization.
3. Brute Force.
Selection sort and bubble sort.
Sequential search and brute-force
string matching.
The closest-pair and convex-hull problems
by brute force.
Exhaustive search.
4. Divide-and-Conquer.
Mergesort.
Quicksort.
Binary search.
Binary tree traversals and related
properties.
Multiplication of large integers and
Strassen's matrix multiplication.
Closest-pair and convex-hull problems
by divide-and-conquer.
5. Decrease-and-Conquer.
Insertion sort.
Depth-first search and breadth-first
search.
Topological sorting.
Algorithms for generating combinatorial
objects.
Decrease-by-a-constant-factor algorithms.
Variable-size-decrease algorithms.
6. Transform-and-conquer.
Presorting.
Gaussian elimination.
Balanced search trees.
Heaps and heapsort.
Horner's rule and binary exponentiation.
Problem reduction.
7. Space and Time Tradeoffs.
Sorting by counting.
Horspool's and Boyer-Moore algorithms
for string matching.
Hashing.
B-trees.
8. Dynamic Programming.
Computing a binomial coefficient.
Shortest-path problems.
Warshall's and Floyd's algorithms.
Optimal binary search trees.
The knapsack problem and memory functions.
9. Greedy Technique.
Prim's algorithm.
Kruskal's algorithm.
Dijkstra's algorithm.
Huffman trees.
10. Limitations of Algorithm Power.
Lower-bound arguments.
Decision trees.
P, NP, and NP-complete problems.
Challenges of numerical algorithms.
11. Coping with the Limitations
of Algorithm Power.
Backtracking.
Branch-and-bound.
Approximation algorithms for NP-hard
problems.
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. |
