本书是国际算法大师乌迪·曼博（Udi Manber）博士撰写的一本享有盛誉的著作，强调了算法设计的创造性方面，通过算法开发步骤来描述算法设计过程。此外，本书创造性地将算法设计过程同定理归纳证明过程进行类比，揭示了算法设计的基本思想和本质，旨在提高读者的问题求解以及理解算法设计的过程和思想的能力。

本书是国际算法大师乌迪·曼博（Udi Manber）博士撰写的一本享有盛誉的著作。全书共分12章：第1章到第4章为介绍性内容，涉及数学归纳法、算法分析、数据结构等内容；第5章提出了与归纳证明进行类比的算法设计思想；第6章到第9章分别给出了4个领域的算法，如序列和集合的算法、图算法、几何算法、代数和数值算法；第10章涉及归约，也是第11章的序幕，而后者涉及NP完全问题；第12章则介绍了并行算法；最后是部分习题的答案及参考文献。本书的特色有二，旨在提高读者的问题求解能力，使读者能够理解算法设计的过程和思想：一是强调算法设计的创造性过程，注重算法设计背后的创造性思想，而不拘泥于某个具体算法的详细讨论；二是将算法设计类比于定理归纳证明，揭示了算法设计的基本思想和本质。

本书的组织结构清晰且易于理解，强调了创造性，具有浓郁特色，时至今日仍有其巨大的价值，并且适合作为计算机及相关专业算法和高级算法课程的教材。

第1章 引论/1

第2章 数学归纳法/6

 2.1 引言/6

 2.2 三个简单的例子/7

 2.3 平面内区域的计数/8

 2.4 简单的着色问题/10

 2.5 复杂一些的加法题/10

 2.6 一个简单的不等式/11

 2.7 欧拉公式/12

 2.8 图论中的一个问题/13

 2.9 格雷码/14

 2.10 在图上寻找无重边的路/16

 2.11 数学平均数和几何平均数定理/17

 2.12 循环不变量：将十进制数转换为二进制数/19

 2.13 常见的错误/20

 2.14 小结/21

第3章 算法分析/27

 3.1 引言/27

 3.2 符号O/28

 3.3 时间与空间复杂度/30

 3.4 求和/31

 3.5 递推关系/33

3.5.1 巧妙地猜测/34

3.5.2 分治关系/36

3.5.3 涉及全部历史的递推关系/37

 3.6 一些有用的证明论据/39

 3.7 小结/40

第4章 数据结构简介/44

 4.1 引言/44

 4.2 基本数据结构/44

4.2.1 元素/44

4.2.2 数组/45

4.2.3 记录/45

4.2.4 链表/46

 4.3 树/47

4.3.1 树的表示/48

4.3.2 堆/49

4.3.3 二叉搜索树/51

4.3.4 AVL树/54

 4.4 散列/56

 4.5 合并?查找问题/58

 4.6 图/60

 4.7 小结/61

第5章 基于归纳的算法设计/66

 5.1 引言/66

 5.2 多项式求值/66

 5.3 最大导出子图/68

 5.4 寻找一对一映射/69

 5.5 社会名流问题/71

 5.6 分治算法：轮廓问题/73

 5.7 在二叉树中计算平衡因子/75

 5.8 寻找最大连续子序列/76

 5.9 增强归纳假设/77

 5.10 动态规划：背包问题/77

 5.11 常见的错误/80

 5.12 小结/80

第6章 序列和集合的算法/85

 6.1 引言/85

 6.2 二叉搜索的几种形式/85

6.2.1 纯二叉搜索/85

6.2.2 循环序列的二叉搜索/86

6.2.3 二叉搜索特殊下标/86

6.2.4 二叉搜索长度未知的序列/88

6.2.5 重叠子序列问题/88

6.2.6 解方程/89

 6.3 内插搜索/89

 6.4 排序/90

6.4.1 桶排序和基数排序/90

6.4.2 插入排序和选择排序/92

6.4.3 归并排序/93

6.4.4 快速排序/93

6.4.5 堆排序/98

6.4.6 排序问题的下界/100

 6.5 顺序统计/102

6.5.1 最大数和最小数/102

