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
鄂公網(wǎng)安備 42010302001612號(hào) 