算法设计技巧与分析 英文版PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

PART 1 Basic Concepts and Introduction to Algorithms1

Chapter 1 Basic Concepts in Algorithmic Analysis5

1.1 Introduction5

1.2 Historical Background6

1.3 Binary Search8

1.3.1 Analysis of the binary search algorithm10

1.4 Merging Two Sorted Lists12

1.5 Selection Sort14

1.6 Insertion Sort15

1.7 Bottom-Up Merge Sorting17

1.7.1 Analysis of bottom-up merge sorting19

1.8 Time Complexity20

1.8.1 Order of growth21

1.8.2 The O-notation25

1.8.3 The Ω-notation26

1.8.4 The ？-notation27

1.8.5 Examples29

1.8.6 Complexity clases and the o-notation31

1.9 Space Complexity32

1.10 Optimal Algorithms34

1.11 How to Estimate the Running Time of an Algorithm35

1.11.1 Counting the number of iterations35

1.11.2 Counting the frequency of basic operations38

1.11.3 Using recurrence relations41

1.12 Worst case and average case analysis42

1.12.1 Worst case analysis44

1.12.2 Average case analysis46

1.13 Amortized Analysis47

1.14 Input Size and Problem Instance50

1.15 Exercises52

1.16 Bibliographic Notes59

Chapter 2 Mathematical Preliminaries61

2.1 Sets，Relations and Functions61

2.1.1 Sets62

2.1.2 Relations63

2.1.2.1 Equivalence relations64

2.1.3 Functions64

2.2 Proof Methods65

2.2.1 Direct proof65

2.2.2 Indirect proof66

2.2.3 Proof by contradiction66

2.2.4 Proof by counterexample67

2.2.5 Mathematical induction68

2.3 Logarithms69

2.4 Floor and Ceiling Functions70

2.5 Factorial and Binomial Coefficients71

2.5.1 Factorials71

2.5.2 Binomial coeffcients73

2.6 The Pigeonhole Principle75

2.7 Summations76

2.7.1 Approximation of summations by integration78

2.8 Recurrence Relations82

2.8.1 Solution of linear homogeneous recurrences83

2.8.2 Solution of inhomogeneous recurrences85

2.8.3 Solution of divide-and-conquer recurrences87

2.8.3.1 Expanding the recurrence87

2.8.3.2 Substitution91

2.8.3.3 Change of variables95

2.9 Exercises98

Chapter 3 Data Structures103

3.1 Introduction103

3.2 Linked Lists103

3.2.1 Stacks and queues104

3.3 Graphs104

3.3.1 Representation of graphs106

3.3.2 Planar graphs107

3.4 Trees108

3.5 Rooted Trees108

3.5.1 Tree traversals109

3.6 Binary Trees109

3.6.1 Some quantitative aspects of binary trees111

3.6.2 Binary search trees112

3.7 Exercises112

3.8 Bibliographic Notes114

Chapter 4 Heaps and the Disjoint Sets Data Structures115

4.1 Introduction115

4.2 Heaps115

4.2.1 Operations on heaps116

4.2.2 Creating a heap120

4.2.3 Heapsort124

4.2.4 Min and max heaps125

4.3 Disjoint Sets Data Structures125

4.3.1 The union by rank heuristic127

4.3.2 Path compression129

4.3.3 The union-find algorithms130

4.3.4 Analysis of the union-find algorithms132

4.4 Exercises134

4.5 Bibliographic Notes137

PART 2 Techniques Based on Recursion139

Chapter 5 Induction143

5.1 Introduction143

5.2 Two Simple Examples144

5.2.1 Selection sort144

5.2.2 Insertion sort145

5.3 Radix Sort145

5.4 Integer Exponentiation148

5.5 Evaluating Polynomials（Horner’s Rule）149

5.6 Generating Permutations150

5.6.1 The first algorithm150

5.6.2 The second algorithm152

5.7 Finding the Majority Element154

5.8 Exercises155

5.9 Bibliographic Notes158

Chapter 6 Divide and Conquer161

6.1 Introduction161

6.2 Binary Search163

6.3 Mergesort165

6.3.1 How the algorithm works166

6.3.2 Analysis of the mergesort algorithm167

6.4 The Divide and Conquer Paradigm169

6.5 Selection：Finding the Median and the kth Smallest Element172

6.5.1 Analysis of the selection algorithm175

6.6 Quicksort177

6.6.1 A partitioning algorithm177

6.6.2 The sorting algorithm179

6.6.3 Analysis of the quicksort algorithm181

6.6.3.1 The worst case behavior181

6.6.3.2 The average case behavior184

6.6.4 Comparison of sorting algorithms186

6.7 Multiplication of Large Integers187

6.8 Matrix Multiplication188

6.8.1 The traditional algorithm188

6.8.2 Recursive version188

6.8.3 Strassen’s algorithm190

6.8.4 Comparisons of the three algorithms191

6.9 The Closest Pair Problem192

6.9.1 Time complexity194

6.10 Exercises195

6.11 Bibliographic Notes202

Chapter 7 Dynamic Programming203

7.1 Introduction203

7.2 The Longest Common Subsequence Problem205

7.3 Matrix Chain Multiplication208

7.4 The Dynamic Programming Paradigm214

7.5 The All-Pairs Shortest Path Problem215

7.6 The Knapsack Problem217

7.7 Exercises220

7.8 Bibliographic Notes226

PART 3 First-Cut Techniques227

Chapter 8 The Greedy Approach231

8.1 Introduction231

8.2 The Shortest Path Problem232

8.2.1 A linear time algorithm for dense graphs237

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 graphs246

8.5 File Compression248

8.6 Exercises251

8.7 Bibliographic Notes255

