1引言：一些典型问题 1
1.1第一个问题：稳定匹配 1
1.2五个典型问题 12
带解答的练习 19
练习 22
注释和进一步阅读 28
2算法分析基础 29
2.1计算可解性 29
2.2增长的渐近阶 35
2.3用列表和数组实现稳定匹配算法 42
2.4常见运行时间综述 47
2.5更复杂的数据结构：优先队列 57
带解答的练习 65
练习 67
注释和进一步阅读 70
3图 73
3.1基本定义与应用 73
3.2图连通性与图遍历 78
3.3用优先队列与栈实现图遍历 87
3.4二分性测试：广度优先搜索的应用 94
3.5有向图中的连通性 97
3.6有向无环图和拓扑排序 99
带解答的练习 104
练习 107
注释和进一步阅读 112
4贪心算法 115
4.1区间调度：贪心算法保持领先 116
4.2最小延迟的调度：交换论证 125
4.3最优缓存：更复杂的交换论证 131
4.4图的最短路径 137
4.5最小生成树问题 142
4.6实现Kruskal算法：Union-Find数据结构 151
4.7聚类 157
4.8哈夫曼码和数据压缩 161
4.9最小费用有向树：多阶段贪心算法 177
带解答的练习 183
练习 188
注释和进一步阅读 205
5分治 209
5.1第一个递推式：归并排序算法 210
5.2进一步的递推关系 214
5.3计数逆序 221
5.4寻找最近点对 225
5.5整数乘法 231
5.6卷积和快速傅里叶变换 234
带解答的练习 242
练习 246
注释和进一步阅读 249
6动态规划 251
6.1加权区间调度：递归过程 252
6.2动态规划原理：备忘录或子问题迭代 258
6.3分段最小二乘：多重选择 261
6.4子集和与背包：加一个变量 266
6.5RNA二级结构：区间上的动态规划 272
6.6序列比对 278
6.7通过分治在线性空间中的序列比对 284
6.8图中的最短路径 290
6.9最短路径和距离向量协议 297
6.10图中的负环 301
带解答的练习 307
练习 312
注释和进一步阅读 335
7网络流 337
7.1最大流问题和Ford-Fulkerson算法 338
7.2网络中的最大流和最小割 346
7.3选择好的增广路径 352
7.4预流推动最大流算法 357
7.5第一个应用：二分匹配问题 367
7.6有向图和无向图中的不相交路径 373
7.7最大流问题的推广 378
7.8调查设计 384
7.9航线调度 387
7.10图像分割 391
7.11项目选择 396
7.12棒球排除 400
7.13进一步的方向：对匹配问题增加费用 404
带解答的练习 411
练习 415
注释和进一步阅读 448
8 NP和计算难解性 451
8.1多项式时间归约 452
8.2通过“小配件”归约：可满足性问题 459
8.3有效证书和NP的定义 463
8.4NP完全问题 466
8.5排序问题 473
8.6划分问题 481
8.7图着色 485
8.8数值问题 490
8.9Co-NP和NP的不对称性 495
8.10困难问题的部分分类 497
带解答的练习 500
练习 505
注释和进一步阅读 529
9PSPACE：NP之外的一类问题 531
9.1 PSPACE 531
9.2 PSPACE中的一些难题 533
9.3在多项式空间中求解量化问题和博弈 536
9.4在多项式空间中求解规划问题 538
9.5证明问题是PSPACE完全的 543
带解答的练习 547
练习 550
注释和进一步阅读 551
10扩展易解性的界限 553
10.1寻找小的顶点覆盖 554
10.2求解树上的NP难问题 558
10.3圆弧集着色 563
10.4图的树分解 572
10.5构造树分解 584
带解答的练习 591
练习 594
注释和进一步阅读 598
11近似算法 599
11.1贪心算法和最优值的界限：负载均衡问题 600
11.2中心选址问题 606
11.3集合覆盖：一般贪心启发式 612
11.4定价方法：顶点覆盖 618
11.5用定价方法最大化：不相交路径问题 624
11.6线性规划和舍入：顶点覆盖的应用 630
11.7再论负载均衡：更高级的LP应用 637
11.8任意好的近似：背包问题 644
带解答的练习 649
练习 651
注释和进一步阅读 659
12局部搜索 661
12.1优化问题的地形 662
12.2Metropolis算法和模拟退火算法 666
12.3局部搜索在Hopfield神经网络中的应用 671
12.4通过局部搜索进行最大割近似 676
12.5选择邻居关系 679
12.6用局部搜索分类 681
12.7最佳响应动态和纳什均衡 690
带解答的练习 700
练习 702
注释和进一步阅读 705
13随机算法 707
13.1第一个应用：消除争用 708
13.2寻找全局最小割 714
13.3随机变量及其期望 719
13.4MAX 3-SAT的随机近似算法 724
13.5随机分治：找中位数和快速排序 727
13.6散列：字典的随机实现 734
13.7寻找最近点对：随机方法 741
13.8随机缓存 750
13.9切尔诺夫界 758
13.10负载均衡 760
13.11分组路由 762
13.12背景知识：一些基本概率定义 769
带解答的练习 776
练习 782
注释和进一步阅读 793
后记：永远运行的算法 795
参考文献 805