第1章 算法概述

1.1 引言

1.1.1 算法的描述

1.1.2 算法的特性

1.1.3 为什么学习算法

1.2 算法的设计

1.3 算法的分析

1.3.1 正确性分析

1.3.2 时空效率分析

1.3.3 时空特性分析

1.4 解决问题的一般步骤

1.5 小结

1.6 习题

第2章 递归与分治策略

2.1 递归算法

2.1.1 递归的概念

2.1.2 具有递归特性的问题

2.1.3 递归算法分析

2.2 分治策略

2.2.1 分治法的基本步骤

2.2.2 分治法的适用条件

2.2.3 二分搜索技术

2.2.4 棋盘覆盖问题

2.2.5 快速排序

2.2.6 大整数乘法

2.2.7 矩阵乘法

2.3 ACM经典问题解析

2.3.1 蜂窝问题（难度：★☆☆☆☆）

2.3.2 Humble Numbers（难度：★★☆☆☆）

2.3.3 Copying Books（难度：★★★☆☆）

2.3.4 Fractal（难度：★★★☆☆）

2.3.5 TOYS（难度：★★☆☆☆）

2.3.6 Cable master（难度：★★☆☆☆）

2.4 小结

2.5 习题

第3章 动态规划

3.1 何谓动态规划

3.1.1 动态规划的基本思想

3.1.2 设计动态规划法的步骤

3.1.3 动态规划问题的特征

3.1.4 动态规划与静态规划的关系

3.2 矩阵连乘积问题

3.2.1 分析最优解的结构

3.2.2 建立递归关系

3.2.3 计算最优值

3.2.4 构造最优解

3.3 动态规划算法的基本要素

3.3.1 最优子结构

3.3.2 重叠子问题

3.3.3 备忘录方法

3.4 最长公共子序列

3.4.1 最长公共子序列的结构

3.4.2 子问题的递归结构

3.4.3 计算最优值

3.4.4 构造最长公共子序列

3.5 最大子段和

3.5.1 递归关系分析

3.5.2 算法实现

3.6 0-1背包问题

3.6.1 递归关系分析

3.6.2 算法实现

3.7 ACM经典问题解析

3.7.1 数塔（难度：★★☆☆☆）

3.7.2 免费馅饼（难度：★★★☆☆）

3.7.3 Dividing（难度：★★★☆☆）

3.7.4 Win the Bonus（难度：★★★★☆）

3.7.5 Monkey and Banana（难度：★★★★☆）

3.7.6 Railroad（难度：★★★★☆）

3.8 小结

3.9 习题

第4章 贪心算法

4.1 活动安排问题

4.2 贪心算法的理论基础

4.2.1 贪心算法的基本思想

4.2.2 贪心算法的基本要素

4.2.3 贪心算法的基本步骤

4.3 删数问题

4.3.1 贪心策略选择

4.3.2 最优子结构

4.3.3 算法实现

4.3.4 复杂度分析

4.4 背包问题

4.4.1 最优子结构性质

4.4.2 贪心选择性质

4.4.3 算法实现

4.4.4 复杂度分析

4.5 最优装载问题

4.5.1 贪心选择性质

4.5.2 最优子结构性质

4.5.3 算法实现

4.5.4 复杂度分析

4.6 单源最短路径

4.6.1 算法基本思想

4.6.2 贪心选择性质

4.6.3 最优子结构性质

4.6.4 Dijkstra算法实现

4.6.5 复杂度分析

4.7 多处最优服务次序问题

4.7.1 贪心选择策略

4.7.2 贪心选择性质

4.7.3 最优子结构性质

4.7.4 算法实现

4.7.5 复杂度分析

4.8 ACM经典问题解析

4.8.1 Fat Mouse Trade（难度：★★☆☆☆）

4.8.2 Sorting the Photos（难度：★★★☆☆）

4.8.3 Moving Tables（难度：★★★☆☆）

4.8.4 Box of Bricks（难度：★★★★☆）

4.8.5 Wooden Sticks（难度：★★★★☆）

4.8.6 钓鱼问题（难度：★★★★☆）

4.8.7 树形DP问题（难度：★★★★☆）

4.8.8 Frogs'Neighborhood（难度：★★★☆☆）

4.9 小结

4.10 习题

第5章 回溯法

5.1 回溯法的基本思想

5.1.1 问题的解空间

5.1.2 搜索的解空间

5.1.3 回溯的基本步骤

5.1.4 回溯法实现

5.2 图的m着色问题

5.2.1 问题的解空间

5.2.2 约束条件

5.2.3 搜索解空间

5.2.4 代码实现

5.2.5 算法时间复杂度分析

5.3 n皇后问题

5.3.1 问题的解空间

5.3.2 约束条件

5.3.3 搜索过程

