Preface
List of Figures
Chapter 1 INTRODUCTION
Chapter 2 THE COMPLEXITY OF ALGORITHMS AND THE LOWER BOUNDS OF PROBLEMS
2-1 The time complexity of an algorithm
2-2 The best-, average- and worst-case analysis of algorithms
2-3 The lower bound of a problem
2-4 The worst-case lower bound of sorting
2-5 Heap sort: A sorting algorithm which is optimal in worst cases
2-6 The average-case lower bound of sorting
2-7 Improving a lower bound through oracles
2-8 Finding the lower bound by problem transformation
2-9 Notes and references
2-10 Further reading materials
Exercises
Chapter 3 THE GREEDY METHOD
3-1 Kruskal's method to find a minimum spanning tree
3-2 Prim's method to find a minimum spanning tree
3-3 The single-source shortest path problem
3-4 The 2-way merge problem
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
鄂公网安备 42010302001612号 