第一章 导引与基本数据结构 1
1.1 算法 1
1.2 分析算法 3
1.3 用SPARKS语言写算法 7
1.4 基本数据结构 14
1.4.1 栈和队列 14
1.4.2 树 17
1.4.3 集合的树表示和不相交集合的合并--树结构应用实例 23
1.4.4 图 29
1.5 递归和消去递归 32
习题 36
第二章 分治法 39
2.1 一般方法 39
2.2 二分检索 40
2.3 找最大和最小元素 46
2.4 归并分类 49
2.5 快速分类 55
2.6 选择问题 60
2.7 斯特拉森矩阵乘法 66
习题 68
第三章 贪心方法 71
3.1 一般方法 71
3.2 磁带上的最优存储 72
3.3 背包问题 74
3.4 带有限期的作业排序 77
3.5 最优归并模式 83
3.6 最小生成树 86
3.7 单源最短路径 92
习题 95
第四章 动态规划 99
4.1 一般方法 99
4.2 多段图 101
4.3 每对结点之间的最短路径 104
4.4 最优二分检索树 107
4.5 0/1背包问题 113
4.6 可靠性设计 119
4.7 货郎担问题 121
4.8 流水线调度问题 124
习题 127
第五章 基本检索与周游方法 129
5.1 一般方法 129
5.1.1 二元树周游 129
5.1.2 树周游 138
5.1.3 图的检索和周游 138
5.2 代码最优化 143
5.3 双连通分图和深度优先检索 154
5.4 片/或图 158
5.5 对策树 161
习题 167
第六章 回溯法 172
6.1 一般方法 172
6.2 8-皇后问题 181
6.3 子集和数问题 183
6.4 图的着色 185
6.5 哈密顿环 188
6.6 背包问题 190
习题 193
第七章 分枝-限界法 198
7.1 一般方法 198
7.2 0/1背包问题 211
7.3 货郎担问题 219
习题 224
8.1 基本概念 226
第八章 NP-难度和NP-完全的问题 226
8.2 COOK定量 233
8.3 NP-难度的图问题 239
8.4 NP-难度的调度问题 246
8.5 NP-难度的代码生成问题 249
8.6 若干简化了的NP-难度问题 254
习题 256
参考文献 257