Text

Introduction to the design and analysis of algorithms

---

Contents:

1 Introduction
1.1 What is an algorithm
1.2 Fundamentals of algorithmic problem solving
1.3 Important problem types
1.4 Fundamentals data structures
Summary

2 Fundamentals of the analysis of algorithm efficiency
2.1 The analysis framework
2.2 Asymptotic notations and basic efficiency classes
2.3 Mathematical analysis of recursive algorithms
2.4 Mathematical analysis of nonrecursive algorithms
2.5 Example: computing the nth Fibonacci number
2.6 Empirical analysis algorithms
2.7 Algorithms visualization
Summary

3 Brute force and exhaustive search
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
3.5 Depth-first search and breadth-first search
Summary

4 Decrease- and-conquer
4.1 Insertion sort
4.2 Topological sorting
4.3 Algorithms for generating combinatorial objects
4.4 Decrease-by-a-constant-factor algorithms
4.5 Variable-size-decrease algorithms
Summary

5 Divide-and-conguer
5.1 Mergesort
5.2 Quicksort
5.3 Binary tree traversals related properties
5.4 Multiplication of largers and strassen’s matrix multiplication
5.5 The closest-pair and convex-hull problems by divide-and-conquer
Summary

6 Transform-and-conguer
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
Summary

7 Space and time trade-offs
7.1 Sorting by counting
7.2 Input enhancement in string matching
7.3 Hashing
7.4 B-trees
Summary

8 Dynamic programming
8.1 Three basic examples
8.2 The knapsack problem and memory functions
8.3 Optimal binary search trees
8.4 Warshall’s and floyd’s algorithms
Summary

9 Greedy technique
9.1 Prim’s algorithm
9.2 Kruskal’s algorithm
9.3 Dijkstra’s algorithm
9.4 Huffman trees and codes
Summary

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
Summary

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
Summary

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 equantions
Summary

Appendix A Useful formulas for the analysis of algorithms
Appendix B Short tutorial on recurrence relation
References
Hints to exercises
Index

---

Availability

Detail Information

Series Title

--

Call Number

518.1 LEV i

Publisher

New Jersey : Pearson., 2012

Collation

xxiv, 564 hal.; ilus.; 24 cm

Language

English

ISBN/ISSN

9780132316811

Classification

518.1

Content Type

-

Media Type

-

Carrier Type

-

Edition

Third Edition

Subject(s)

Algoritma
Algorithms

Specific Detail Info

--

Statement of Responsibility

Anany Levitin

Other version/related

File Attachment

Comments

---

You must be logged in to post a comment