算法设计技巧与分析 英文版PDF电子书下载

PART 1 Basic Concepts and Introduction to Algorithms 1

Chapter 1 Basic Concepts in Algorithmic Analysis 5

1.1 Introduction 5

1.2 Historical Background 6

1.3 Binary Search 8

1.3.1 Analysis of the binary search algorithm 10

1.4 Merging Two Sorted Lists 12

1.5 Selection Sort 14

1.6 Insertion Sort 15

1.7 Bottom-Up Merge Sorting 17

1.7.1 Analysis of bottom-up merge sorting 19

1.8 Time Complexity 20

1.8.1 Order of growth 21

1.8.2 The O-notation 25

1.8.3 The Ω-notation 26

1.8.4 The θ-notation 27

1.8.5 Examples 29

1.8.6 Complexity classes and the o-notation 31

1.9 Space Complexity 32

1.10 Optimal Algorithms 34

1.11 How to Estimate the Running Time of an Algorithm 35

1.11.1 Counting the number of iterations 35

1.11.2 Counting the frequency of basic operations 38

1.11.3 Using recurrence relations 41

1.12 Worst case and average case analysis 42

1.12.1 Worst case analysis 44

1.12.2 Average case analysis 46

1.13 Amortized Analysis 47

1.14 Input Size and Problem Instance 50

1.15 Exercises 52

1.16 Bibliographic Notes 59

Chapter 2 Mathematical Preliminaries 61

2.1 Sets, Relations and Functions 61

2.1.1 Sets 62

2.1.2 Relations 63

2.1.3 Functions 64

2.1.2.1 Equivalence relations 64

2.2 Proof Methods 65

2.2.1 Direct proof 65

2.2.2 Indirect proof 66

2.2.3 Proof by contradiction 66

2.2.4 Proof by counterexample 67

2.2.5 Mathematical induction 68

2.3 Logarithms 69

2.4 Floor and Ceiling Functions 70

2.5 Factorial and Binomial Coefficients 71

2.5.1 Factorials 71

2.5.2 Binomial coefficients 73

2.6 The Pigeonhole Principle 75

2.7 Summations 76

2.7.1 Approximation of summations by integration 78

2.8 Recurrence Relations 82

2.8.1 Solution of linear homogeneous recurrences 83

2.8.2 Solution of inhomogeneous recurrences 85

2.8.3.1 Expanding the recurrence 87

2.8.3 Solution of divide-and-conquer recurrences 87

2.8.3.2 Substitution 91

2.8.3.3 Change of variables 95

2.9 Exercises 98

Chapter 3 Data Structures 103

3.1 Introduction 103

3.2 Linked Lists 103

3.3 Graphs 104

3.2.1 Stacks and queues 104

3.3.1 Representation of graphs 106

3.3.2 Planar graphs 107

3.4 Trees 108

3.5 Rooted Trees 108

3.5.1 Tree traversals 109

3.6 Binary Trees 109

3.6.1 Some quantitative aspects of binary trees 111

3.7 Exercises 112

3.6.2 Binary search trees 112

3.8 Bibliographic Notes 114

Chapter 4 Heaps and the Disjoint Sets Data Structures 115

4.1 Introduction 115

4.2 Heaps 115

4.2.1 Operations on heaps 116

4.2.2 Creating a heap 120

4.2.3 Heapsort 124

4.3 Disjoint Sets Data Structures 125

4.2.4 Min and max heaps 125

4.3.1 The union by rank heuristic 127

4.3.2 Path compression 129

4.3.3 The union-find algorithms 130

4.3.4 Analysis of the union-find algorithms 132

4.4 Exercises 134

4.5 Bibliographic Notes 137

PART 2 Techniques Based on Recursion 139

5.1 Introduction 143

Chapter 5 Induction 143

5.2 Two Simple Examples 144

5.2.1 Selection sort 144

5.2.2 Insertion sort 145

5.3 Radix Sort 145

5.4 Integer Exponentiation 148

5.5 Evaluating Polynomials(Horner s Rule) 149

5.6 Generating Permutations 150

5.6.1 The first algorithm 150

5.6.2 The second algorithm 152

