A、《算法四版》

1、排序

1.1 初级排序

  • 1.1.1 选择排序
  • 1.1.2 插入排序
  • 1.1.3 希尔排序

1.2 归并排序

  • 1.2.1 原地归并
  • 1.2.2 自顶向下
  • 1.2.3 自底向上

1.3 快速排序

  • 1.3.1 基本算法
  • 1.3.2 算法改进

1.4 优先队列

  • 1.4.1 初级实现
  • 1.4.2 堆排序

1.5 应用

  • 1.5.1 对各种数据进行排序
  • 1.5.2 我应该使用哪种排序算法

2、查找

2.1 符号表

  • 2.1.1 有序符号表
  • 2.1.2 无序链表之顺序查找
  • 2.1.3 有序数组之二分查找

2.2 二叉查找树

2.3 平衡查找树

  • 2.3.1 2-3查找树
  • 2.3.2 红黑二叉查找树
  • 2.3.3 红黑树

2.4 散列表

  • 2.4.1 散列函数
  • 2.4.2 拉链法散列表
  • 2.4.2 线性探测法散列表

2.5 应用

  • 2.5.1 我应该使用符号表的哪种实现
  • 2.5.2 集合的API
  • 2.5.3 字典类用例
  • 2.5.4 索引类用例
  • 2.5.5 稀疏向量

3、图

3.1 无向图

  • 3.1.1 深度优先搜索
  • 3.1.2 寻找路径
  • 3.1.3 广度优先搜索
  • 3.1.4 符号图

3.2 有向图

  • 3.2.1 环和有向无环图

3.3 最小生成树

  • 3.3.1 加权无向图
  • 3.3.2 最小生成树的API和测试用例
  • 3.3.3 Prim
  • 3.3.4 Kruskal

3.4 最短路径

  • 3.4.1 加权有向图
  • 3.4.2 Dijkstra
  • 3.4.3 无环加权有向图
  • 3.4.4 一般加权有向图

4、字符串

  • 4.1 字符串排序
  • 4.1.1 键索引计数法
  • 4.1.2 低位优先的字符串排序
  • 4.1.3 高位优先的字符串排序
  • 4.1.4 三向字符串快速排序
  • 4.1.5 字符串排序算法的选择

4.2 单词查找树

  • 4.2.1 单词查找树
  • 4.2.2 三向单词查找树

4.3 子字符串查找

  • 4.3.1 暴力子字符串查找算法
  • 4.3.2 Knuth-Morris-Pratt子字符串查找算法
  • 4.3.3 Boyer-Moore字符串查找算法
  • 4.3.4 Rabin-Karp指纹字符串查找算法

4.4 正则表达式

  • 4.4.1 非确定有限状态自动机
  • 4.4.2 模拟NFA的运行

4.5 数据压缩

  • 4.5.1 读写二进制数据
  • 4.5.2 局限
  • 4.5.3 热身运动:基因组
  • 4.5.4 游程编码
  • 4.5.5 霍夫曼压缩

B、《算法导论》

1、 基础(Foundations)

  • 01 计算中算法的角色(The Role of Algorithms in Computing)
  • 02 开始(Getting Started)
  • 03 函数的增长率(Growth of Functions)
  • 04 递归(Recurrences)
  • 05 概率分析与随机化算法(Probabilistic Analysis and Randomized Algorithms)

2、 排序与顺序统计(Sorting and Order Statistics)

  • 06 堆排序(Heapsort)
  • 07 快速排序(Quicksort)
  • 08 线性时间中的排序(Sorting in Linear Time)
  • 09 中值与顺序统计(Medians and Order Statistics)

3、 数据结构(Data Structures)

  • 10 基本的数据结构(Elementary Data Structures)
  • 11 散列表(Hash Tables)
  • 12 二叉查找树(Binary Search Trees)
  • 13 红-黑树(Red-Black Trees)
  • 14 扩充的数据结构(Augmenting Data Structures)

