Introduction to the design and analysis of algorithms / Anany Levitin.

By: Levitin, Anany [author]
Language: English Publisher: Boston : Addison Wesley, c2003Description: xxiv, 497 pages : illustrations ; 23 cmContent type: text Media type: unmediated Carrier type: volume ISBN: 0201743957; 9780201743951Subject(s): Computer algorithmsDDC classification: 005.1
Contents:
(Each chapter ends with a "Summary".)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.
Summary: This text introduces the reader to the design and analysis of algorithms. It teaches broad problem-solving skills alongside an introduction to algorithms.
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)
Item type Current location Home library Call number Status Date due Barcode Item holds
BOOK BOOK COLLEGE LIBRARY
COLLEGE LIBRARY
SUBJECT REFERENCE 		005.1 L579 2003 (Browse shelf) Available CITU-CL-29050
Total holds: 0

Includes index.

(Each chapter ends with a "Summary".)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.

This text introduces the reader to the design and analysis of algorithms. It teaches broad problem-solving skills alongside an introduction to algorithms.

There are no comments for this item.

to post a comment.