第1章 导论

1.1 什么是算法

1.2 算法规范

1.2.1 导论

1.2.2 递归算法

1.3 性能分析

1.3.1 空间复杂度

1.3.2 时间复杂度

1.3.3 平摊复杂度

1.3.4 渐进符号（O，Ω，Θ）

1.3.5 实际复杂度

1.3.6 性能测量

1.4 概率算法

1.4.1 概率论基础

1.4.2 随机算法：正规描述

1.4.3 确认重复元素

1.4.4 素数测试

1.4.5 优缺点

1.5 参考文献及阅读

第2章 数据结构基础

2.1 栈与队列

2.2 树

2.2.1 术语

2.2.2 二叉树

2.3 字典

2.3.1 二叉搜索树

2.4 优先队列

2.4.1 堆

2.4.2 堆排序

2.5 集合与不相交集合的并集

2.5.1 导论

2.5.2 求并集及查找操作

2.6 图

2.6.1 导论

2.6.2 定义

2.6.3 图的表示

2.7 参考文献及阅读

第3章 分治策略

3.1 一般方法

3.2 残缺棋盘

3.3 二分搜索

3.4 找最大值和最小值

3.5 合并排序

3.6 快速排序

3.6.1 性能测量

3.6.2 随机排序算法

3.7 选择

3.7.1 最差情况下的最优算法

3.7.2 Select2的实现

3.8 矩阵相乘

3.9 凸包

3.9.1 几种几何基本

3.9.2 QuickHull算法

3.9.3 Graham扫描

3.9.4 O（nlogn）的分治算法

3.10 参考文献及阅读

3.11 附加习题

第4章 贪心法

4.1 一般方法

4.2 集装箱装船

4.3 背包问题

4.4 树节点分裂

4.5 有期限的工作序列化

4.6 最小生成树

4.6.1 Prim算法

4.6.2 Kruskal算法

4.6.3 最优的随机算法（＊）

4.7 磁带最优存储

4.8 最优合并模式

4.9 单源最短路径

4.10 参考文献及阅读

4.11 附加习题

第5章 动态规划

5.1 一般方法

5.2 多段图

5.3 每对顶点间最短路径

5.4 单源最短路径：一般权重

5.5 最优二叉搜索树（＊）

5.6 串编辑

5.7 0/1背包

5.8 可靠性设计

5.9 旅行商问题

5.10 流水车间调度

5.11 参考文献及阅读

5.12 附加习题

第6章 基本遍历及搜索技术

6.1 二叉树的遍历及搜索

6.2 图的遍历及搜索

6.2.1 广度优先搜索及遍历

6.2.2 深度优先搜索及遍历

6.3 连通分支及生成树

6.4 双连通分支

6.5 参考文献及阅读

第7章 回溯

7.1 一般方法

7.2 八皇后问题

7.3 子集求和

7.4 图着色

7.5 哈密尔顿回路

7.6 背包问题

7.7 参考文献及阅读

7.8 附加习题

第8章 分支定界

8.1 方法

8.1.1 最少代价（LC）搜索

8.1.2 15拼图：一个例子

8.1.3 最少代价搜索的控制抽象

8.1.4 定界

8.1.5 FIFO分支定界

8.1.6 LC分支定界

8.2 0/1背包问题

8.2.1 LC分支定界解法

8.2.2 FIFO分支定界解法

8.3 旅行商问题（＊）

8.4 效率

8.5 参考文献及阅读

第9章 代数问题

9.1 一般方法

9.2 求值与插值

9.3 快速傅里叶变换（FFT）

9.3.1 In-place版本的快速傅里叶变换

9.3.2 继续思考

9.4 模算术

9.5 更快的求值和插值

9.6 参考文献及阅读

第10章 下界理论

10.1 比较树

10.1.1 有序搜索

10.1.2 排序

10.1.3 选择

10.2 预言及对手论证

10.2.1 合并

10.2.2 最大和次大

10.2.3 状态空间法

10.2.4 选择

10.3 规约求下界

10.3.1 找凸包

10.3.2 不相交集合问题

10.3.3 在线中位数查找

10.3.4 三角形矩阵相乘

10.3.5 下三角形矩阵求逆

10.3.6 计算传递闭包

10.4 代数问题中的技巧（＊）

10.5 参考文献及阅读

第11章 NP难及NP完全问题