4、 高级的设计与分析技术(Advanced Design and Analysis Techniques)

  • 15 动态规划(Dynamic Programming)
  • 16 贪婪算法(Greedy Algorithms)
  • 17 分摊分析(Amortized Analysis)

5、 高级的数据结构(Advanced Data Structures)

  • 18 B-树(B-Trees)
  • 19 二项式堆(Binomial Heaps)
  • 20 斐波纳契堆(Fibonacci Heaps)
  • 21 不相交集的数据结构(Data Structures for Disjoint Sets)

6、 图算法(Graph Algorithms)

  • 22 基本的图算法(Elementary Graph Algorithms)
  • 23 最小生成树(Minimum Spanning Trees)
  • 24 单源最短路径(Single-Source Shortest Paths)
  • 25 全对的最短路径(All-Pairs Shortest Paths)
  • 26 最大流(Maximum Flow)

7、 精选的主题(Selected Topics)

  • 27 排序网络(Sorting Networks)
  • 28 矩阵运算(Matrix Operations)
  • 29 线性规划(Linear Programming)
  • 30 多项式与快速傅里叶变换(Polynomials and the FFT)
  • 31 数论算法(Number-Theoretic Algorithms)
  • 32 字符串匹配(String Matching)
  • 33 计算几何学(Computational Geometry)
  • 34 NP-完备性(NP-Completeness)
  • 35 近似算法(Approximation Algorithms)

8、 附录:数学背景(Mathematical Background)

  • 附录A 求和(Summations)
    • A.1 求和公式及其性质
    • A.2 确定求和时间的界
    • 思考题
    • 附录注记
  • 附录B 集合等离散数学内容。(Sets, Etc.)
    • B.1 集合
    • B.2 关系
    • B.3 函数
    • B.4 图
    • B.5 树
    • B.5.1 自由树
    • B.5.2 有根树和有序树
    • B.5.3 二叉树和位置树
    • 思考题
    • 附录注记
  • 附录C 计数与概率(Counting and Probability)
    • C.1 计数
    • C.2 概率
    • C.3 离散随机变量
    • C.4 几何分布与二项分布
    • *C.5 二项分布的尾部
    • 思考题
    • 附录注记
  • 附录D 矩阵
    • D.1 矩阵与矩阵运算
    • D.2 矩阵基本性质
    • 思考题
    • 附录注记
  • 参考文献

C、《计算机程序设计艺术》

第1卷 基本算法(Vol 1: Fundamental Algorithms)

1.1 基本概念(Chapter 1: Basic Concepts)

1.1.1 算法(Algorithms)

1.1.2 数学准备(Mathematical Preliminaries )

  • 1.1.2.01 数学归纳法
  • 1.1.2.02 数、幂和对数
  • 1.1.2.03 和与积
  • 1.1.2.04 整数函数和初等函数
  • 1.1.2.05 排列和阶乘
  • 1.1.2.06 二项式系数
  • 1.1.2.07 调和数
  • 1.1.2.08 斐波那契数
  • 1.1.2.09 生成函数
  • 1.1.2.10 典型算法分析
  • 1.1.2.11 渐进表示

    • 1.1.2.11.1大O记号
    • 1.1.2.11.2欧拉求和公式
    • 1.1.2.11.3若干渐近计算式

      1.1.3 MIX

  • 1.1.3.1 MIX的描述

  • 1.1.3.2 MIX汇编语言

  • 1.1.3.3 排列的应用

1.1.4 若干基本程序设计技术(Some Fundamental Programming Techniques )

  • 1.1.4.1 子程序
  • 1.1.4.2 协同程序
  • 1.1.4.3 解释程序
  • 1.1.4.4 输入与输出
  • 1.1.4.5 历史和参考文献

1.2 信息结构(Chapter 2: Information Structures)

1.2.1 引论(Introduction)

