算法设计(英文版)

目录

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 / 实现Kruskal算法：Union-Find数据结构　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 / RNA二级结构：在区间上的动态规划　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 / *大流问题与Ford-Fulkerson算法　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 / NP与计算的难解性　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 / 有效证书和NP的定义　463

8.4　NP-Complete Problems / NP完全问题　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 / Co-NP及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 / PSPACE：一类超出NP的问题　531

9.1　PSPACE / PSPACE　531

9.2　Some Hard Problems in PSPACE / 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 / 证明问题是PSPACE完全的　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 / 在树上解NP难问题　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 / 再论负载均衡：更高级的LP应用　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 / Metropolis算法与模拟退火算法　666

12.3　An Application of Local Search to Hopfield Neural Networks / 局部搜索在Hopfield神经网络中的应用　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 / 关于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