11.1 基本概念

11.1.1 非确定算法

11.1.2 NP难及NP完全

11.2 Cook定理（＊）

11.3 NP难的图问题

11.3.1 团判定问题（CDP）

11.3.2 点覆盖判定问题（NCDP）

11.3.3 色数判定问题（CNDP）

11.3.4 有向图哈密尔顿回路问题（DHC）（＊）

11.3.5 旅行商判定问题（TSP）

11.3.6 AND/OR图判定问题（AOG）

11.4 NP难的调度问题

11.4.1 调度相同处理器

11.4.2 流水车间调度

11.4.3 作业车间调度

11.5 NP难的代码生成问题

11.5.1 有公共子表达式的代码生成

11.5.2 实现并行赋值指令

11.6 简化的NP难问题

11.7 参考文献及阅读

11.8 附加习题

第12章 近似算法

12.1 导论

12.2 绝对近似

12.2.1 平面图着色

12.2.2 最大程序存储问题

12.2.3 NP难的绝对近似

12.3 ε近似

12.3.1 调度独立任务

12.3.2 装箱

12.3.3 NP难的ε近似问题

12.4 多项式时间近似方案

12.4.1 调度独立任务

12.4.2 0/1背包

12.5 完全多项式时间近似方案

12.5.1 舍入

12.5.2 区间划分

12.5.3 间隔

12.6 概率上好的近似方案（＊）

12.7 参考文献及阅读

12.8 附加习题

第13章 PRAM算法

13.1 介绍

13.2 计算模型

13.3 基本技巧和算法

13.3.1 前缀计算

13.3.2 表排列

13.4 选取

13.4.1 使用n2个处理器选取最大元

13.4.2 使用n个处理器选取最大元

13.4.3 整数范围内的最大元

13.4.4 使用n2个处理进行一般性选择

13.4.5 工作最优的随机化选择算法（＊）

13.5 归并

13.5.1 对数时间的算法

13.5.2 奇偶归并

13.5.3 工作最优的算法

13.5.4 一个运行时间为O（log log m）的算法

13.6 排序

13.6.1 奇偶归并排序

13.6.2 一个可供选择的随机化算法

13.6.3 Preparata算法

13.6.4 Reischuk随机化算法（＊）

13.7 图问题

13.7.1 传递闭包的另一种计算方法

13.7.2 全点对的最小路径问题

13.8 凸包计算

13.9 下界

13.9.1 排序的平均运行时间下界

13.9.2 寻找最大元

13.10 参考文献及阅读

13.11 附加习题

第14章 网格算法

14.1 计算模型

14.2 数据包路由

14.2.1 线性数组中的数据包路由

14.2.2 网格上PPR问题的贪心算法

14.2.3 使用小队列的随机化算法

14.3 基本算法

14.3.1 广播

14.3.2 前缀计算

14.3.3 数据聚集

14.3.4 稀疏列举排序

14.4 选取

14.4.1 n=p′情形下的随机化算法（＊）

14.4.2 n>p情形下的随机化算法（＊）

14.4.3 n>p情形下的确定性算法

14.5 归并

14.5.1 通过秩实现线性数组上的归并

14.5.2 线性数组上的奇偶归并

14.5.3 网格上的奇偶归并

14.6 排序

14.6.1 线性数组上的排序

14.6.2 网格上的排序

14.7 图问题

14.7.1 n×n网格上的传递闭包算法

14.7.2 全点对最短路径算法

14.8 凸包计算

14.9 参考文献及阅读

14.10 附加习题

第15章 超立方算法

15.1 计算模型

15.1.1 超立方

15.1.2 蝴蝶网络

15.1.3 其他网络的嵌入

15.2 偏转置路由

15.2.1 贪心算法

15.2.2 随机化算法

15.3 基本算法

15.3.1 广播

15.3.2 前缀计算

15.3.3 数据聚集

15.3.4 稀疏列举排序

15.4 选取

15.4.1 n=p情形下的随机化算法（＊）

15.4.2 n>p情形下的随机化选取算法（＊）

15.4.3 n>p情形下的确定性算法

15.5 归并

15.5.1 奇偶归并

15.5.2 双调归并

15.6 排序

15.6.1 奇偶归并排序

15.6.2 双调排序

15.7 图问题

15.8 凸包计算

15.9 参考文献及阅读

15.10 附加习题