1.2.2 线性表(Linear Lists )

  • 1.2.2.1 栈、队列和双端队列
  • 1.2.2.2 顺序分配
  • 1.2.2.3 链接分配
  • 1.2.2.4 循环链表
  • 1.2.2.5 双链表
  • 1.2.2.6 数组与正交表

1.2.3 树(Trees)

  • 1.2.3.1 遍历二叉树
  • 1.2.3.2 树的二叉树表示
  • 1.2.3.3 树的其他表示
  • 1.2.3.4 树的基本数学性质
    • 1.2.3.4.1 自由树 
    • 1.2.3.4.2 定向树
    • 1.2.3.4.3 无限性引理
    • 1.2.3.4.4 树的枚举
    • 1.2.3.4.5 路径长度
    • 1.2.3.4.6 历史和参考文献

2.4 多链结构

2.5 动态存储分配

2.6 历史和参考文献

习题答案

附录A数值表

附录B记号索引

附录C算法和定理索引

人名索引

索引

第2卷 半数值算法(Vol 2: Seminumerial Algorithms)

第3章 随机数(Chapter 3: Random Numbers)

  • 3.1. 引言(Introduction)
  • 3.2. 生成均匀的随机数(Generating Uniform Random Numbers)
    • 3.2.1. 线性同余法(The Linear Congruential Method)
    • 3.2.1.1. 模的选择(Choice of modulus)
    • 3.2.1.2. 乘数的选择(Choice of multiplier)
    • 3.2.1.3. 势(Potency)
    • 3.2.2. 其他方法(Other Methods)
  • 3.3. 统计检验(Statistical Tests)
    • 3.3.1. 研究随机数据的一般检验过程(General Test Procedures for Studying Random Data)
    • 3.3.2. 经验检验(Empirical Tests)
    • *3.3.3. 理论检验(Theoretical Tests)
    • 3.3.4. 谱检验(The Spectral Test)
  • 3.4. Other 其他类型的随机量(Types of Random Quantities)
    • 3.4.1. 数值分布(Numerical Distributions)
    • 3.4.2. 随机抽样和洗牌(Random Sampling and Shuffling)
  • *3.5. 什么是随机序列?(What Is a Random Sequence?)

第4章 算术(Chapter 4: Arithmetic)

  • 4.1. 按位记数系统(Positional Number Systems)
  • 4.2. 浮点算术(Floating Point Arithmetic)
    • 4.2.1. 单精度计算(Single-Precision Calculations)
    • 4.2.2. 浮点算术的精度(Accuracy of Floating Point Arithmetic)
    • *4.2.3. 双精度计算(Double-Precision Calculations)
    • 4.2.4. 浮点数的分布(Distribution of Floating Point Numbers)
  • 4.3. 多精度算术(Multiple Precision Arithmetic)
    • 4.3.1. 经典算法(The Classical Algorithms)
    • *4.3.2. 模算术(Modular Arithmetic)
    • *4.3.3. 乘法有多快?(How Fast Can We Multiply?)
  • 4.4. 进制转换(Radix Conversion)
  • 4.5. 有理数算术(Rational Arithmetic)
    • 4.5.1. 分数(Fractions)
    • 4.5.2. 最大公因数(The Greatest Common Divisor)
    • *4.5.3. 对欧几里得算法的分析(Analysis of Euclid’s Algorithm)
    • 4.5.4. 分解素因数(Factoring into Primes)
  • 4.6. 多项式算术(Polynomial Arithmetic)
    • 4.6.1. 多项式除法(Division of Polynomials)
    • *4.6.2. 多项式的因子分解(Factorization of Polynomials)
    • 4.6.3. 幂的计算(Evaluation of Powers)
    • 4.6.4. 多项式求值(Evaluation of Polynomials)
  • *4.7. 对幂级数的操作(Manipulation of Power Series)
  • 习题答案 420
  • 附录A 数值表 572
  • 附录B 记号索引 576
  • 附录C 算法和定理索引 580