Chapter 9 Graph Traversal257

9.1 Introduction257

9.2 Depth-First Search257

9.2.1 Time complexity of depth-first search261

9.3 Applications of Depth-First Search262

9.3.1 Graph acyclicity262

9.3.2 Topological sorting262

9.3.3 Finding articulation points in a graph263

9.3.4 Strongly connected components266

9.4 Breadth-First Search267

9.5 Applications of Breadth-First Search269

9.6 Exercises270

9.7 Bibliographic Notes273

PART 4 Complexity of Problems275

Chapter 10 NP-Complete Problems279

10.1 Introduction279

10.2 The Class P282

10.3 The Class NP283

10.4 NP-Complete Problems285

10.4.1 The satisfiability problem285

10.4.2 Vertex cover，independent set and clique problems288

10.4.3 More NP-complete Problems291

10.5 The Class co-NP292

10.6 The Class NPI294

10.7 The Relationships Between the Four Classes295

10.8 Exercises296

10.9 Bibliographic Notes298

Chapter 11 Introduction to Computational Complexity299

11.1 Introduction299

11.2 Model of Computation：The Turing Machine299

11.3 k-tape Turing Machines and Time complexity300

11.4 Off-Line Turing Machines and Space Complexity303

11.5 Tape Compression and Linear Speed-Up305

11.6 Relationships Between Complexity Classes306

11.6.1 Space and time hierarchy theorems309

11.6.2 Padding arguments311

11.7 Reductions313

11.8 Completeness318

11.8.1 NLOGSPACE-complete problems318

11.8.2 PSPACE-complete problems319

11.8.3 P-complete problems321

11.8.4 Some conclusions of completeness323

11.9 The Polynomial Time Hierarchy324

11.10 Exercises328

11.11 Bibliographic Notes332

Chapter 12 Lower Bounds335

12.1 Introduction335

12.2 Trivial Lower Bounds335

12.3 The Decision Tree Model336

12.3.1 The search problem336

12.3.2 The sorting problem337

12.4 The Algebraic Decision Tree Model339

12.4.1 The element uniqueness problem341

12.5 Linear Time Reductions342

12.5.1 The convex hull problem342

12.5.2 The closest pair problem343

12.5.3 The Euclidean minimum spanning tree problem344

12.6 Exercises345

12.7 Bibliographic Notes346

PART 5 Coping with Hardness349

Chapter 13 Backtracking353

13.1 Introduction353

13.2 The 3-Coloring Problem353

13.3 The 8-Queens Problem357

13.4 The General Backtracking Method360

13.5 Branch and Bound362

13.6 Exercises367

13.7 Bibliographic notes369

Chapter 14 Randomized Algorithms371

14.1 Introduction371

14.2 Las Vegas and Monte Carlo Algorithms372

14.3 Randomized Quicksort373

14.4 Randomized Selection374

14.5 Testing String Equality377

14.6 Pattern Matching379

14.7 Random Sampling381

14.8 Primality Testing384

14.9 Exercises390

14.10 Bibliographic Notes392

Chapter 15 Approximation Algorithms393

15.1 Introduction393

15.2 Basic Definitions393

15.3 Difference Bounds394

15.3.1 Planar graph coloring395

15.3.2 Hardness result：the knapsack problem395

15.4 Relative Performance Bounds396

15.4.1 The bin packing problem397

15.4.2 The Euclidean traveling salesman problem399

15.4.3 The vertex cover problem401

15.4.4 Hardness result：the traveling salesman problem402

15.5 Polynomial Approximation Schemes404

15.5.1 The knapsack problem404

15.6 Fully Polynomial Approximation Schemes407

15.6.1 The subset-sum problem408

15.7 Exercises410

15.8 Bibliographic Notes413

PART 6 Iterative Improvement for Domain-Specific Problems415

Chapter 16 Network Flow419

16.1 Introduction419

16.2 Preliminaries419

16.3 The Ford-Fulkerson Method423

16.4 Maximum Capacity Augmentation424

16.5 Shortest Path Augmentation426

16.6 Dinic’s Algorithm429

16.7 The MPM Algorithm431

16.8 Exercises434

16.9 Bibliographic Notes436

Chapter 17 Matching437

17.1 Introduction437

17.2 Preliminaries437

17.3 The Network Flow Method440

17.4 The Hungarian Tree Method for Bipartite Graphs441

17.5 Maximum Matching in General Graphs443

17.6 An O（n2.5）Algorithm for Bipartite Graphs450

17.7 Exercises455

17.8 Bibliographic Notes457

PART 7 Techniques in Computational Geometry459

Chapter 18 Geometric Sweeping463

18.1 Introduction463

18.2 Geometric Preliminaries465

18.3 Computing the Intersections of Line Segments467

18.4 The Convex Hull Problem471

18.5 Computing the Diameter of a Set of Points474

18.6 Exercises478

18.7 Bibliographic Notes480

Chapter 19 Voronoi Diagrams481

19.1 Introduction481

19.2 Nearest-Point Voronoi Diagram481

19.2.1 Delaunay triangulation484

19.2.2 Construction of the Voronoi diagram486

19.3 Applications of the Voronoi Diagram489

19.3.1 Computing the convex hull489

19.3.2 All nearest neighbors490

19.3.3 The Euclidean minimum spanning tree491

19.4 Farthest-Point Voronoi Diagram492

19.4.1 Construction of the farthest-point Voronoi diagram493

19.5 Applications of the Farthest-Point Voronoi Diagram496

19.5.1 All farthest neighbors496

19.5.2 Smallest enclosing circle497

19.6 Exercises497

19.7 Bibliographic Notes499

Bibliography501

Index511