算法设计与分析导论(英文影印版)

.3-5 the minimum cycle basis problem solved by the greedy algorithm
3-6 the 2-terminal one to any problem solved by the greedy method
3-7 the minimum cooperative guards problem for 1-spiral polygons solved by the greedy method
3-8 the experimental results
3-9 notes and references
3-10 further reading materials
exercises
chapter 4 the divide-and-conquer strategy
4-1 the 2-dimensional maxima finding problem
4-2 the closest pair problem
4-3 the convex hull problem
4-4 the voronoi diagrams constructed by the divide-and-conquer strategy
4-5 applications of the voronoi diagrams
4-6 the fast fourier transform
4-7 the experimental results
4-8 notes and references
4-9 further reading materials
exercises
chapter 5 tree searching strategies
5-1 breadth-first search
5-2 depth-first search
5-3 hill climbing
5-4 best-first search strategy
5-5 branch-and-bound strategy
5-6 a personnel assignment problem solved by the branch-and-bound strategy
5-7 the traveling salesperson optimization problem solved by the branch-and-bound strategy
5-8 the 0/1 knapsack problem solved by the branch-and-bound strategy
5-9 a job scheduling problem solved by the branch-and-bound approach
5-10 a* algorithm
5-11 a channel routing problem solved by a specialized a* algorithm
5-12 the linear block code decoding problem solved by the a* algorithm
5-13 the experimental results
5-14 notes and references
5-15 further reading materials
exercises
chapter 6 prune-and-search
6-1 the general method
6-2 the selection problem
6-3 linear programming with two variables
6-4 the 1-center problem
6-5 the experimental results
6-6 notes and references
6-7 further reading materials
exercises..
chapter 7 dynamic programming
7-1 the resource allocation problem
7-2 the longest common subsequence problem
7-3 the 2-sequence alignment problem
7-4 the rna maximum base pair matching problem
7-5 0/1 knapsack problem
7-6 the optimal binary tree problem
7-7 the weighted perfect domination problem on trees
7-8 the weighted single step graph edge searching problem on trees
7-9 the m-watchmen routes problem for 1-spiral polygons solved by the dynamic programming approach
7-10 the experimental results
7-11 notes and references
7-12 further reading materials
exercises
chapter 8 the theory of np-completeness
8-1 an informal discussion of the theory of np-completeness
8-2 the decision problems
8-3 the satisfiability problem
8-4 the np problems
8-5 cook's theorem
8-6 np-complete problems
8-7 examples of proving np-completeness
8-8 the 2-satisfiability problem
8-9 notes and references
8-10 further reading materials
exercises
chapter 9 approximation algorithms
9-1 an approximation algorithm for the node cover problem
9-2 an approximation algorithm for the euclidean traveling salesperson problem
9-3 an approximation algorithm for a special bottleneck traveling salesperson problem
9-4 an approximation algorithm for a special bottleneck weighted k-supplier problem
9-5 an approximation algorithm for the bin packing problem
9-6 an optimal approximation algorithm for the rectilinear m-center problem
9-7 an approximation algorithm for the multiple sequence alignment problem
9-8 a 2-approximation algorithm for the sorting by transposition problem
9-9 the polynomial time approximation scheme
9-10 a 2-approximation algorithm for the minimum routing cost spanning tree problem
9-11 a ptas for the minimum routing cost spanning tree problem
9-12 npo-completeness
9-13 notes and references
9-14 further reading materials
exercises
chapter 10 amortized analysis
10-1 an example of using the potential function
10-2 an amortized analysis of skew heaps
10-3 amortized analysis of avl-trees
10-4 amortized analysis of self-organizing sequential search heuristics
10-5 pairing heap and its amortized analysis
10-6 amortized analysis of a disjoint set union algorithm
10-7 amortized analysis of some disk scheduling algorithms
10-8 the experimental results
10-9 notes and references
10-10 further reading materials
exercises
chapter 11 randomized algorithms
11-1 a randomized algorithm to solve the closest pair problem
11-2 the average performance of the randomized closest pair problem
11-3 a randomized algorithm to test whether a number is a prime
11-4 a randomized algorithm for pattern matching
11-5 a randomized algorithm for interactive proofs
11-6 a randomized linear time algorithm for minimum spanning trees
11-7 notes and references
11-8 further reading materials
exercises
chapter 12 on-line algorithms
12-1 the on-line euclidean spanning tree problem solved by the greedy method
12-2 the on-line k-server problem and a greedy algorithm to solve this problem defined on planar trees
12-3 an on-line obstacle traversal algorithm based on the balance strategy
12-4 the on-line bipartite matching problem solved by the compensation strategy
12-5 the on-line m-machine problem solved by the moderation strategy
12-6 on-line algorithms for three computational geometry problems based on the elimination strategy
12-7 an on-line spanning tree algorithm based on the randomization strategy
12-8 notes and references
12-9 further reading materials
exercises
bibliography
author index
subject index...