算法設(shè)計(jì)技巧與分析：英文版

Preface                  
 PART 1 Basic Concepts and Introduction to                  
 Algorithms                  
 Chapter 1 Basic Concepts in Algorithmic Analysis                  
 1.1 Introduction                  
 l.2 Historical BaCkground                  
 1.3 Binary Search                  
 1.3.1 Analysis of the binary search algorithm                  
 1.4 Merging Two Sorted Lists                  
 1.5 Selectinn Sort                  
 1.6 Insertion Sort                  
 1.7 Bottom-Up Merge Sorting                  
 1.7.1 Analysis of bottom-up merge sorting                  
 1.8 Time Complexity                  
 1.8.1 Order of growth                  
 1.8.2 The O-notation                  
 1.8.3 The fl-notation                  
 l.8.4 The e-notation                  
 1.8.5 MamPles                  
 1.8.6 Complekity classes and the o-notation                  
 1.9 Space Complexity                  
 1.10 Optimal Algorithms                  
                   
                   
 1.1l How to Bstimate the Running Time of an Algorithm                  
 1.l1.1 Couliting the number of forrations                  
 l.1l.2 Counting the frequency of basic operatha                  
 1.1l.3 Using recurrence relations                  
 1.l2 Worst case and average case analysis                  
 l.12.1 Wofst case analysis                  
 1.12.2 Average case analysis                  
 l.13 Amedised Analyais                  
 1.14 Input Sise and Problem Instance                  
 1.15 Exercises                  
 1.16 Bibiographic Notes                  
 Chapter 2 Mathematical Preliminaries                  
 2.1 Sots, Reations and Annctions                  
 2.1.1 sets                  
 2.1.2 ffelations                  
 2.1.2.l Equivalence relations                  
 2.1.3 Thnctions                  
 2.2 Proof Mehods                  
 2.2.1 Direct proof                  
 2.2.2 Indirect proof                  
 2.2.3 Proof by colltradiction                  
 2.2.4 Proof by cotillterexample                  
 2.2.5 Mathematical induction                  
 2.3 Logarithms                  
 2.4 Floor and Ceiling Tunctions                  
 2.5 Factorial and Binomial Coefficients                  
 2.5.1 Factorials                  
 2.5.2 Bintalal coefficients                  
 2.6 The Pigeonhole Principle                  
 2.7 Summations                  
 2.7.1 Approkimation of summations by integration                  
 2.8 Recurrence Relations                  
 2.8.1 Solution of linear homogeneous recurrences                  
 2.8.2 Solution of inhomogeneous recurrences                  
 2.8.3 Solation of divide-and-conquer recurrence                  
 2.8.3.1 Expanding the recurrence                  
 2.8.3.2 Sutistitution                  
 2.8.3.3 Change of variables                  
 2.9 Exercises                  
 Chapter 3 Data Structures                  
 3.1 Introdction                  
 3.2 Linked Lists                  
 3.2.1 Stacks ana queues                  
 3.3 Graphs                  
 3.3.1 Representation of graphs                  
 3.3.2 planar graphs                  
 3.4 Trees                  
 3.5 Rooted Trees                  
 3.5.1 Tree traversals                  
 3.6 Binary Trees                  
 3.6.l Some quantitative aspects of binary trees                  
 3.6.2 Binary search trees                  
 3.7 Exercises                  
 3.8 Blbliographic Notes                  
 Chapter 4 Heaps and the Disjoint Sets Data Structure                  
 4.l Iotroduction                  
 4.2 Heaps                  
 4.2.1 Operations on heaps                  
 4.2.2 Creating a heap                  
 4.2.3 Heapsort                  
 4.2.4 Min and max heaps                  
 4.3 Disjoint Sets Data Structures                  
 4.3.1 The union by rank heuristic                  
 4.3.2 Path compression                  
 4.3.3 The union-find algorithms                  
 4.3.4 Analysis of the uninn-find algorithms                  
 4.4 Exercises                  
 4.5 Bibliographic Notes                  
 PART 2 Techniques Based on Recursion                  
 Chapter 5 Induction                  
                   
                   
 5.1 Introduction                  
 5.2 Two Simple Examples                  
 5.2.1 Selection sort                  
 5.2.2 Insertion sort                  
 5.3 Tadix Sort                  
 5.4 Integer Exponentiation                  
 5.5 Evaluating Polynomials (Horner's Rule)                  
 5.6 Generating Permutations                  
 5.6.1 The first algorithm                  
 5.6.2 The second algorithm                  
 5.7 Finding the Majority Element                  
 5.8 Exercises                  
 5.9 Bibliographic Notes                  
 Chapter 6 Divide and Conquer                  
 6.1 Introduction                  
 6.2 Binary Search                  
 6.3 Mergesort                  
 6.3.1 How the algorithm works                  
 6.3.2 Analysis of the mergesort algorithm                  
 6.4 The Divide and Conquer Paradigm                  
 6.5 Selection: Finding the Median and the kth Smallest Element                  
 6.5.l Analysis of the selection algorithm                  
 6.6 Quicksort                  
 6.6.1 A partitinning algorithm.                  
 6.6.2 The sorting algorithm                  
 6.6.3 Analysis of the quicksort algorithm                  
 6.6.3.1 The worst case behavior                  
 6.6.3.2 The average case behavior                  
 6.6.4 Comparison of sorting algorithms                  
 6.7 Multiplication of Large Integers                  
 6.8 Matrin Multiplication                  
 6.8.1 The traditional algorithm                  
 6.8.2 Recursive version                  
 6.8.3 Strassen's algorithm                  
 6.8.4 Comparisons of the three algorithms                  
 6.9 The Closest Pair Prob1em                  
 6.9.1 Time complekity                  
 6.10 Exercises                  
 6.11 BibliograPhic Notes                  
 Chapter 7 Dynamic Programming                  
 7.1 Introduction                  
 7.2 The Longed Common Subsequence Problem                  
 7.3 Matris Chain Multiplication                  
 7.4 The Dynamic Programming Paradigm                  
 7.5 The All-Pairs Shortest Path Problem.                  
 7.6 The Knapsack Problem                  
 7.7 Exercises                  
 7.8 Bibliographic Notes                  
 PART 3 First-Cut Techniques                  
 Chapter 8 The Greedy Approach                  
 8.1 Introduction                  
 8.2 The Shortest Path Problem                  
 8.2.1 A linear time algorithm for dense graphs                  
 8.3 Minimum Cost Spanning nees (Kruskal's Algorithm)                  
 8.4 Minimum Cost Spanning nees (Prim's Algorithm)                  
 8.4.1 A linear time algorithm for dense graphs                  
 8.5 File Compression                  
 8.6 Exercises                  
 8.7 Bibliographic Notes                  
 Chapter 9 Graph Thaversal                  
 9.1 Introduction                  
 9.2 Depth-First Search                  
 9.2.1 Time'complexity of depth-first search                  
 9.3 Applications of Depth-First Search                  
 9.3.1 Graph acyclicity                  
 9.3.2 Topological sorting                  
 9.3.3 Finding articulation points in a graph                  
 9.3.4 Strongly connected components                  
 9.4 Breadth-First Search                  
 9.5 Applications of Breadth-First Sparch                  
                   
                   
 9.6 Exercises                  
 9.7 Bibliographic Notes                  
 PART 4 Complexity of Problems                  
 Chapter 10 NP-Complete Problems                  
 10.l Illtroduction                  
 10.2 The Class P                  
 10.3 The Class NP                  
 10.4 NP-Complete Problems                  
 10.4.1 The satisfiability problem                  
 10.4.2 Vertex cover, independent set and clique problems                  
 10.4.3 More NP-complete Problems                  
 10.5 The Class co-NP                  
 10.6 The Class NPI                  
 10.7 The Relationips Between the Four Classes                  
 l0.8 Exercises                  
 10.9 Biblioaraphic Notes                  
 Chapter 11 Introduction to Computational Complexity                  
 11.1 Introduction                  
 11.2 Mode of Computation: Tlie Turing Machine                  
 11.3 k-tape Thring Machines and Time complexity                  
 11.4 Off-Line Turing Machines and Space Complexity                  
 11.5 Tape Compression and Linear Speed-Up                  
 11.6 Relationships Between complexity Classes                  
 l1.6.1 Space and for hieraxchy theorems.                  
 11.6.2 Padding arguments                  
 ll.7 Reductions                  
 11.8 Completeness                  
 1l.8.1 NLOGSPACE-complete problems                  
 11.8.2 PSPACE-complete problems                  
 11.8.3 P-complete problems                  
 11.8.4 Some conclusions of completeness                  
 11.9 The Polynomial Time Hierarchy                  
 11.10  Exercises                  
 11.11  Bibliographic Notes                  
 Chapter 12 Lower Bouuds                  
 12.1 Introduction                  
 12.2 Trivial Lower Bounds                  
 12.3 The Decision Tree Model                  
 12.3.1 The search problem                  
 12.3.2 The sorting problem                  
 l2.4 The Algebraic Decision Tree Model                  
 l2.4.1 The element uniqueness problem                  
 12.5 Linear Time bouctions                  
 12.5.1 The convex hull problem                  
 12.5.2 The closest pair problem                  
 12.5.3 The Euclidean minimum spanning tree problem                  
 12.6 Exercises                  
 12.7 Bibliographic Notes                  
 PART 5 Coping with Hardness                  
 Chapter 13 Backtracking                  
 13.1 Introduction                  
 13.2 The 3-Coloring Problem                  
 13.3 The 8-Queens Problem                  
 13.4 The General Backtracking Method                  
 13.5 Branch and Bound                  
 13.6 Exercises                  
 13.7 Bib1iographic notes                  
 Chapter 14 Randomized Algorithms                  
 14.l Introduction                  
 14.2 Las Vegas and Moote Carlo Algorithms                  
 14.3 Randomised Quicksort                  
 l4.4 Randomized Selection                  
 l4.5 Testing String Equality                  
 14.6 Pattern Matching                  
 14.7 Random Sampling                  
 l4.8 Primality Testing                  
 14.9 Exercises                  
 14.10  Bibliographic Notes                  
                   
                   
 Chapter 15 Approximation Algorithms                  
 15.1 Introduction                  
 15.2 Basic Definitions                  
 l5.3 Difference Bounds                  
 15.3.1 Planar graph coloring                  
 15.3.2 Hardness result: the knapsack problem                  
 15.4 Relative Performance Bounds                  
 15.4.1 The bin packing problem                  
 15.4.2 The Euclidean traveling salesman problem                  
 l5.4.3 The vertex cover problem                  
 15.4.4 Hardness resu1t: the traveling sa1esman problem                  
 15.5 Polynomial Approximation Schemes                  
 15.5.1 The knapsack problem                  
 15.6 Fully Po1ynomial Approximation Schemes                  
 15.6.1 The subset-sum problem                  
 15.7 Exercises                  
 15.8 BibliograPhic NOtes                  
 PART 6 Iterative Improvement for Domain-Specific                  
 Problems                  
 Chapter 16 Network Flow                  
 16.1 Introduction                  
 16.2 Pre1iminaries                  
 16.3 The Ford-Fulkerson Method                  
 16.4 Mtalmum Capacity Augmelltation                  
 16.5 Shortest Path Augmentation                  
 16.6 Dinic's Algorithm                  
 16.7 The MPM Algorithm                  
 16.8 Exercises                  
 16.9 Bibliographic Notes                  
 Chapter 17 Matching                  
 17.1 Introduction                  
 l7.2 Preliminaries                  
 17.3 Tbe Network Flow Method                  
 17.4 The Hungarian Tree Method for Bipartite Graphs                  
 17.5 Maximum Matching in General Graphs                  
 17.6 An O(n) Algorithm for Bipwtite Graphs                  
 17.7 Exercises                  
 17.8 Bibllogranfor Notes                  
 PART 7 Techniques in Computational Geometry                  
 Chapter 18 Geometric Sweeping                  
 18.1 Introduction                  
 18.2 Geometric Preliminaries                  
 l8.3 Computing the Intersections of Line Segments                  
 18.4 The Convex Hull Problem                  
 18.5 Computing the Diameter of a Set of Points                  
 18.6 Exercises                  
 18.7 Bib1iographic Notes                  
 Chapter 19 Voronoi Diagrams                  
 l9.1 Introduction                  
 19.2 Nearest-Point Voronoi Diagram                  
 19.2.1 Delaunay triangulation                  
 19.2.2 Construction of the Voronoi diagram                  
 l9.3 Applications of the Voronoi Diagram                  
 19.3.1 Computing the convex hull                  
 19.3.2 All nearest neighbors                  
 19.3.3 The Euclidean minimum spanning tree                  
 19.4 Farthed-Point Voronoi Diagram                  
 19.4.1 Construction of the farthest-point Voronoi diagram                  
 19.5 Applications of the Farthest-Point Voronoi Diagram                  
 19.5.1 All farthest neighbors                  
 19.5.2 Smallest enclosing circle                  
 19.6 Exercises                  
 l9.7 Bibliographic Notes                  
 Bibliography                  
 Index