The design and analysis of computer algorithms / Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman.

Includes index.

Bibliography: p. [451]-462.

1 Models of Computation
1.1 Algorithms and their complexity
1.2 Random access machines
1.3 Computational complexity of RAM programs .
1.4 A stored program model
1.5 Abstractions of the RAM
1.6 A primitive model of computation: the Turing machine.
1.7 Relationship between the Turing machine and RAM models
1.8 Pidgin ALGOL—a high-level language
2 Design of EflBcient Algorithms
2.1 Data structures: lists, queues, and stacks
2.2 Set representations
2.3 Graphs
2.4 Trees
2.5 Recursion
2.6 Divide-and-conquer
2.7 Balancing
2.8 Dynamic programming.
2.9 Epilogue
3 Sorting and Order Statistics
3.1 The sorting problem
3.2 Radix sorting
3.3 Sorting by comparisons
3.4 Heapsort—an 0(n log n) comparison sort
3.5 Quicksort—an 0(n log n) expected time sort
3.6 Order statistics
3.7 Expected time for order statistics
4 Data Structures for Set Manipulation Problems
4.1 Fundamental operations on sets.
4.2 Hashing
4.3 Binary search
4.4 Binary search trees
4.5 Optimal binary search trees
4.6 A simple disjoint-set union algorithm
vil
4.7 Tree structures for the UNION-FIND problem
4.8 Applications and extensions of the UNION-FIND algorithm
4.9 Balanced tree schemes
4.10 Dictionaries and priority queues
4.11 Mergeable heaps
4.12 Concatenable queues .
4.13 Partitioning
4.14 Chapter summary
5 Algorithms on Graphs
S.l Minimum-cost spanning trees
5.1 Depth-first search
5.3 Biconnectivity
5.4 Depth-first search of a directed graph
5.5 Strong connectivity
5.6 Path-finding problems
5.7 A transitive closure algorithm
5.8 A shortest-path algorithm
5.9 Path problems and matrix multiplication
5.10 Single-source problems
5.11 Dominators in a directed acyclic graph: putting the concepts together.
6 Matrix Multiplication and Related Operations
6.1 Basics
6.2 Strassen's matrix-multiplication algorithm
6.3 Inversion of matrices
6.4 LUP decomposition of matrices
6.5 Applications of LUP decomposition
6.6 Boolean matrix multiplication
7 The Fast Fourier Transform and its Applications
7.1 The discrete Fourier transform and its inverse
7.2 The fast Fourier transform algorithm .
7.3 The FFT using bit operations
7.4 Products of polynomials
7.5 The Schonhage-Strassen integer-multiplication algorithm
8 Integer and Polynomial Arithmetic
8.1 The similarity between integers and polynomials
8.2 Integer multiplication and division
8.3 Polynomial multiplication and division
8.4 Modular arithmetic
8.5 Modular polynomial arithmetic and polynomial evaluation
8.6 Chinese remaindering
8.7 Chinese remaindering and interpolation of polynomials.
8.8 Greatest common divisors and Euclid's algorithm . . .
8.9 An asymptotically fast algorithm for polynomial CCD's
8.10 Integer CCD's
8.11 Chinese remaindering revisited
8.12 Sparse polynomials
9 Pattern-Matching Algorithms
9.1 Finite automata and regular expressions
9.2 Recognition of regular expression patterns,
9.3 Recognition of substrings
9.4 Two-way deterministic pushdown automata
9.5 Position trees and substring identifiers
10 NP-Complete Problems
10.1 Nondeterministic Turing machines
10.2 The classes ^ and .
10.3 Languages and problems
10.4 NP-completeness of the satisfiability problem .
10.5 Additional NP-complete problems
10.6 Polynomial-space-bounded problems.
11 Some Provably Intractable Problems
11.1 Complexity hierarchies
11.2 The space hierarchy for deterministic Turing machines.
11.3 A problem requiring exponential time and space
11.4 A nonelementary problem
12 Lower Bounds on Numbers of Arithmetic Operations
12.1 Fields
12.2 Straight-line code revisited
12.3 A matrix formulation of problems
12.4 A row-oriented lower bound on multiplications
12.5 A column-oriented lower bound on multiplications.
12.6 A row-and-column-oriented bound on multiplications
12.7 Preconditioning