算法设计技巧与分析

第一部分  基本概念和算法导引
第1章  算法分析基本概念
  1.1  引言
  1.2  历史背景
  1.3  二分搜索
  1.4合并两个已排序的表
  1.5  选择排序
  1.6  插入排序
  1.7  自底向上合并排序
  1.8时间复杂性
  1.9空间复杂陛
  1.10最优算法
  1.11如何估计算法运行时间
  1.12最坏情况和平均情况的分析
  1.13平摊分析
  1.14输人大小和问题实例
  1.15练习
  1.16参考注释
第2章  数学预备知识
  2.1  集合、关系和函数
  2.2  证明方法
  2.3  对数
  2.4底函数和顶函数
  2.5  阶乘和二项式系数
  2.6  鸽巢原理
  2.7  和式
  2.8  递推关系
  2.9  练习
第3章数据结构
  3.1  引言
  3.2  链表
  3.3  图
3.4  树
  3.5  根树
  3.6  二叉树
  3.7  练习
  3.8  参考注释
第4章  堆和不相交集数据结构
  4.1  引言
  4.2  堆
  4.3不相交集数据结构
  4.4  练习
  4.5  参考注释
第二部分  基于递归的技术
第5章归纳法
  5.1  引言
  5.2两个简单的例子
  5.3  基数排序
  5.4  整数幂
  5.5  多项式求值(Homer规则)
  5.6  生成排列
  5.7寻找多数元素
  5.8  练习
  5.9  参考注释
第6章  分治
  6.1  引言
  6.2  二分搜索
  6.3  合并排序
  6.4  分治范式
  6.5  寻找中项和第K小元素
  6.6  快速排序
  6.7大整数乘法
  6.8  矩阵乘法
  6.9最近点对问题
  6.10练习
  6.11参考注释
第7章动态规划
  7.1  引言
  7.2最长公共子序列问题
  7.3矩阵链相乘
    7.4动态规划范式
  7.5  所有点对的最短路径问题
  7。6  背包问题
  7.7  练习
  7.8  参考注释
第三部分  最先割技术
第8章贪心算法
  8.1  引言
  8.2最短路径问题
  8.3  最小耗费生成树(Kmskal算法)
  8.4最小耗费生成树(Prim算法)
  8.5  文件压缩
  8.6  练习  
  8.7  参考注释
第9章  图的遍历
  9.1  引言
  9.2深度优先搜索
  9.3  深度优先搜索的应用
  9.4广度优先搜索
  9.5  广度优先搜索的应用
  9.6  练习
  9.7  参考注释
第四部分  问题的复杂性
第10章  NP完全问题
  10.1  引言
  10.2  P类
  10.3  NP类  
  10.4  NP完全问题  
  10.5  co-NP类
  10.6 NH类
  10.7  四种类之间的关系
  10.8  练习
  10.9  参考注释
第11章  计算复杂性引论
  11.1  引言
  11.2计算模型：图灵机
  11.3  K带图灵机和时间复杂性
  11.4  离线图灵机和空间复杂性
  11.5  带压缩和线性增速
  11.6  复杂性类之间的关系
  11.7  归约
  11.8  完全性
  11.9  多项式时间层次
  11.10练习
  11.11参考注释
第12章  下界
  12.1  引言
  12.2  平凡下界
  12.3决策树模型
  12.4代数决策树模型
  12.5线性时间归约
  12.6  练习
  12.7参考注释
第五部分  克服困难性
第13章  回溯法
  13.1  引言
  13.2  3着色问题
  13.3  8皇后问题
  13.4一般回溯方法
  13.5分支限界法
  13.6  练习
  13.7  参考注释
第14章  随机算法
  14.1  引言
  14.2  LasVegas和MonteCarlo算法
  14.3  随机化快速排序
  14.4随机化的选择算法
  14.5  测试串的相等性
  14.6  模式匹配
  14.7  随机取样
  14.8素数性测试 
  14.9练习      
  14.10参考注释
   15章  近似算法
  15.1  引言
  15.2  基本定义
  15.3  差界
  15.4相对性能界
  15.5  多项式近似方案
  15.6完全多项式近似方案
  15.7  练习
  15.8  参考注释
第六部分  域指定问题的迭代改进
第16章  网络流
  16.1  引言
  16.2  预备知识
  16.3 Ford-Fulkerson方法
  16.4最大容量增值
  16.5最短路径增值
  16.6  Dinic算法  
  16.7  MPM算法
  16.8  练习
  16.9  参考注释
第17章  匹配
  17.1  引言
  17.2  预备知识
  17.3  网络流方法
  17.4  二分图的匈牙利树方法
  17.5  一般图中的最大匹配
  17.6  二分图的O(n的2.5次方)算法
  17.7  练习
  17.8  参考注释
第七部分  计算几何技术
第18章  几何扫描
  18.1  引言
  18.2几何预备知识
  18.3计算线段的交点
  18.4  凸包问题
  18.5计算点集的直径
  18.6  练习
  18.7  参考注释
第19章  Voronoi图解
  19.1  引言
  19.2最近点Voronoi图解
  19.3 Vomnoi图解的应用
  19.4最远点Voronoi图解
  19.5  最远点Voronoi图解的应用  
  19.6  练习
  19.7  参考注释
参考文献