5.7 Finding the Majority Element 154

5.8 Exercises 155

5.9 Bibliographic Notes 158

Chapter 6 Divide and Conquer 161

6.1 Introduction 161

6.2 Binary Search 163

6.3 Mergesort 165

6.3.1 How the algorithm works 166

6.3.2 Analysis of the mergesort algorithm 167

6.4 The Divide and Conquer Paradigm 169

6.5 Selection: Finding the Median and the kth Smallest Element 172

6.5.1 Analysis of the selection algorithm 175

6.6 Quicksort 177

6.6.1 A partitioning algorithm 177

6.6.2 The sorting algorithm 179

6.6.3 Analysis of the quicksort algorithm 181

6.6.3.1 The worst case behavior 181

6.6.3.2 The average case behavior 184

6.6.4 Comparison of sorting algorithms 186

6.7 Multiplication of Large Integers 187

6.8 Matrix Multiplication 188

6.8.1 The traditional algorithm 188

6.8.2 Recursive version 188

6.8.3 Strassen s algorithm 190

6.8.4 Comparisons of the three algorithms 191

6.9 The Closest Pair Problem 192

6.9.1 Time complexity 194

6.10 Exercises 195

6.11 Bibliographic Notes 202

Chapter 7 Dynamic Programming 203

7.1 Introduction 203

7.2 The Longest Common Subsequence Problem 205

7.3 Matrix Chain Multiplication 208

7.4 The Dynamic Programming Paradigm 214

7.5 The All-Pairs Shortest Path Problem 215

7.6 The Knapsack Problem 217

7.7 Exercises 220

7.8 Bibliographic Notes 226

PART 3 First-Cut Techniques 227

Chapter 8 The Greedy Approach 231

8.1 Introduction 231

8.2 The Shortest Path Problem 232

8.2.1 A linear time algorithm for dense graphs 237

8.3 Minimum Cost Spanning Trees (Kruskal s Algorithm) 239

8.4 Minimum Cost Spanning Trees (Prim s Algorithm) 242

8.4.1 A linear time algorithm for dense graphs 246

8.5 File Compression 248

8.6 Exercises 251

8.7 Bibliographic Notes 255

Chapter 9 Graph Traversal 257

9.1 Introduction 257

9.2 Depth-First Search 257

9.2.1 Time-complexity of depth-first search 261

9.3.2 Topological sorting 262

9.3.1 Graph acyclicity 262

9.3 Applications of Depth-First Search 262

9.3.3 Finding articulation points in a graph 263

9.3.4 Strongly connected components 266

9.4 Breadth-First Search 267

9.5 Applications of Breadth-First Search 269

9.6 Exercises 270

9.7 Bibliographic Notes 273

PART 4 Complexity of Problems 275

10.1 Introduction 279

Chapter 10 NP-Complete Problems 279

10.2 The Class P 282

10.3 The Class NP 283

10.4 NP-Complete Problems 285

10.4.1 The satisfiability problem 285

10.4.2 Vertex cover,independent set and clique problems 288

10.4.3 More NP-complete Problems 291

10.5 The Class co-NP 292

10.6 The Class NPI 294

10.7 The Relationships Between the Four Classes 295

10.8 Exercises 296

10.9 Bibliographic Notes 298

Chapter 11 Introduction to Computational Complexity 299

11.1 Introduction 299

11.2 Model of Computation: The Turing Machine 299

11.3 k-tape Turing Machines and Time complexity 300

11.4 Off-Line Turing Machines and Space Complexity 303

11.5 Tape Compression and Linear Speed-Up 305

11.6 Relationships Between Complexity Classes 306

11.6.1 Space and time hierarchy theorems 309

11.6.2 Padding arguments 311

11.7 Reductions 313

11.8 Completeness 318

11.8.1 NLOGSPACE-complete problems 318

11.8.2 PSPACE-complete problems 319

11.8.3 P-complete problems 321

11.8.4 Some conclusions of completeness 323

11.9 The Polynomial Time Hierarchy 324

11.10 Exercises 328

11.11 Bibliographic Notes 332

Chapter 12 Lower Bounds 335

