Introduction to the Design and Analysis of Algorithms

by Levitin, Anany

• ISBN13: 9780321358288
• ISBN10: 0321358287
• Edition: 2nd
• Format: Paperback
• Copyright: 2007-01-01
• Publisher: Addison Wesley

Summary

Based on a new classification of algorithm design techniques and a clear delineation of analysis methods, Introduction to the Design and Analysis of Algorithms, 2e presents the subject in a truly innovative manner. Written in a reader-friendly style, the book encourages broad problem-solving skills while thoroughly covering the material required for introductory algorithms. The author emphasizes conceptual understanding before the introduction of the formal treatment of each technique. Popular puzzles are used to motivate readers'interest and strengthen their skills in algorithmic problem solving. Other enhancement features include chapter summaries, hints to the exercises, and a solution manual. For those interested in learning more about algorithms.

Table of Contents

Preface

Introduction

The notion of algorithm

Fundamentals of algorithmic problem solving

Important problem types

Fundamental data structures

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

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

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

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

Transform-and-conquer

Presorting

Gaussian elimination

Balanced search trees

Heaps and heapsort

Horner's rule and binary exponentiation

Problem reduction

Space and Time Tradeoffs

Sorting by counting

Horspool's and Boyer-Moore algorithms for string matching

Hashing

B-trees

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

Greedy Technique

Prim's algorithm

Kruskal's algorithm

Dijkstra's algorithm

Huffman trees

Limitations of Algorithm Power

Lower-bound arguments

Decision trees

P, NP, and NP-complete problems

Challenges of numerical algorithms

Coping with the Limitations of Algorithm Power

Backtracking

Branch-and-bound

Approximation algorithms for NP-hard problems

Algorithms for solving nonlinear equations

Epilogue

Useful Formulas for the Analysis of Algorithms

Short Tutorial on Recurrence Relations

Bibliography

Hints to Exercises

Index

Table of Contents provided by Publisher. All Rights Reserved.