《算法设计与分析》

§1-1 引言1

第一章 绪论1

第二章 数据结构1

§2-1 引言1

§2-2 线性结构2

§2-3 树4

§1-2 算法的描述5

§2-4 图5

习题二5

第三章 算法和计算复杂性5

§3-1 引言5

§1-3 算法的设计与分析6

§3-2 随机存取机（RAM）6

§3-3 RAM程序的计算复杂性7

§3-4 算法描述语言7

习题三8

第四章 递归和生成函数8

§4-1 引言8

§4-2 递归算法的应用和实现8

§4-3 递归问题的非递归算法9

习题一18

§4-4 递归方程（即递推关系）的求解和生成函数100

习题四110

§5-1 引言112

第五章 分治法112

§5-2 二分检索114

§5-3 分治一归并排序119

§5-4 整数乘法和矩阵乘法125

§5-5 选择问题131

习题五136

第六章 排序137

§6-1 引言137

§6-2 n个直观的排序算法139

§6-3 快速排序149

§6-4 堆选排序154

§6-5 基数排序162

习题六169

第七章 动态规划170

§7-1 引言170

§7-2 单源最短路问题171

§7-3 资源分配问题176

§7-4 用动态规划求解的几个问题181

§7-5 货郎担问题184

习题七190

第八章 贪心法193

§8-1 引言193

§8-2 背包问题197

§8-3 最小生成树200

§8-4 单源最短路问题206

习题八211

第九章 回溯法213

§9-1 引言213

§9-2 n后问题225

§9-3 子集和数问题229

§9-4 图的着色问题232

§9-5 哈密顿环问题236

习题九239

第十章 P、NP和NP完全问题241

§10-1 引言241

§10-2 确定型图灵机及P243

§10-3 非确定型图灵机及NP251

§10-4 可满足性问题及Cook定理255

§10-5 若干NP完全问题及NP难题261

§10-6 近似算法273

习题十284

参考文献286