第3卷 排序与查找(Vol 3: Sorting and Searching)

第5章 排序 (Chapter 5: Sorting)

  • *5.1. 排序的组合性质(Combinatorial Properties of Permutations)
    • *5.1.1. 反序(Inversions)
    • *5.1.2. 多重集的排列(Permutations of a Multiset)
    • *5.1.3. 游程(Runs)
    • *5.1.4. Tableaux and Involutions
  • 5.2. 内部排序(Internal sorting)
    • 5.2.1. 插入排序(Sorting by Insertion)
    • 5.2.2. 交换排序(Sorting by Exchanging)
    • 5.2.3. 选择排序(Sorting by Selection)
    • 5.2.4. 合并排序(Sorting by Merging)
    • 5.2.5. 分布排序(Sorting by Distribution)
  • 5.3. 最优排序(Optimum Sorting)
    • 5.3.1. 比较次数最少的排序(Minimum-Comparison Sorting)
    • *5.3.2. 比较次数最少的合并(Minimum-Comparison Merging)
    • *5.3.3. 比较次数最少的选择(Minimum-Comparison Selection)
    • *5.3.4. 排序网络(Networks for Sorting)
  • 5.4. 外部排序(External Sorting)
    • 5.4.1. 多路合并和替代选择(Multiway Merging and Replacement Selection)
    • *5.4.2. 多阶段合并(The Polyphase Merge)
    • *5.4.3. 级联合并(The Cascade Merge)
    • *5.4.4. 反向读取磁带(Reading Tape Backwards)
    • *5.4.5. 振荡排序(The Oscillating Sort)
    • *5.4.6. 磁带合并的实践考虑(Practical Considerations for Tape Merging)
    • *5.4.7. 外部基数排序(External Radix Sorting)
    • *5.4.8. 双磁带排序(Two-Tape Sorting)
    • *5.4.9. 磁盘与磁鼓(Disks and Drums)
  • 5.5. 小结、历史与文献(Summary, History, and Bibliography)

第6章 查找(Chapter 6: Searching)

  • 6.1. 顺序查找(Sequential Searching)
  • 6.2. 通过键的比较进行查找(Searching by Comparison of Keys)
    • 6.2.1. 查找有序表(Searching an Ordered Table)
    • 6.2.2. 二叉树查找(Binary Tree Searching)
    • 6.2.3. 平衡树(Balanced Trees)
    • 6.2.4. 多路树(Multiway Trees)
  • 6.3. 数字查找(Digital Searching)
  • 6.4. 散列(Hashing)
  • 6.5. 辅助键的查找(Retrieval on Secondary Keys)

第4卷 组合算法(Vol 4: Combinatorial Algorithms)

第7章 组合检索(Chapter 7: Combinatorial Searching)

  • 7.1. Zeros and Ones 4
    • 7.1.1. Boolean Basice  4
    • 7.1.2. Boolean Evaluation  9
    • 7.1.3 Bitwise Tricks and Techniques 13
    • 7.1.4. Binary Decision Diagrams  20
  • 7.2. Generating All Possibilities 28
    • 7.2.1. Generating Basic Combinatorial Patterns   28
    • 7.2.1.1. Generating all n-tuples  28
    • 7.2.1.2. Generating all permutations  31
    • 7.2.1.3. Generating all combinations  35
    • 7.2.1.4. Generating all partitions  39
    • 7.2.1.5. Generating all set partitions   41
    • 7.2.1.6. Generating all trees  44
    • 7.2.1.7. History and further references   48

第8章 递归(Chapter 8: Recursion)

第5卷 语法算法(Vol 5: Syntactic Algorithms)

第9章 词法扫描(Chapter 9: Lexical Scanning)

第10章 语法分析(Chapter 10: Parsing Sechniques)