目   录
卷I 实用算法设计
第1章 算法设计简论	3
1.1 机器人巡游最优化	4
1.2 合理挑选工作 	8
1.3 关于正确性的推理	11
1.3.1 问题和特性	11
1.3.2 表述算法 	12
1.3.3 论证非正确性	13
1.4 归纳与递归	14
1.5 建立问题的模型	16
1.5.1 组合式对象	17
1.5.2 递归式对象	18
1.6 反证法	20
1.7 关于“算法征战逸事”	20
1.8 算法征战逸事: 通灵者的模型建立	21
1.9 估算 	24
1.10 习题	25
第2章 算法分析	30
2.1 RAM计算模型	30
2.2 大O记号	32
2.3 增长量级与强弱关系	35
2.4 以大O来推演公式	37
2.4.1 函数相加 	38
2.4.2 函数相乘 	38
2.5 关于效率的推理	39
2.5.1 选择排序 	39
2.5.2 插入排序 	40
2.5.3 字符串模式匹配	41
2.5.4 矩阵乘法 	43
2.6 求和 	44
2.7 对数及其应用 	46
2.7.1 对数与二分查找	46
2.7.2 对数与树 	46
2.7.3 对数与比特	46
2.7.4 对数与乘法	47
2.7.5 快速求幂 	47
2.7.6 对数与求和	48
2.7.7 对数与司法正义	48
2.8 对数的特性	50
2.9 算法征战逸事: 锥体之秘	51
2.10 高等分析(*) 	53
2.10.1 一些深奥难懂的函数	54
2.10.2 极限与强弱关系	55
2.11 习题	56
第3章 数据结构.	65
3.1 紧接数据结构与链接数据结构	65
3.1.1 数组.	66
3.1.2 指针与链接结构	67
3.1.3 对比.	69
3.2 容器: 栈与队列.	70
3.3 字典 	71
3.4 二叉查找树	75
3.4.1 实现二叉查找树	76
3.4.2 二叉查找树究竟能有多好.	80
3.4.3 平衡查找树	80
3.5 优先级队列	82
3.6 算法征战逸事: 剥离三角剖分	84
3.7 散列 	87
3.7.1 碰撞消除 	87
3.7.2 凭借散列实现副本检测.	89
3.7.3 其他散列技巧.	91
3.7.4 规范化	91
3.7.5 精简.	91
3.8 专用数据结构 	92
3.9 算法征战逸事: 把它们串起来	93
3.10 习题	96
第4章 排序 	103
4.1 排序的应用 	103
4.2 排序的范式 	107
4.3 堆排序: 借助数据结构而得的最优排序.	108
4.3.1 堆	109
4.3.2 建堆.	111
4.3.3 取最小元 	112
4.3.4 更快的建堆算法(*) 	114
4.3.5 利用增量式插入来排序.	116
4.4 算法征战逸事: 给我一张机票	117
4.5 归并排序: 通过分治来排序	119
4.6 快速排序: 通过随机化来排序	122
4.6.1 快速排序期望情况的直观解释 	124
4.6.2 随机化算法.	125
4.6.3 快速排序真的快吗 	127
4.7 分配排序: 通过装桶来排序	127
4.8 算法征战逸事: 为被告辩护的Skiena	129
4.9 习题	131
第5章 分治 	138
5.1 二分查找及相关算法 	138
5.1.1 出现次数的计数	139
5.1.2 单侧二分查找.	140
5.1.3 平方根和其他方根 	140
5.2 算法征战逸事: 错中揪错.	141
5.3 递推关系	142
5.4 求解分治递推关系	144
5.5 快速乘法	145
5.6 最大子范围与最近点对 .	146
5.7 并行算法	148
5.7.1 数据并行化.	149
5.7.2 并行化的陷阱.	149
5.8 算法征战逸事: 毫无进展.	150
5.9 卷积(*).	151
5.9.1 卷积的应用.	152
5.9.2 快速多项式乘法(**) .	153
5.10 习题	155
第6章 散列与随机化算法	158
6.1 重温概率论 	159
6.1.1 概率.	159
6.1.2 复合事件与独立性 	160
6.1.3 条件概率 	161
6.1.4 概率分布 	162
6.1.5 均值与方差.	163
6.1.6 投掷硬币 	163
6.2 理解球与箱 	165
6.3 为什么散列是随机化算法.	167
6.4 Bloom过滤器	168
6.5 生日悖论和完美散列 	170
6.6 取小式散列 	172
6.7 高效字符串匹配.	174
6.8 素性检验	176
6.9 算法征战逸事: 将我的中间名首字母告诉Knuth	177
6.10 随机数从何而来	178
6.11 习题	179
第7章 图的遍历	182
7.1 图的风格	183
7.2 用于图的数据结构	187
7.3 算法征战逸事: 我曾是摩尔定律的受害者	191
7.4 算法征战逸事: 图的获取.	194
7.5 遍历图	196
7.6 广度优先搜索 	196
7.6.1 实现.	198
7.6.2 发掘遍历的功用	199
7.6.3 寻找路径 	199
7.7 广度优先搜索的应用 	200
7.7.1 连通分量 	200
7.7.2 双色图	201
7.8 深度优先搜索 	202
7.9 深度优先搜索的应用 	205
7.9.1 寻找环	206
7.9.2 关节点	206
7.10 有向图的深度优先搜索.	210
7.10.1 拓扑排序	211
7.10.2 强连通分量.	212
7.11 习题	215
第8章 加权图算法	222
8.1 最小生成树 	222
8.1.1 Prim算法	223
8.1.2 Kruskal算法.	226
8.1.3 合并—查找数据结构	228
8.1.4 最小生成树的变种 	230
8.2 算法征战逸事: 网络之外别无他求.	231
8.3 最短路径	234
8.3.1 Dijkstra算法.	234
8.3.2 全图点对最短路径 	237
8.3.3 传递闭包 	239
8.4 算法征战逸事: 拨出文档.	239
8.5 网络流和二部匹配	243
8.5.1 二部匹配 	243
8.5.2 计算网络流.	244
8.6 随机化最小割 	247
8.7 去设计图, 而非算法	248
8.8 习题	251
第9章 组合搜索	255
9.1 回溯	255
9.2 回溯实例	258
9.2.1 构建全部子集.	258
9.2.2 构建全部置换.	259
9.2.3 构建图的全部路径 	260
9.3 搜索剪枝法 	262
9.4 数独	263
9.5 算法征战逸事: 覆盖棋盘.	267
9.6 最佳优先搜索 	271
9.7 A.启发式方法.	272
9.8 习题	274
第10章 动态规划	279
10.1 缓存与计算 	280
10.1.1 以递归计算Fibonacci数	280
10.1.2 以缓存计算Fibonacci数	281
10.1.3 以动态规划计算Fibonacci数	 283
10.1.4 二项式系数.	283
10.2 字符串近似匹配	285
10.2.1 以递归计算编辑距离	.286
10.2.2 以动态规划求解编辑距离	287
10.2.3 重建路径	289
10.2.4 编辑距离的变种	291
10.3 最长递增子序列	293
10.4 算法征战逸事: 条码的文本压缩.	295
10.5 无次序划分/子集和值 .	298
10.6 算法征战逸事: 功率平衡	.300
10.7 依次序划分问题	302
10.8 上下文无关语言的语法分析	305
10.9 动态规划的局限性: TSP.	307
10.9.1 动态规划算法什么时候是正确的?.	308
10.9.2 动态规划算法什么时候是高效的?.	309
10.10 算法征战逸事: 过去所发生的事就是Prolog	310
10.11 习题	313
第11章 NP完全	321
11.1 问题和归约 	321
11.1.1 关键思想	322
11.1.2 判定问题	323
11.2 算法的归约 	323
11.2.1 最近点对	324
11.2.2 最长递增子序列	324
11.2.3 最小公倍数.	325
11.2.4 凸包(*) 	326
11.3 基础性的难解性归约 	327
11.3.1 哈密顿环	328
11.3.2 独立集和顶点覆盖 	329
11.3.3 团	332
11.4 可满足性	333
11.5 创造性的归约	335
11.5.1 顶点覆盖	335
11.5.2 整数规划	337
11.6 难解性证明的艺术	339
11.7 算法征战逸事: 争分夺秒亦难.	340
11.8 算法征战逸事: 后来我失败了	.343
11.9 P与NP	345
11.9.1 验证与发现	.345
11.9.2 P类和NP类.	345
11.9.3 可满足性问题为何如此之难	 346
11.9.4 是NP难解还是NP完全?	346
11.10 习题	348
第12章 处理难解问题	354
12.1 近似算法	354
12.2 顶点覆盖问题的近似算法	355
12.3 欧氏空间旅行商问题	 357
12.4 何时平均已经够好	360
12.4.1 最大化k-SAT	360
12.4.2 最大无环子图	361
12.5 集合覆盖	361
12.6 启发式搜索方法	363
12.6.1 随机抽样	364
12.6.2 局部搜索	366
12.6.3 模拟退火	368
12.6.4 模拟退火的应用	372
12.7 算法征战逸事: 只不过它不是收音机而已	.373
12.8 算法征战逸事: 对阵列退火	376
12.9 遗传算法与其他启发式搜索方法	.379
12.10 量子计算 	380
12.10.1 “Quantum”计算机的特性	.380
12.10.2 Grover数据库搜索算法	382
12.10.3 更快的“Fourier”变换	383
12.10.4 整数因子分解的Shor算法	384
12.10.5 展望量子计算	385
12.11 习题	387
第13章 如何设计算法	390
卷II 算法世界搭车客指南
第14章 算法问题目录册	397
第15章 数据结构	399
15.1 字典	399
15.2 优先级队列 	404
15.3 后缀树和后缀数组	407
15.4 图数据结构 	410
15.5 集合数据结构	413
15.6  k维树.	416
第16章 数值问题	420
16.1 解线性方程组	421
16.2 带宽约减	424
16.3 矩阵乘法	426
16.4 行列式与积和式	428
16.5 约束最优化与无约束最优化	430
16.6 线性规划	434
16.7 随机数生成	 437
16.8 因子分解与素性检验	 440
16.9 精确算术	443
16.10 背包问题	 446
16.11 离散傅里叶变换	449
第17章 组合问题	453
17.1 排序	453
17.2 查找	457
17.3 中位数和选择	461
17.4 生成置换	463
17.5 生成子集	467
17.6 生成划分	469
17.7 图的生成	473
17.8 日历计算	477
17.9 作业调度	478
17.10 可满足性	 481
第18章 图问题: 多项式时间.	484
18.1 连通分量	484
18.2 拓扑排序	487
18.3 最小生成树	 489
18.4 最短路径	494
18.5 传递闭包与传递约简 	498
18.6 匹配	500
18.7 欧拉环/中国邮递员	 503
18.8 边连通度与顶点连通度	.506
18.9 网络流	508
18.10 精致绘图	 511
18.11 绘树	514
18.12 平面性检验与嵌入	 516
第19章 图问题: NP难解	520
19.1 团	 520
19.2 独立集	523
19.3 顶点覆盖	525
19.4 旅行商问题	 527
19.5 哈密顿环	530
19.6 图划分	533
19.7 顶点着色	535
19.8 边着色	539
19.9 图同构	540
19.10 Steiner树 	544
19.11 反馈边集/反馈顶点集	.547
第20章 计算几何	551
20.1 稳健的几何基元操作	 551
20.2 凸包	555
20.3 三角剖分	558
20.4 Voronoi图 	561
20.5 最近邻搜索	 563
20.6 范围搜索	566
20.7 点定位	569
20.8 相交检测	571
20.9 装箱问题	574
20.10 中轴变换 	577
20.11 多边形划分	 579
20.12 简化多边形	 582
20.13 形状相似度	 584
20.14 运动规划	 587
20.15 直线排布维护	.590
20.16 Minkowski和	.592
第21章 集合与字符串问题	595
21.1 集合覆盖	595
21.2 组集	598
21.3 字符串匹配	 600
21.4 字符串近似匹配	603
21.5 文本压缩	607
21.6 密码学	610
21.7 有限状态机最小化	613
21.8 最长公共子串/最长公共子序列 	 616
21.9 最短公共超串	618
第22章 算法相关资源	621
22.1 算法库	621
22.1.1 LEDA 	621
22.1.2 CGAL 	622
22.1.3 Boost图库	622
22.1.4 Netlib 	622
22.1.5 ACM算法集萃	623
22.1.6 GitHub与SourceForge.	623
22.1.7 The Stanford GraphBase	623
22.1.8 Combinatorica	624
22.1.9 源自书籍的程序	624
22.2 数据源	625
22.3 在线文献资源	626
22.4 专业咨询服务	626
参考文献	627