本书系统地介绍了算法设计与分析的基本内容,并对讨论的算法进行了详尽分析。全书共8章,内容包括算法基础、基本算法设计和分析技术(分治法、动态规划、贪心法、回溯法和分枝限界法)、图算法以及NP完全性理论。书中以类**程序设计语言对算法所作的简明描述,使得稍微具有程序设计语言知识的人即可读懂。此外,书中以大量图例说明每个算法的工作过程,使得算法更加易于理解和掌握。
本书可作为高等院校与计算机相关的各专业“算法设计”课程的教材,也可作为计算机领域的相关科研人员的参考书。此外,本书还可供参加ACM程序设计大赛的算法爱好者参考。

第1章 算法基础
1.1 算法 ?
1.1.1 冒泡排序 ?
1.1.2 循环不变式和冒泡排序算法的正确性 ?
1.1.3 伪代码使用约定
1.2 算法分析 ?
1.2.1 冒泡排序算法分析 ?
1.2.2 *坏情况和平均情况分析 ?
1.2.3 增长的数量级
1.3 算法的运行时间 ?
1.3.1 函数增长 ?
1.3.2 渐近表示
习题 第2章 分治法
2.1 递归与递归方程 ?
2.1.1 递归的概念 ?
2.1.2 替换方法 ?
2.1.3 递归树方法 ?
2.1.4 主方法
2.2 分治法 ?
2.2.1 分治法的基本思想 ?
2.2.2 二叉查找算法
2.3 分治法应用实例 ?
2.3.1 找*大值与*小值 ?
2.3.2 Strassen矩阵乘法 ?
2.3.3 整数相乘 ?
2.3.4 归并排序 ?
2.3.5 快速排序 ?
2.3.6 线性时间选择 ?
2.3.7 *近点对问题
习题 第3章 动态规划
3.1 用表代替递归
3.2 -1背包问题
3.3 矩阵链乘问题
3.4 动态规划的基本元素
3.5 备忘录方法
3.6 装配线调度问题
3.7 *长公共子序列
3.8 *优二分检索树
3.9 凸多边形*优三角剖分
习题 第4章 贪心法
4.1 背包问题
4.2 活动选择问题
4.3 贪心算法的基本元素
4.4 哈夫曼编码
4.5 *小生成树算法 ?
4.5.1 *小生成树的基本原理 ?
4.5.2 Kruskal算法 ?
4.5.3 Prim算法 ?
4.5.4 Boruvka算法 ?
4.5.5 比较与改进
4.6 贪心算法的理论基础
4.7 作业调度问题
习题 第5章 回溯法
5.1 回溯法的基本原理
5.2 n-皇后问题
5.3 子集和数问题
5.4 -1背包问题
5.5 着色问题
习题 第6章 分枝限界法
6.1 分枝限界法的基本思想
6.2 -1背包问题
6.3 作业调度问题
习题 第7章 图算法
7.1 图的表示
7.2 广度优先搜索
7.3 Dijkstra算法
7.4 Bellman Ford算法
7.5 Floyd Warshall算法
习题 第8章 NP完全性
8.1 P类问题和NP类问题 ?
8.1.1 复杂类P和复杂类NP ?
8.1.2 NP中的有趣问题
8.2 NP完全性 ?
8.2.1 多项式时间归约和NP难度 ?
8.2.2 Cook定理
8.3 典型的NP完全问题 ?
8.3.1 CNF?3SAT问题和3SAT问题 ?
8.3.2 顶点覆盖问题 ?
8.3.3 团问题和集合覆盖问题 ?
8.3.4 子集和数问题与背包问题 ?
8.3.5 哈密尔顿回路问题和TSP问题
习题 附录A 习题选解
附录B 索引
参考文献