第一章  算法分析基本概念：算法的概念，算法正确性，算法效率，算法的评估：掌握算法时间复杂性和空间复杂性的表示方法及O的定义

基本要求：理解算法与程序的区别；理解算法的正确性；掌握算法时间复杂性和空间复杂性的表示方O的定义；了解Ω，θ和O的定义

第二章 数学预备知识： 鸽巢原理，递推关系

基本要求：掌握递推关系的计算，用于后面章节中的算法分析

第三章 数据结构：常用数据结构

基本要求：掌握常用的数据结构

第四章 堆和不相交集数据结构：

基本要求：掌握堆的概念，堆的生成、删除、添加元素操作，理解不相交集数据结构

第五章 归纳法：基数排序，整数幂，多项式求值，生成排列

基本要求：掌握归纳法的基本设计思想，实现基数排序、整数幂、排列

第六章 递归与分治：递归概念，分治法基本思想，二分搜索技术，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择等

基本要求：掌握分治法的基本思想；理解分治法设计的特点；实现二分搜索算法、合并排序，快速排序，线性时间选择算法；能够用递推关系式求得分治法的时间复杂度

第七章 动态规划方法：动态规划的基本要素，数字三角形问题，最长公共子序列，最大子段和，凸多边形最优三角剖分,0-1背包问题，所有点对间的最短路径（Floyd-Warshall算法）等

基本要求：掌握动态规划的最优性原理，算法设计的基本步骤；实现数字三角形问题，最长公共子序列，最大子段和，凸多边形最优三角剖分,0-1背包问题，所有点对间的最短路径（Floyd-Warshall算法）

第八章 贪心算法：贪心算法的基本要素，分数背包问题，哈夫曼编码，单源最短路径问题（Dijkstra算法），最小生成树问题（Prim算法；Kruskal算法）

基本要求： 掌握贪心算法设计的基本步骤，与动态规划的区别；实现分数背包问题，哈夫曼编码，单源最短路径问题（Dijkstra算法），最小生成树问题（Prim算法；Kruskal算法）

第九章 图的遍历:深度优先、广度优先算法

基本要求：理解图的遍历的概念，掌握遍历的方法。实现深度优先、广度优先算法

第十章 问题的复杂性： P类与NP类问题。

基本要求：了解P类与NP类问题

第十一章 回溯法：回溯法的基本思想，图的着色问题， n皇后问题

基本要求：理解回溯法的基本思想。实现3-着色问题，8皇后问题。

使用教材：

M. H. Alsuwaiyel，吴伟昶 等译，《算法设计技巧与分析》（中文版），电子工业出版社，2004

教学参考书：

[1]T.H. Cormen,C.E. Leiserson, R.L. Rivest,C. Stein, Introduction to Algorithms(the thirdedition)，TheMIT Press，2009.

[2]M. H. Alsuwaiyel，Algorithms Design Techniques and Analysis，World Scientific Publishing Company，2003.

[3] 科尔曼（T.H. Corme）等著，尹建平 等译，算法导论，机械工业出版社，2013.

注：[1]为主要教学参考书，Introduction to Algorithms（算法导论），[3]为中文译本。该书是麻省理工学院算法课的教材。我们下载了麻省理工学院该门课的PPT，讲课视频，还有每堂课教师讲述的语句，可以配合PPT及视频理解讲课内容。[2]为使用教材的英文原版。

麻省理工学院 算法课 开放课程网站地址：

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/