ALGORITHM DESIGNPDF电子书下载

1 Introduction:Some Representative Problems 1

1.1 A First Problem:Stable Matching 1

1.2 Five Representative Problems 12

Solved Exercises 19

Exercises 22

Notes and Further Reading 28

2 Basics of Algorithm Analysis 29

2.1 Computational Tractability 29

2.2 Asymptotic Order of Growth 35

2.3 Implementing the Stable Matching Algorithm Using Lists and Arrays 42

2.4 A Survey of Common Running Times 47

2.5 A More Complex Data Structure:Priority Queues 57

Solved Exercises 65

Exercises 67

Notes and Further Reading 70

3 Graphs 73

3.1 Basic Definitions and Applications 73

3.2 Graph Connectivity and Graph Traversal 78

3.3 Implementing Graph Traversal Using Queues and Stacks 87

3.4 Testing Bipartiteness:An Application of Breadth-First Search 94

3.5 Connectivity in Directed Graphs 97

3.6 Directed Acyclic Graphs and Topological Ordering 99

Solved Exercises 104

Exercises 107

Notes and Further Reading 112

4 Greedy Algorithms 115

4.1 Interval Scheduling:The Greedy Algorithm Stays Ahead 116

4.2 Scheduling to Minimize Lateness:An Exchange Argument 125

4.3 Optimal Caching:A More Complex Exchange Argument 131

4.4 Shortest Paths in a Graph 137

4.5 The Minimum Spanning Tree Problem 142

4.6 Implementing Kruskal's Algorithm:The Union-Find Data Structure 151

4.7 Clustering 157

4.8 Huffman Codes and Data Compression 161

4.9 Minimum-Cost Arborescences:A Multi-Phase Greedy Algorithm 177

Solved Exercises 183

Exercises 188

Notes and Further Reading 205

5 Divide and Conquer 209

5.1 A First Recurrence:The Mergesort Algorithm 210

5.2 Further Recurrence Relations 214

5.3 Counting Inversions 221

5.4 Finding the Closest Pair of Points 225

5.5 Integer Multiplication 231

5.6 Convolutions and the Fast Fourier Transform 234

Solved Exercises 242

Exercises 246

Notes and Further Reading 249

6 Dynamic Programming 251

6.1 Weighted Interval Scheduling:A Recursive Procedure 252

6.2 Principles of Dynamic Programming:Memoization or Iteration over Subproblems 258

6.3 Segmented Least Squares:Multi-way Choices 261

6.4 Subset Sums and Knapsacks:Adding a Variable 266

6.5 RNA Secondary Structure:Dynamic Programming over Intervals 272

6.6 Sequence Alignment 278

6.7 Sequence Alignment in Linear Space via Divide and Conquer 284

6.8 Shortest Paths in a Graph 290

6.9 Shortest Paths and Distance Vector Protocols 297

6.10 Negative Cycles in a Graph 301

Solved Exercises 307

Exercises 312

Notes and Further Reading 335

7 Network Flow 337

7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm 338

7.2 Maximum Flows and Minimum Cuts in a Network 346

7.3 Choosing Good Augmenting Paths 352

7.4 The Preflow-Push Maximum-Flow Algorithm 357

7.5 A First Application:The Bipartite Matching Problem 367

7.6 Disjoint Paths in Directed and Undirected Graphs 373

7.7 Extensions to the Maximum-Flow Problem 378

7.8 Survey Design 384

7.9 Airline Scheduling 387

7.10 Image Segmentation 391

7.11 Project Selection 396

7.12 Baseball Elimination 400

7.13 A Further Direction:Adding Costs to the Matching Problem 404

Solved Exercises 411

Exercises 415

Notes and Further Reading 448

8 NP and Computational Intractability 451

8.1 Polynomial-Time Reductions 452

8.2 Reductions via "Gadgets":The Satisfiability Problem 459

8.3 Efficient Certification and the Definition of NP 463

8.4 NP-Complete Problems 466

8.5 Sequencing Problems 473

8.6 Partitioning Problems 481

8.7 Graph Coloring 485

8.8 Numerical Problems 490

8.9 Co-NP and the Asymmetry of NP 495

8.10 A Partial Taxonomy of Hard Problems 497

Solved Exercises 500

Exercises 505

Notes and Further Reading 529

9 PSPACE:A Class of Problems beyond NP 531

9.1 PSPACE 531

9.2 Some Hard Problems in PSPACE 533

9.3 Solving Quantified Problems and Games in Polynomial Space 536

9.4 Solving the Planning Problem in Polynomial Space 538

9.5 Proving Problems PSPACE-Complete 543

Solved Exercises 547

Exercises 550

Notes and Further Reading 551

10 Extending the Limits of Tractability 553

10.1 Finding Small Vertex Covers 554

10.2 Solving NP-Hard Problems on Trees 558

10.3 Coloring a Set of Circular Arcs 563

10.4 Tree Decompositions of Graphs 572

10.5 Constructing a Tree Decomposition 584

Solved Exercises 591

Exercises 594

Notes and Further Reading 598

11 Approximation Algorithms 599

11.1 Greedy Algorithms and Bounds on the Optimum:A Load Balancing Problem 600

11.2 The Center Selection Problem 606

11.3 Set Cover:A General Greedy Heuristic 612

11.4 The Pricing Method:Vertex Cover 618

11.5 Maximization via the Pricing Method:The Disjoint Paths Problem 624

11.6 Linear Programming and Rounding:An Application to Vertex Cover 630

11.7 Load Balancing Revisited:A More Advanced LP Application 637

11.8 Arbitrarily Good Approximations:The Knapsack Problem 644

Solved Exercises 649

Exercises 651

Notes and Further Reading 659

12 Local Search 661

12.1 The Landscape of an Optimization Problem 662

12.2 The Metropolis Algorithm and Simulated Annealing 666

12.3 An Application of Local Search to Hopfield Neural Networks 671

12.4 Maximum-Cut Approximation via Local Search 676

12.5 Choosing a Neighbor Relation 679

12.6 Classification via Local Search 681

12.7 Best-Response Dynamics and Nash Equilibria 690

Solved Exercises 700

Exercises 702

Notes and Further Reading 705

13 Randomized Algorithms 707

13.1 A First Application:Contention Resolution 708

13.2 Finding the Global Minimum Cut 714

13.3 Random Variables and Their Expectations 719

13.4 A Randomized Approximation Algorithm for MAX 3-SAT 724

13.5 Randomized Divide and Conquer:Median-Finding and Quicksort 727

13.6 Hashing:A Randomized Implementation of Dictionaries 734

13.7 Finding the Closest Pair of Points:A Randomized Approach 741

13.8 Randomized Caching 750

13.9 Chernoff Bounds 758

13.10 Load Balancing 760

13.11 Packet Routing 762

13.12 Background:Some Basic Probability Definitions 769

Solved Exercises 776

Exercises 782

Notes and Further Reading 793

Epilogue:Algorithms That Run Forever 795

References 805

Index 815