2012级--学期安排 (第二学期)

基本要求

• 理解数据抽象，理解并能够应用常用的数据结构。
• 掌握重要算法设计策略以及算法设计与分析的基本方法。
• 理解并能够应用支持上述内容的离散数学工具与方法。

注意：程序设计能力要求贯穿于整个课程，不再单列。

指定教材

• CS: Cliff Stein et al.: Discrete Mathematics for Computer Scientists, 1st ed. Addison-Wesley, 2010
• DW: Douglas West: Introduction to Graph Theory, 2nd ed. Pearson, 2000
• SB: Sara Baase et al.: Computer Algorithms - Introduction to Design and Analysis, 3rd ed. Addison-Wesley, 1999 (第2章：抽象数据类型)
• TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009
• WS: Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008

推荐课外读物

• Kenneth H. Rosen: Discrete Mathematics and Its Applications, 7th ed. McGraw-Hill, 2011

学习周历

日期	论题	学习目的	阅读材料	引导要点	书面作业	编程任务
2.25--3.1	2-1：算法问题与解题的算法	理解计算机算法的相关概念 掌握算法复杂性的基本度量方法	TC第1、2、3章	算法设计与算法分析是计算机问题求解不可互却的两个方面	TC第2章问题1、2、3、4 TC第3章问题2、3、4	WS第9章项目5 WS第9章项目6
3.4--3.8	2-2：组合与计数	掌握在算法分析中常用的计数原理与方法	CS第1章	为什么算法分析中需要计数	CS第1.1节问题9、13 CS第1.2节问题15 CS第1.3节问题6、9、14 CS第1.5节问题8、10、15	任给k个元素的字母表；编程输出所有可能的组合串，且每个串中没有重复字母。如果可以任意某一个或多个字母可重复的次数，修改你的算法。复杂性是否会增加？
3.11--3.15	2-3：分治法与递归	掌握利用分治法设计算法的思路 深入理解递归在算法设计中的作用	TC第4章	策略在计算机算法设计中的意义	TC第4.1节练习5 TC第4.3节练习3、7 TC第4.4节练习2、8 TC第4.5节练习4 TC第4章问题1、3、4	Strassen算法
3.18--3.22	2-4：递归及其数学基础	进一步理解递归的数学基础 更深入地掌握递归算法的分析方法	CS第4章	如何解递归式	CS第4.1节问题16、17 CS第4.2节问题8、11、17 CS第4.3节问题9、13、16 CS第4.4节问题1、4、6 CS第4.5节问题8、9、10	WS第10章项目10 WS第10章项目13
3.25--3.29	2-5：离散概率基础	理解离散概率的基本概念 掌握简单离散概率计算的基本方法	CS第5章第1、2、3、4节	正确理解期望值，由此建立算法分析中期望效率理解的基础	CS第5.1节问题6、10、11、12、13 CS第5.2节问题2、9、10、14、15 CS第5.3节问题3、4、8、11、12、13 CS第5.4节问题5、6、8、10、17、20、21	利用一个现成的随机数生成函数，模拟3个色子的试验；加大试验次数，比较试验结果与理论概率分布
4.1--4.5	2-6：概率分析与随机算法	理解概率在算法设计中的作用 掌握基于概率的算法分析的基本方法	TC第5章 CS第5章第6、7节	随机变量在算法分析中的意义	CS第5.6节问题4、8 CS第5.7节问题1、2、4、6、12、16、18 TC第5.2节练习1、2、4 TC第5.3节练习1、2、3、4 TC第5章问题2	随机排列生成算法
4.8--4.12	2-7：排序与选择	深入理解快速排序算法的设计思想与分析方法 通过排序理解问题复杂度的下限，并探索一些线性排序算法 掌握以中位数为代表的统计算法	TC第7、8、9章	如何证明问题复杂度的下限	TC第7.1节练习2 TC第7.2节练习4 TC第7.3节练习2 TC第7.4节练习2 TC第7章问题4、5 TC第8.1节练习3、4 TC第8.2节练习4 TC第8.3节练习4 TC第8.4节练习2 TC第8章问题2 TC第9.1节练习1 TC第9.3节练习5、7	快速排序
4.15--4.19	2-8：基本数据结构	掌握堆栈、队列、链表、指针、根树的概念、实现以及在算法设计中的应用	TC第10章	数据结构的算法支撑与实现效率的平衡	TC第10.1节练习4、5、6 TC第10.2节练习1、2、3、6 TC第10.3节练习4、5 TC第10.4节练习2、3、4 TC第10章问题3	实现根树
4.22--4.26	2-9：堆与堆排序	理解并掌握堆的结构、实现以及算法应用 通过堆的应用与实现理解抽象数据类型的基本概念以及分层抽象的思想	TC第6章 SB第2章	从数据结构到抽象数据类型的思想发展	TC第6.1节练习2、4、7 TC第6.2节练习2、5、6 TC第6.3节练习3 TC第6.4节练习2、4 TC第6.5节练习5、7、9	堆排序
4.29--5.3	2-10：Hashing方法	掌握Hashing方法的原理、处理冲突的方法以及分析方法	TC第11章 CS第5章第5节	Hashing方法中的冲突处理	CS第5.5节问题8、11、14 TC第11.2节练习3、5、6 TC第11.3节练习3、4 TC第11.4节练习2、3 TC第11章问题1、2	用至少两个不同的Hash函数实现hashing，并比较冲突情况
5.6--5.10	2-11：搜索树	掌握利用树结构存储与搜索数据的方法	TC第12、13章	树的平衡与搜索效率的关系	TC第12.1节练习2、5 TC第12.2节练习5、8、9 TC第12.3节练习5 TC第12章问题1 TC第13.1节练习5、6、7 TC第13.2节练习2 TC第13.3节练习1、5 TC第13.4节练习1、2、7	实现红黑树，并比较与简单二分搜索树的执行效率
5.13--5.17	2-12：动态规划	通过实例掌握动态规划的基本思想与算法设计方法	TC第15章	以空间换时间的关键是存储效率 动态规划与指数时间的有效降低	TC第15.1节练习1、3 TC第15.2节练习2、4 TC第15.3节练习3、5、6 TC第15.4节练习3、5 TC第15.5节练习1 TC第15章问题4	实现矩阵连乘
5.20--5.24	2-13：贪心算法	掌握利用贪心策略设计算法的思路与方法 掌握用分摊进行算法分析的思想与方法	TC第16章第1、2、3节 TC第17章	贪心算法的正确性证明	TC第16.1节练习2、3 TC第16.2节练习1、2 TC第16.3节练习2、5、8 TC第16章问题1 TC第17.1节练习3 TC第17.2节练习2 TC第17.4节练习1	Hoffman码
5.27--5.31	2-14：用于动态等价关系的数据结构	理解动态等价关系的概念以及在问题求解中的意义 掌握以union-find为代表的相应数据结构 进一步理解抽象数据类型的意义	TC第21章 SB第2章	算法分析的困难性	TC第21.1节练习2、3 TC第21.2节练习1、3、6 TC第21.3节练习1、2、3 TC第21章问题1	编一个程序自动生成迷宫
6.3--6.7	2-15：图的基本概念	掌握图的基本概念以及图论的基本证明方式	DW第1章	图论应用的广泛性以及图论证明方法的独特性 理解图与关系的联系	DW第1.1节练习4、5、10、14、16、31 DW第1.2节练习5、7、11、17、18、20、38、40 DW第1.3节练习1、10、14、15、18、61 DW第1.4节练习1、5、8、10、11、21	WS第11章项目3 WS第11章项目5
6.10--6.14	2-16：图的计算机表示以及遍历	掌握在计算机中表示图的方式 掌握图的深度优先与广度优先遍历方法	TC第22章	图表示中形式与效率的关系 不同遍历方法的算法意义	TC第22.1节练习3、8 TC第22.2节练习3、4、5 TC第22.3节练习6、7、8、9、12 TC第22.4节练习2、3 TC第22.5节练习5、7	实现深度与广度遍历
6.17--6.21	2-17：树	理解树的基本数学性质 掌握用加权树建立数学模型的方法	DW第2章	树的数学性质在计算机问题求解中的意义	DW第2.1节练习2、7、9、15、18、21、23、29、33、37、48 DW第2.2节练习2、6、7、8、10 DW第2.3节练习1、2、6、12、13、14、18、21	WS第14章项目10 WS第14章项目11
暑假自学	2-18：最小生成树算法	理解贪心算法策略在最小生成树问题上的应用	TC第23章	如何评价同一问题的不同算法		Prim和Kruskal算法