12.1 Introduction 335

12.2 Trivial Lower Bounds 335

12.3 The Decision Tree Model 336

12.3.1 The search problem 336

12.3.2 The sorting problem 337

12.4 The Algebraic Decision Tree Model 339

12.4.1 The element uniqueness problem 341

12.5 Linear Time Reductions 342

12.5.1 The convex hull problem 342

12.5.2 The closest pair problem 343

12.5.3 The Euclidean minimum spanning tree problem 344

12.6 Exercises 345

12.7 Bibliographic Notes 346

PART 5 Coping with Hardness 349

Chapter 13 Backtracking 353

13.1 Introduction 353

13.2 The 3-Coloring Problem 353

13.3 The 8-Queens Problem 357

13.4 The General Backtracking Method 360

13.5 Branch and Bound 362

13.6 Exercises 367

13.7 Bibliographic notes 369

14.1 Introduction 371

Chapter 14 Randomized Algorithms 371

14.2 Las Vegas and Monte Carlo Algorithms 372

14.3 Randomized Quicksort 373

14.4 Randomized Selection 374

14.5 Testing String Equality 377

14.6 Pattern Matching 379

14.7 Random Sampling 381

14.8 Primality Testing 384

14.9 Exercises 390

14.1O Bibliographic Notes 392

Chapter 15 Approximation Algorithms 393

15.1 Introduction 393

15.2 Basic Definitions 393

15.3 Difference Bounds 394

15.3.1 Planar graph coloring 395

15.3.2 Hardness result: the knapsack problem 395

15.4 Relative Performance Bounds 396

15.4.1 The bin packing problem 397

15.4.2 The Euclidean traveling salesman problem 399

15.4.3 The vertex cover problem 401

15.4.4 Hardness result:the traveling salesman problem 402

15.5 Polynomial Approximation Schemes 404

15.5.1 The knapsack problem 404

15.6 Fully Polynomial Approximation Schemes 407

15.6.1 The subset-sum problem 408

15.7 Exercises 410

15.8 Bibliographic Notes 413

PART 6 Iterative Improvement for Domain-Specific Problems 415

Chapter 16 Network Flow 419

16.1 Introduction 419

16.2 Preliminaries 419

16.3 The Ford-Fulkerson Method 423

16.4 Maximum Capacity Augmentation 424

16.5 Shortest Path Augmentation 426

16.6 Dinic s Algorithm 429

16.7 The MPM Algorithm 431

16.8 Exercises 434

16.9 Bibliographic Notes 436

Chapter 17 Matching 437

17.1 Introduction 437

17.2 Preliminaries 437

17.3 The Network Flow Method 440

17.4 The Hungarian Tree Method for Bipartite Graphs 441

17.5 Maximum Matching in General Graphs 443

17.6 An O(n2.5) Algorithm for Bipartite Graphs 450

17.7 Exercises 455

17.8 Bibliographic Notes 457

PART 7 Techniques in Computational Geometry 459

Chapter 18 Geometric Sweeping 463

18.1 Introduction 463

18.2 Geometric Preliminaries 465

18.3 Computing the Intersections of Line Segments 467

18.4 The Convex Hull Problem 471

18.5 Computing the Diameter of a Set of Points 474

18.6 Exercises 478

18.7 Bibliographic Notes 480

Chapter 19 Voronoi Diagrams 481

19.1 Introduction 481

19.2 Nearest-Point Voronoi Diagram 481

19.2.1 Delaunay triangulation 484

19.2.2 Construction of the Voronoi diagram 486

19.3 Applications of the Voronoi Diagram 489

19.3.1 Computing the convex hull 489

19.3.2 All nearest neighbors 490

19.3.3 The Euclidean minimum spanning tree 491

19.4 Farthest-Point Voronoi Diagram 492

19.4.1 Construction of the farthest-point Voronoi diagram 493

19.5 Applications of the Farthest-Point Voronoi Diagram 496

19.5.1 All farthest neighbors 496

19.5.2 Smallest enclosing circle 497

19.6 Exercises 497

19.7 Bibliographic Notes 499

Bibliography 501

Index 511