第1章 入门 1
1.1问题 1
1.2算法的概念 1
1.3算法的正确性 3
1.4算法的效率 5
1.5问题的下界 9
1.6小结 10
习题 11
实验题 12
第2章 渐近符号 13
2.1 Θ符号 13
2.2 Ο符号 15
2.3 Ω符号 16
2.4渐近符号的性质 17
2.5常用函数的直观含义 18
2.6小结 18
习题 19
第3章 算法分析方法 20
3.1概率分析 20
3.2分摊分析 22
3.2.1合计方法 23
3.2.2记账方法 25
3.2.3势能方法 27
3.3实验分析 29
3.4小结 30
习题 31
第4章 递归 32
4.1算法思想 32
4.1.1递归算法的应用 33
4.1.2递归与迭代 40
4.2递归方程的求解 41
4.2.1替换方法 41
4.2.2递归树方法 43
4.2.3公式法 45
4.3多项式求值实验 47
4.4小结 48
习题 48
实验题 49
第5章 分治算法 50
5.1算法思想 50
5.2合并排序 51
5.3快速排序 53
5.4大整数乘法 56
5.5矩阵乘法 58
5.6残缺棋盘游戏 59
5.7快速傅里叶变换（FFT） 62
5.8小结 63
习题 63
实验题 65
第6章 动态规划 66
6.1算法思想 66
6.2装配线调度问题 68
6.3矩阵链乘法问题 73
6.4最长公共子序列问题 77
6.5 0/1背包问题 81
6.6最优二叉搜索树问题 84
6.7动态规划的基本性质 88
6.8小结 92
习题 92
实验题 94
第7章 贪心算法 95
7.1算法思想 95
7.2任务选择问题 95
7.3背包问题 100
7.4哈夫曼编码问题 102
7.5缓存维护问题 106
7.6任务选择问题实验 108
7.7小结 109
习题 109
实验题 111
第8章 图算法 112
8.1图的搜索问题 113
8.1.1宽度优先搜索 113
8.1.2深度优先搜索 117
8.2最小生成树问题 121
8.2.1 Kruskal算法 122
8.2.2 Prim算法 124
8.3最短路径问题 125
8.3.1单个源点的最短路径问题 128
8.3.2所有点对的最短路径问题 131
8.4小结 134
习题 135
实验题 137
第9章 网络流与匹配 138
9.1最大流问题 138
9.1.1 FordFulkerson方法 140
9.1.2最短路径增广算法 145
9.1.3 Dinic算法 148
9.1.4 MPM算法 151
9.1.5最大流问题的变形 152
9.2最小费用流问题 153
9.2.1消除回路算法 154
9.2.2最小费用路算法 156
9.2.3最小费用路算法的改进 158
9.3匹配问题 160
9.3.1二分图匹配 163
9.3.2一般图的匹配 167
9.4小结 172
习题 172
实验题 174
第10章 线性规划 175
10.1线性规划问题 175
10.1.1线性规划问题的标准形式 176
10.1.2线性规划问题的松弛形式 178
10.2求解算法 180
10.2.1图解法 180
10.2.2单纯形算法 181
10.3对偶 188
10.4小结 192
习题 192
实验题 193
第11章NP完全理论 194
11.1判定问题 195
11.2 P和NP 197
11.3 NPC 201
11.3.1 NPC的定义 201
11.3.2电路可满足性问题 203
11.4 NPC的证明 206
11.4.1可满足性问题 206
11.4.2 3-CNF可满足性问题 208
11.4.3团问题 210
11.4.4顶点覆盖问题 212
11.5其他NP完全问题 213
11.6小结 215
习题 215
第12章 回溯 218
12.1算法思想 218
12.2装载问题 222
12.3 0/1背包问题 226
12.4着色问题 228
12.5 n皇后问题 230
12.6旅行商问题 232
12.7流水作业调度问题 234
12.8零件切割问题 236
12.9小结 238
习题 238
实验题 240
第13章 分支限界 241
13.1算法思想 241
13.2装载问题 243
13.3 0/1背包问题 251
13.4可满足性问题 254
13.5旅行商问题 256
13.6流水作业调度问题 258
13.7 0/1背包问题实验 260
13.8小结 261
习题 262
实验题 263
第14章 启发式搜索 264
14.1算法思想 264
14.2 A搜索 265
14.2.1最短路径问题 267
14.2.2 8数字问题 268
14.3博弈搜索算法 271
14.3.1α和β剪支 273
14.3.2分硬币游戏 275
14.3.3井字博弈 275
14.4小结 281
习题 281
实验题 283
第15章 数论 284
15.1数论基础 284
15.2最大公约数 287
15.3同余 289
15.4模幂运算 294
15.5数论的应用 295
15.5.1 Hash函数 295
15.5.2 RSA公钥加密系统 296
15.6小结 299
习题 299
实验题 300
第16章 计算几何 301
16.1叉积及其应用 301
16.2计算任意线段的交点 304
16.3凸包 306
16.3.1礼物包装算法 307
16.3.2 Graham扫描法 309
16.3.3分治算法求凸包 310
16.4最近点对 316
16.5 Voronoi图 318
16.5.1 Voronoi图的定义及其性质 318
16.5.2 Voronoi图的构造 321
16.5.3 Voronoi图的应用 325
16.6小结 327
习题 327
实验题 328
参考文献 329