计算机算法

第1章  导论
  1.1  什么是算法
  1.2  算法规范
      1.2.1  引言
      1.2.2  递归算法
  1.3  性能分析
      1.3.1  空间复杂度
      1.3.2  时间复杂度
      1.3.3  渐近符号 （O、 Ω、 Θ）
      1.3.4  实际复杂度
      1.3.5  性能度量
  1.4  随机算法
      1.4.1  概率论基础
      1.4.2  随机算法： 非形式化的描述
      1.4.3  识别重复元素
      1.4.4  素数测试
      1.4.5  优点与缺点
  1.5  参考文献和读物
第2章  基本数据结构 
  2.1  栈和队列
  2.2  树
      2.2.1  术语
      2.2.2  二叉树
  2.3  字典
      2.3.1  二叉查找树
      2.3.2  代价分摊
  2.4  优先队列
      2.4.1  堆
      2.4.2  堆排序
  2.5  集合和不相交集合的并
      2.5.1  概述
      2.5.2  并和查找操作
  2.6  图
      2.6.1  概述
      2.6.2  定义
      2.6.3  图的表示方法
  2.7  参考文献和读物
第3章  分治算法
  3.1  一般方法
  3.2  二叉查找
  3.3  查找最大值和最小值
  3.4  归并排序
  3.5  快速排序
      3.5.1  性能度量
      3.5.2  随机排序算法
  3.6  选择
      3.6.1  最坏情况下的最优算法
      3.6.2  Select2的实现
  3.7  Strassen矩阵乘法
  3.8  凸包
      3.8.1  几种原始几何方法
      3.8.2  QuickHull算法
      3.8.3  Graham扫描算法
      3.8.4  一个O(nlogn)的分治算法
  3.9  参考文献和读物
  3.10  附加习题
第4章  贪心算法
  4.1  一般方法
  4.2  背包问题
  4.3  树节点分割
  4.4  带有期限的作业顺序问题
  4.5  最小代价生成树
      4.5.1  Prim算法
      4.5.2  Kruskal算法
      4.5.3  一个最优随机算法（*）
  4.6  磁带的最优存储
  4.7  最优归并模式
  4.8  单源最短路径
  4.9  参考文献和读物
  4.10  附加习题
第5章  动态规划
  5.1  一般方法
  5.2  多部图
  5.3  每一对顶点之间的最短路径
  5.4  单源最短路径： 普通权值
  5.5  最优二叉查找树(*)
  5.6  串编辑
  5.7  0/1背包
  5.8  可靠性设计
  5.9  旅行商问题
  5.10  流水作业调度
  5.11  参考文献和读物
  5.12  附加习题
第6章  基本的查找和遍历技术
  6.1  二叉树算法
  6.2  图算法
      6.2.1  广度优先搜索和遍历
      6.2.2  深度优先搜索和遍历
  6.3  连通分支和生成树
  6.4  双连通分支和DFS算法
  6.5  参考文献和读物
第7章  回溯
  7.1  一般方法
  7.2  8皇后问题
  7.3  子集求和问题
  7.4  图的着色
  7.5  哈密顿回路
  7.6  背包问题
  7.7  参考文献和读物
  7.8  附加习题
第8章  分支限界法
  8.1  一般方法
      8.1.1  最小代价查找
      8.1.2  15拼板： 一个例子
      8.1.3  LC查找的控制抽象
      8.1.4  限界
      8.1.5  FIFO分支限界法
      8.1.6  LC分支限界法
  8.2  0/1背包问题
      8.2.1  LC分支限界法求解
      8.2.2  FIFO分支限界法求解
  8.3  旅行商问题(*)
  8.4  效率因素
  8.5  参考文献和读物
第9章  代数问题
  9.1  一般方法
  9.2  计算和插值
  9.3  快速傅里叶变换
      9.3.1  FFT的原地版本
      9.3.2  一些保留问题
  9.4  模运算
  9.5  更快的计算和插值
  9.6  参考文献和读物
第10章  下界理论
  10.1  比较树
      10.1.1  有序查找
      10.1.2  排序
      10.1.3  选择
  10.2  喻示和对立论
      10.2.1  归并
      10.2.2  最大和次大
      10.2.3  状态空间方法
      10.2.4  选择
  10.3  通过规约求下界
      10.3.1  寻找凸包
      10.3.2  不相交集合问题
      10.3.3  即时中值查找
      10.3.4  三角矩阵相乘
      10.3.5  下三角矩阵求逆
      10.3.6  计算传递闭包
  10.4  解决代数问题的技术(*)
  10.5  参考文献和读物
