算法设计PDF|Epub|txt|kindle电子书版本网盘下载

算法设计PDF格式电子书版下载

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

1 Introduction：Some Representative Problems1

1.1 A First Problem：Stable Matching1

1.2 Five Representative Problems12

Solved Exercises19

Exercises22

Notes and Further Reading28

2 Basics of Algorithm Analysis29

2.1 Computational Tractability29

2.2 Asymptotic Order of Growth35

2.3 Implementing the Stable Matching Algorithm Using Lists and Arrays42

2.4 A Survey of Common Running Times47

2.5 A More Complex Data Structure：Priority Queues57

Solved Exercises65

Exercises67

Notes and Further Reading70

3 Graphs73

3.1 Basic Definitions and Applications73

3.2 Graph Connectivity and Graph Traversal78

3.3 Implementing Graph Traversal Using Queues and Stacks87

3.4 Testing Bipartiteness：An Application of Breadth-First Search94

3.5 Connectivity in Directed Graphs97

3.6 Directed Acyclic Graphs and Topological Ordering99

Solved Exercises104

Exercises107

Notes and Further Reading112

4 Greedy Algorithms115

4.1 Interval Scheduling：The Greedy Algorithm Stays Ahead116

4.2 Scheduling to Minimize Lateness：An Exchange Argument125

4.3 Optimal Caching：A More Complex Exchange Argument131

4.4 Shortest Paths in a Graph137

4.5 The Minimum Spanning Tree Problem142

4.6 Implementing Kruskal’s Algorithm：The Union-Find Data Structure151

4.7 Clustering157

4.8 Huffman Codes and Data Compression161

4.9 Minimum-Cost Arborescences：A Multi-Phase Greedy Algorithm177

Solved Exercises183

Exercises188

Notes and Further Reading205

5 Divide and Conquer209

5.1 A First Recurrence：The Mergesort Algorithm210

5.2 Further Recurrence Relations214

5.3 Counting Inversions221

5.4 Finding the Closest Pair of Points225

5.5 Integer Multiplication231

5.6 Convolutions and the Fast Fourier Transform234

Solved Exercises242

Exercises246

Notes and Further Reading249

6 Dynamic Programming251

6.1 Weighted Interval Scheduling：A Recursive Procedure252

6.2 Principles of Dynamic Programming：Memoization or Iteration over Subproblems258

6.3 Segmented Least Squares：Multi-way Choices261

6.4 Subset Sums and Knapsacks：Adding a Variable266

6.5 RNA Secondary Structure：Dynamic Programming over Intervals272

6.6 Sequence Alignment278

6.7 Sequence Alignment in Linear Space via Divide and Conquer284

6.8 Shortest Paths in a Graph290

6.9 Shortest Paths and Distance Vector Protocols297

6.10 Negative Cycles in a Graph301

Solved Exercises307

Exercises312

Notes and Further Reading335

7 Network Flow337

7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm338

7.2 Maximum Flows and Minimum Cuts in a Network346

7.3 Choosing Good Augmenting Paths352

7.4 The Preflow-Push Maximum-Flow Algorithm357

7.5 A First Application：The Bipartite Matching Problem367

7.6 Disjoint Paths in Directed and Undirected Graphs373

7.7 Extensions to the Maximum-Flow Problem378

7.8 Survey Design384

7.9 Airline Scheduling387

7.10 Image Segmentation391

7.11 Project Selection396

7.12 Baseball Elimination400

7.13 A Further Direction：Adding Costs to the Matching Problem404

Solved Exercises411

Exercises415

Notes and Further Reading448

8 NP and Computational Intractability451

8.1 Polynomial-Time Reductions452

8.2 Reductions via “Gadgets”：The Satisfiability Problem459

8.3 Efficient Certification and the Definition of NP463

8.4 NP-Complete Problems466

8.5 Sequencing Problems473

8.6 Partitioning Problems481

8.7 Graph Coloring485

8.8 Numerical Problems490

8.9 Co-NP and the Asymmetry of NP495

8.10 A Partial Taxonomy of Hard Problems497

Solved Exercises500

Exercises505

Notes and Further Reading529

9 PSPACE：A Class of Problems beyond NP531

9.1 PSPACE531

9.2 Some Hard Problems in PSPACE533

9.3 Solving Quantified Problems and Games in Polynomial Space536

9.4 Solving the Planning Problem in Polynomial Space538

9.5 Proving Problems PSPACE-Complete543

Solved Exercises547

Exercises550

Notes and Further Reading551

10 Extending the Limits of Tractability553

10.1 Finding Small Vertex Covers554

10.2 Solving NP-Hard Problems on Trees558

10.3 Coloring a Set of Circular Arcs563

10.4 Tree Decompositions of Graphs572

10.5 Constructing a Tree Decomposition584

Solved Exercises591

Exercises594

Notes and Further Reading598

11 Approximation Algorithms599

11.1 Greedy Algorithms and Bounds on the Optimum：A Load Balancing Problem600

11.2 The Center Selection Problem606

11.3 Set Cover：A General Greedy Heuristic612

11.4 The Pricing Method：Vertex Cover618

11.5 Maximization via the Pricing Method：The Disjoint Paths Problem624

11.6 Linear Programming and Rounding：An Application to Vertex Cover630

11.7 Load Balancing Revisited：A More Advanced LP Application637

11.8 Arbitrarily Good Approximations：The Knapsack Problem644

Solved Exercises649

Exercises651

Notes and Further Reading659

12 Local Search661

12.1 The Landscape of an Optimization Problem662

12.2 The Metropolis Algorithm and Simulated Annealing666

12.3 An Application of Local Search to Hopfield Neural Networks671

12.4 Maximum-Cut Approximation via Local Search676

12.5 Choosing a Neighbor Relation679

12.6 Classification via Local Search681

12.7 Best-Response Dynamics and Nash Equilibria690

Solved Exercises700

Exercises702

Notes and Further Reading705

13 Randomized Algorithms707

13.1 A First Application：Contention Resolution708

13.2 Finding the Global Minimum Cut714

13.3 Random Variables and Their Expectations719

13.4 A Randomized Approximation Algorithm for MAX 3-SAT724

13.5 Randomized Divide and Conquer：Median-Finding and Quicksort727

13.6 Hashing：A Randomized Implementation of Dictionaries734

13.7 Finding the Closest Pair of Points：A Randomized Approach741

13.8 Randomized Caching750

13.9 Chemoff Bounds758

13.10 Load Balancing760

13.11 Packet Routing762

13.12 Background：Some Basic Probability Definitions769

Solved Exercises776

Exercises782

Notes and Further Reading793

Epilogue：Algorithms That Run Forever795

References805

Index815