算法导论（第三版）

第一部分 基础知识

第 1 章 算法在计算中的应用

1.1 算法

1.2 作为一种技术的算法

第 2 章 算法基础

2.1 插入排序

2.2 分析算法

2.3 设计算法

2.3.1 分治法

2.3.2 分析分治算法

第 3 章 函数的增长

3.1 渐近记号

3.2 标准记号与常用函数

第4 章 分治策略

4.1 最大子数组问题

4.2 矩阵乘法的 Strassen 算法

4.3 用代入法求解递归式

4.4 用递归树方法求解递归式

4.5 用主方法求解递归式

*4.6 证明主定理

4.6.1 对 b 的幂证明主定理

4.6.2 向下取整和向上取整

第 5 章 概率分析和随机算法

5.1 雇佣问题

5.2 指示器随机变量

5.3 随机算法

*5.4 概率分析和指示器随机变量的进一步使用

5.4.1 生日悖论

5.4.2 球与箱子

5.4.3 特征序列

5.4.4 在线雇佣问题

第二部分 排序和顺序统计量

第 6 章 堆排序

6.1 堆

6.2 维护堆的性质

6.3 建堆

6.4 堆排序算法

6.5 优先队列

第 7 章 快速排序

7.1 快速排序的描述

7.2 快速排序的性能

7.3 快速排序的随机化版本

7.4 快速排序分析

7.4.1 最坏情况分析

7.4.2 期望运行时间

第 8 章 线性时间排序

8.1 排序算法的下界

8.2 计数排序

8.3 基数排序

8.4 桶排序

第 9 章 中位数和顺序统计量

9.1 最小值和最大值

9.2 期望为线性时间的选择算法

9.3 最坏情况为线性时间的选择算法

第三部分 数据结构

第 10 章 基本数据结构

10.1 栈和队列

10.2 链表

10.3 指针和对象的实现

10.4 有根树的表示

第 11 章 散列表

11.1 直接寻址表

11.2 散列表

11.3 散列函数

11.3.1 除法散列法

11.3.2 乘法散列法

*11.3.3 全域散列法

11.4 开放寻址法

11.5 完全散列

第 12 章 二叉搜索树

12.1 什么是二叉树

12.2 查询二叉搜索树

12.3 插入和删除

12.4 随机构建二叉搜索树

第 13 章 红黑树

13.1 红黑树的性质

13.2 旋转

13.3 插入

13.4 删除

第 14 章 数据结构的扩张

14.1 动态顺序统计

14.2 如何扩张数据结构

14.3 区间树

第四部分 高级设计和分析技术

第 15 章 动态规划

15.1 钢条切割

15.2 矩阵链乘法

15.3 动态规划原理

15.4 最长公共子序列

15.5 最优二叉搜索树

第 16 章 贪心算法

16.1 活动选择问题

16.2 贪心算法原理

16.3 赫夫曼编码

*16.4 拟阵和贪心算法

*16.5 用拟阵求解任务调度问题

第 17 章 摊还分析

17.1 聚合分析

17.2 核算法

17.3 势能法

17.4 动态表

17.4.1 表扩张

17.4.2 表扩张和收缩

第五部分 高级数据结构

第 18 章 B 树

18.1 B 树的定义

18.2 B 树上的基本操作

18.3 从 B 树上删除关键字

第 19 章 斐波那契堆

19.1 斐波那契结构

19.2 可合并堆操作

19.3 关键字减值和删除一个结点

19.4 最大度数的界

第 20 章 van Emde Boas 树

20.1 基本方法

20.2 递归结构

20.2.1 原型 van Emde Boas 结构

20.2.2 原型 van Emde Boas 结构上的操作

20.3 van Emde Boas 树及其操作

20.3.1 van Emde Boas 树

20.3.2 van Emde Boas 树的操作

第 21 章 用于不相交集合的数据结构

21.1 不相交集合的操作

21.2 不相交集合的链表表示

21.3 不相交集合森林

*21.4 带路径压缩的按秩合并的分析

第六部分 图算法

第 22 章 基本的图算法

22.1 图的表示

22.2 广度优先搜索

22.3 深度优先搜索

22.4 拓扑排序

22.5 强连通分量

第 23 章 最小生成树

23.1 最小生成树的形成

23.2 Kruskal 算法和 Prim 算法

第 24 章 单源最短路径

24.1 Bellman-Ford 算法

24.2 有向无环图中的单源最短路径问题

24.3 Dijkstra 算法

24.4 差分约束和最短路径

24.5 最短路径性质的证明

第 25 章 所有结点对的最短路径问题

25.1 最短路径和矩阵乘法

25.2 Floyd-Warshall 算法

25.3 用于稀疏图的 Johnson 算法

第 26 章 最大流

26.1 流网络

26.2 Ford-Fulkerson 方法

26.3 最大二分匹配

*26.4 推送-重贴标签算法

*26.5 前置重贴标签算法

第七部分 算法问题选编

第 27 章 多线程算法

27.1 动态多线程基础

27.2 多线程矩阵乘法

27.3 多线程归并排序

第 28 章 矩阵运算

28.1 求解线性方程组

28.2 矩阵求逆

28.3 对称正定矩阵和最小二乘逼近

第 29 章 线性规划

29.1 标准型和松弛型

29.2 将问题表达为线性规划

29.3 单纯形算法

29.4 对偶性

29.5 初始基本可行解

第 30 章 多项式与快速傅里叶变换

30.1 多项式的表示

30.2 DFT 和 FFT

30.3 高效 FFT 实现

第 31 章 数论算法

31.1 基础数论概念

31.2 最大公约数

31.3 模运算

31.4 求解模线性方程

31.5 中国余数定理

31.6 元素的幂

31.7 RSA 公钥加密系统

*31.8 素数的测试

*31.9 整数的因子分解

第 32 章 字符串匹配

32.1 朴素字符串匹配算法

32.2 Rabin-Karp 算法

32.3 利用有限自动机进行字符串匹配

32.4 Knuth-Morris-Pratt 算法

第 33 章 计算几何学

33.1 线段的性质

33.2 确定任意一对线段是否相交

33.3 寻找凸包

33.4 寻找最近点对

第 34 章 NP 完全性

34.1 多项式时间

34.2 多项式时间的验证

34.3 NP 完全性与可归约性

34.4 NP 完全性的证明

34.5 NP 完全问题

34.5.1 团问题

34.5.2 顶点覆盖问题

34.5.3 哈密顿回路问题

34.5.4 旅行商问题

34.5.5 子集和问题

第 35 章 近似算法

35.1 顶点覆盖问题

35.2 旅行商问题

35.2.1 满足三角不等式的旅行商问题

35.2.2 一般旅行商问题

35.3 集合覆盖问题

35.4 随机化和线性规划

35.5 子集和问题

第八部分 附录：数学基础知识

附录 A 求和

A.1 求和公式及其性质

A.2 确定求和时间的界

附录 B 集合等离散数学内容

B.1 集合

B.2 关系

B.3 函数

B.4 图

B.5 树

B.5.1 自由树

B.5.2 有根树和有序树

B.5.3 二叉树和位置树

附录 C 计数与概率

C.1 计数

C.2 概率

C.3 离散随机变量

C.4 几何分布与二项分布

C.5 二项分布的尾部

附录 D 矩阵

D.1 矩阵与矩阵运算

D.2 矩阵的基本性质