5.3.4 算法的时间复杂度分析

5.4 装载问题

5.4.1 问题的解空间

5.4.2 约束条件

5.4.3 限界条件

5.4.4 搜索过程

5.4.5 算法效率分析

5.5 0-1背包问题

5.5.1 问题的解空间

5.5.2 约束条件

5.5.3 限界条件

5.5.4 搜索过程

5.5.5 算法效率分析

5.6 旅行商问题

5.6.1 问题的解空间

5.6.2 约束条件

5.6.3 限界条件

5.6.4 搜索解空间

5.6.5 时间复杂度分析

5.7 批处理流水作业调度问题

5.7.1 问题的解空间

5.7.2 约束条件

5.7.3 限界条件

5.7.4 搜索过程

5.7.5 时间复杂度分析

5.8 ACM经典问题解析

5.8.1 Dreisam Equations（难度：★★★☆☆）

5.8.2 A Plug for UNIX（难度：★★★☆☆）

5.8.3 回文构词检测（Anagram Checker）（难度：★★☆☆☆）

5.8.4 Unshuffle（难度：★★★☆☆）

5.9 小结

5.10 习题

第6章 分支限界算法

6.1 分支限界法的基本理论

6.1.1 分支限界法的搜索策略

6.1.2 分支结点的选择

6.1.3 限界函数

6.2 单源最短路径问题

6.2.1 问题描述

6.2.2 算法描述与设计

6.2.3 算法实现

6.3 装载问题

6.3.1 问题描述

6.3.2 算法设计与实现

6.4 0-1背包问题

6.4.1 问题描述

6.4.2 算法描述与设计

6.4.3 算法实现

6.5 旅行商问题

6.5.1 问题描述

6.5.2 算法描述与设计

6.5.3 算法实现

6.7 ACM经典问题

6.7.1 布线问题（难度：★★★☆☆）

6.7.2 方格调整问题（难度：★★★☆☆）

6.7.3 旅行售货员问题（难度：★★★☆☆）

6.7.4 Grandpa's Estate（难度：★★★☆☆）

6.7.5 Find The Multiple（难度：★★★☆☆）

6.8 小结

6.9 习题

第7章 图的搜索算法

7.1 图的广度优先搜索遍历

7.1.1 算法描述与分析

7.1.2 程序实现

7.2 图的深度优先搜索遍历

7.2.1 算法描述与分析

7.2.2 程序实现

7.2.3 有向无圈图的拓扑排序

7.3 有向图的强连通分支

7.3.1 算法描述与分析

7.3.2 程序实现

7.4 无向图的双连通分支

7.4.1 算法描述与分析

7.4.2 程序实现

7.5 流网络与最大流问题

7.5.1 算法描述与分析

7.5.2 程序实现

7.6 ACM经典问题解析

7.6.1 Is It A Tree？（难度：★★★☆☆）

7.6.2 Stockbroker Grapevine（难度：★★★☆☆）

7.6.3 A Plug for UNIX（难度：★★★☆☆）

7.7 小结

7.8 习题

第8章 公钥加密算法

8.1 RSA公钥密码算法

8.1.1 算法描述

8.1.2 快速模幂算法

8.1.3 素数的生成

8.1.4 扩展欧几里得算法

8.2 因子分解算法

8.2.1 Pollard's p-l法

8.2.2 Pollard's rho法

8.3 离散对数密码算法

8.3.1 Diffie-Hellman密钥交换协议

8.3.2 ElGamal公钥密码算法

8.4 离散对数算法

8.4.1 小步／大步法

8.4.2 Pohlig-Hellman法

8.5 ACM的经典问题

8.5.1 简单的加密算法（难度：★★☆☆☆）

8.5.2 古代密码（难度：★★★☆☆）

8.6 小结

8.7 习题

第9章 P和NP问题浅析

9.1 决策问题和优化问题

9.2 何谓P类和NP类问题

9.2.1 P类问题

9.2.2 NP类问题

9.3 （确定性）图灵机

9.3.1 图灵机的定义

9.3.2 k带图灵机形式化描述

9.3.3 图灵机计算实例

9.4 非确定性图灵机

9.4.1 非确定性图灵机定义

9.4.2 非确定性图灵机形式化描述

9.4.3 非确定性图灵机计算实例

9.4.4 非确定性算法

9.4.5 NP类问题的定义

9.4.6 NP难（NP-hard）

9.5 NP完全问题P＊

9.5.1 定义

9.5.2 多项式时间规约

9.5.3 库克定理

9.5.4 3-SAT问题

9.5.5 NP完全问题的近似算法

9.6 NP难问题的近似算法

9.6.1 旅行商问题的近似算法

9.6.2 背包问题的近似算法

9.7 小结

9.8 习题

附录A 求和

附录B 数论入门

参考文献