6.5.2 查找第k小的数/102

 6.6 数据压缩/103

 6.7 串匹配/105

 6.8 序列比较/110

 6.9 概率算法/112

6.9.1 随机数/113

6.9.2 着色问题/114

6.9.3 将拉斯维加斯算法变换成确定性算法/114

 6.10 查找众数/116

 6.11 三个展现有趣证明方法的问题/118

6.11.1 最长递增序列/118

6.11.2 查找集合中两个最大的元素/119

6.11.3 计算多重集合的模/121

 6.12 小结/122

第7章 图算法/130

 7.1 引言/130

 7.2 欧拉图/131

 7.3 图的遍历/133

7.3.1 深度优先搜索/133

7.3.2 广度优先搜索/139

 7.4 拓扑排序/140

 7.5 单源最短路径/142

 7.6 最小代价生成树/146

 7.7 全部最短路径/150

 7.8 传递闭包/151

 7.9 图的分解/153

7.9.1 双连通分支/153

7.9.2 强连通分支/159

7.9.3 利用图分解的例子/164

 7.10 匹配/166

7.10.1 非常稠密图中的完美匹配/166

7.10.2 偶图匹配/167

 7.11 网络流量/169

 7.12 哈密尔顿旅行/173

7.12.1 反向归纳/173

7.12.2 在非常稠密图中找哈密尔顿回路/173

 7.13 小结/174

第8章 几何算法/188

 8.1 引言/188

 8.2 判定点是否在多边形内部/189

 8.3 构造简单多边形/191

 8.4 凸包/193

8.4.1 直接方法/193

8.4.2 礼品包裹算法/194

8.4.3 Graham扫描算法/195

 8.5 最近点对/197

 8.6 水平线段和竖直线段的交点/200

 8.7 小结/203

第9章 代数和数值算法/207

 9.1 引言/207

 9.2 求幂运算/207

 9.3 欧几里得算法/210

 9.4 多项式乘法/211

 9.5 矩阵乘法/212

9.5.1 Winograd算法/212

9.5.2 Strassen算法/213

9.5.3 布尔矩阵/215

 9.6 快速傅里叶变换/218

 9.7 小结/224

第10章 归约/228

 10.1 引言/228

 10.2 归约的例子/229

10.2.1 简单字符串匹配问题/229

10.2.2 特殊代表集/229

10.2.3 关于序列比较的归约/230

10.2.4 在无向图中寻找三角形/231

 10.3 有关线性规划的归约/232

10.3.1 概述与定义/232

10.3.2 归约到线性规划的例子/233

 10.4 下界的归约/235

10.4.1 寻找简单多边形算法复杂度的下界/235

10.4.2 关于矩阵的简单归约/236

 10.5 常见的错误/237

 10.6 小结/238

第11章 NP完全问题/242

 11.1 引言/242

 11.2 多项式时间归约/242

 11.3 非确定性和Cook定理/244

 11.4 NP完全性的证明例子/246

11.4.1 顶点覆盖问题/246

11.4.2 支配集问题/247

11.4.3 3SAT问题/248

11.4.4 团问题/249

11.4.5 3着色问题/250

11.4.6 一般经验/251

11.4.7 更多的NP完全问题/252

 11.5 处理NP完全问题的技术/253

11.5.1 回溯法和分枝限界法/254

11.5.2 确保性能的近似算法/257

 11.6 小结/261

第12章 并行算法/266

 12.1 引言/266

 12.2 并行计算模型/267

 12.3 共享存储器算法/268

12.3.1 并行加/268

12.3.2 寻找最大数的算法/269

12.3.3 并行前缀问题/271

12.3.4 在链表中查寻秩/273

12.3.5 欧拉遍历技术/274

 12.4 互连网络上的算法/275

12.4.1 阵列上的排序/276

12.4.2 排序网络/279

12.4.3 在树中查找第k个最小元素/280

12.4.4 网孔上的矩阵乘法/283

12.4.5 超立方体中的路由/284

 12.5 脉动计算/286

12.5.1 矩阵与向量相乘/286

12.5.2 卷积问题/287

12.5.3 序列的比较/288

 12.6 小结/290

参考文献/317