第11章  难与完全问题
  11.1  基本概念
      11.1.1  非确定性算法
      11.1.2  难和完全类
  11.2  Cook定理（*）
  11.3  难的图问题
      11.3.1  团判定问题
      11.3.2  节点覆盖判定问题
      11.3.3  色数判定问题
      11.3.4  有向哈密顿回路（*）
      11.3.5  旅行商判定问题
      11.3.6  与/或图判定问题
  11.4  难的调度问题
      11.4.1  调度相同的处理器
      11.4.2  流水作业调度
      11.4.3  作业安排调度
  11.5  难的代码生成问题
      11.5.1  带有公共子表达式的代码生成
      11.5.2  实现并行赋值指令
  11.6  一些简化的难问题
  11.7  参考文献和读物
  11.8  附加习题
第12章  近似算法
  12.1  概述
  12.2  绝对近似
      12.2.1  平面图着色
      12.2.2  最多程序存储问题
      12.2.3  难的绝对近似
  12.3  ε近似
      12.3.1  独立任务的调度
      12.3.2  装箱问题
      12.3.3  难的ε近似问题
  12.4  多项式时间近似方案
      12.4.1  独立任务的调度
      12.4.2  0/1背包
  12.5  完全多项式时间近似方案
      12.5.1  舍入法
      12.5.2  区间划分法
      12.5.3  分割法
  12.6  概率上的好算法(*)
  12.7  参考文献和读物
  12.8  附加习题
第13章  PRAM算法
  13.1  概述
  13.2  计算模型
  13.3  基本技术和算法
      13.3.1  前缀计算
      13.3.2  表排序
  13.4  选择
      13.4.1  使用n2个处理器选择最大值
      13.4.2  使用n个处理器选择最大值
      13.4.3  在整数中选择最大值
      13.4.4  使用n2个处理器的一般选择问题
      13.4.5  一个工作最优的随机算法(*)
  13.5  归并
      13.5.1  对数时间算法
      13.5.2  奇偶归并
      13.5.3  工作最优的算法
      13.5.4  O(log logm)时间算法
  13.6  排序
      13.6.1  奇偶归并排序
      13.6.2  随机选择算法
      13.6.3  Preparata算法
      13.6.4  Reischuk随机算法（*）
  13.7  图问题
      13.7.1  计算传递闭包的另一种算法
      13.7.2  每一对顶点之间的最短路径
  13.8  计算凸包
  13.9  下界
      13.9.1  平均情况下排序的下界
      13.9.2  寻找最大值
  13.10  参考文献和读物
  13.11  附加习题
第14章  网格算法
  14.1  计算模型
  14.2  分组路由
      14.2.1  线性阵列中的分组路由
      14.2.2  网格上PPR的贪心算法
      14.2.3  具有小队列的随机算法
  14.3  基本算法
      14.3.1  广播
      14.3.2  前缀计算
      14.3.3  数据集中
      14.3.4  稀疏枚举排序
  14.4  选择
      14.4.1  n=p(*)时的随机算法
      14.4.2  n＞p(*)时的随机选择
      14.4.3  n＞p时的确定性算法
  14.5  归并
      14.5.1  在线性阵列上的顺序号归并
      14.5.2  线性阵列上的奇偶归并
      14.5.3  在网格上的奇偶归并
  14.6  排序
      14.6.1  在线性阵列上的排序
      14.6.2  在网格上的排序
  14.7  图问题
      14.7.1  传递闭包的n×n网格算法
      14.7.2  每一对顶点之间的最短路径
  14.8  计算凸包
  14.9  参考文献和读物
  14.10  附加习题
第15章  超立方体算法
  15.1  计算模型
      15.1.1  超立方体
      15.1.2  蝶形网络
      15.1.3  其他网络的嵌入
  15.2  PPR路由
      15.2.1  贪心算法
      15.2.2  随机算法
  15.3  基本算法
      15.3.1  广播
      15.3.2  前缀计算
      15.3.3  数据集中
      15.3.4  稀疏枚举排序
  15.4  选择
      15.4.1  n=p(*)时的随机算法
      15.4.2  n＞p(*)时的随机选择
      15.4.3  n＞p时的确定性算法
  15.5  归并
      15.5.1  奇偶归并
      15.5.2  双调谐归并
  15.6  排序
      15.6.1  奇偶归并排序
      15.6.2  双调谐排序
  15.7  图问题
  15.8  计算凸包
  15.9  参考文献和读物
  15.10  附加习题
索引