算法设计与分析

1 引论
1.1 什么是算法
1.2 分析算法的准则
1.3 描述算法的语言和基本的数据结构
思考题与习题
2 分治与递归
2.1 折半查找
2.2 搜索二叉排序树
2.2.1 二叉排序树的定义
2.2.2 搜索二叉排序树
2.2.3 向二叉排序树中插入新结点
2.2.4 从二叉排序树中删除一个结点
2.2.5 平衡的二叉排序树
2.3 快速排序
2.4 归并排序
2.5 大整数乘法
2.6 矩阵乘积的Strassen算法
思考题与习题
3 贪心算法
3.1 最小生成树
3.2 单源最短路径
3.3 旅行商问题
思考题与习题
4 动态规划
4.1 动态规划在最短路径中的应用
4.2 矩阵连乘积问题
4.3 求最长公共子序列
4.4 凸多边形的最优三角形剖分
4.5 旅行商问题
思考题与习题
5 回溯法
5.1 树的深度优先遍历
5.2 数的全排列
5.3 八皇后问题
5.4 0-1背包问题
5.5 旅行商问题
思考题与习题
6 分支限界法
6.1 最小耗费搜索
6.2 背包问题
6.3 旅行商问题
思考题与习题
7 字符串
7.1 串概念及简单串匹配算法
7.1.1 字符串的概念
7.1.2 串的匹配
7.1.3 简单串模式匹配算法
7.2 Knuth-Morris-Pratt（KMP）算法
7.2.1 KMP算法
7.2.2 改进的KMP算法
7.3 Boyer.Moore算法
7.3.1 Boyer-Moore算法
7.4 Karp-Rabin串匹配随机算法
思考题与习题
8 NP完全问题与近似算法
8.1 确定型图灵机
8.2 非确定型图灵机
8.3 Cook定理和NP完全理论
8.3.1 NP完全理论
8.3.2 Cook定理
8.3.3 若干NP完全问题
8.4 。NP完全问题的近似算法
8.4.1 0-1背包问题
8.4.2 旅行商问题
思考题与习题
9 概率算法
9.1 随机抽样
9.2 判定素数的概率算法
9.2.1 Fermat素数测试法
9.2.2 MiLler-Rabin素数判定概率算法
思考题与习题
10 数据压缩算法
10.1.ASCII码压缩算法
10.2 哈夫曼编码
10.3 字典法
10.4 LZ算法
10.4.1 LZ77算法
10.4.2 LZ78算法
10.4.3 LZW算法
思考题与习题
11 公钥密码学基础
11.1 公钥密码体制的应用与基本思想
11.2 背包公钥密码
11.3 RSA公钥密码体制
10.4 数字签名和Hash算法
思考题与习题
参考文献