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

基本要求

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

考核方法

所有形式的考核,均不准抄袭。

考核形式	分值
作业	15
OT	10
OJ	15
机试	10
笔试	50

指定教材

• DH: David Harel et al.: Algorithmics - The Spirit of Computing, 3rd ed. Addison-Wesley, 2004
• CS: Clifford Stein et al.: Discrete Mathematics for Computer Scientists, 1st ed. Addison-Wesley, 2010
• TC: Thomas Cormen et al.: Introduction to Algorithms, 3rd ed. MIT, 2009
• MA: Manoochehr Azmoodeh. Abstract Data Types and Algorithms, Macmillan Education, UK, 1990

推荐课外阅读材料

(可参照习题课扩展材料部分所给出的阅读建议)

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

• [TAOCP-4A] Donald E. Knuth: The Art of Computer Programming Vol4A: Combinatorial Algorithms Part 1, 2011

• [GKP] Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science, 2nd Edition, 1994.

• [PP] Jon Bentley: Programming Pearls, 2nd Edition, 1999.

• [AoA] Robert Sedgewick, Philippe Flajolet: Book: An Introduction to the Analysis of Algorithms, 2nd Edition, 2012.

• [TheBook] Martin Aigner: Book: Proofs from THE BOOK, Fifth Edition, 2014.

• [MCS] Eric Lehman, F Thomson Leighton, Albert R Meyer: Mathematics for Computer Science, MIT, 2018.

更多阅读材料将随课堂进度添加。

学习周历

日期	论题	学习目的	阅读材料	引导要点	书面作业 (非稳定版本作业@GitHub)	编程作业
2020-02-20	1-13: 布尔代数	理解布尔代数基本概念 理解布尔代数与格的联系与区别 布尔代数表达式的化简	SM第15章	布尔代数	1-13-boolean-algebra	[布尔代数与算法正确性]
2020-02-27	2-1: 算法的正确性	理解并能够区分算法错误与程序错误 理解算法正确性的概念及其证明方法	DH第5章	循环不变式	2-1-correctness	[热身专题]
2020-03-05	2-2：算法的效率 2019-2-2-efficiency 2019-2-2-efficiency-handout	理解算法的时间复杂性的概念与渐近表示方式	DH第6章 TC 2.1节, 2.2节 TC 第3章	如何做算法复杂度分析	2-2-efficiency	[算法复杂度]
2020-03-12	2-3：组合与计数 2019-2-3-counting 2019-2-3-counting-handout	掌握在算法分析中常用的计数原理与方法	CS第1章	组合计数技巧与常见形式	2-3-counting	[组合与计数]
2020-03-19	2-4: 分治法与递归	掌握利用分治法设计算法的思路 深入理解递归在算法设计中的作用	TC 第2.3节 TC 第4章	算法设计中的分治思想	2-4-recurrence	[分治法与递归]
2020-03-26	2019-2-5-linear-recurrences (马) 2019-2-5-linear-recurrences (魏) 2019-2-5-linear-recurrences-handout (魏)	进一步理解递归的数学基础 更深入地掌握递归算法的分析方法	CS第4章 4.1-4.5 节	如何解递归式	2-5-solving-recurrence	[分治法与递归2]
2020-04-02	2-6: 算法方法	通过具体示例了解算法设计的基本策略	DH第4章	理解复杂算法背后的简单原理	2-6-algorithmic-methods	[算法方法]
2020-04-09	2-7: 离散概率基础	理解离散概率的基本概念 掌握简单离散概率计算的基本方法	CS第5章: 5.1, 5.2, 5.3, 5.4 节	正确理解“期望”的概念，为理解平均情况时间复杂度分析建立基础	2-7-discrete-probability	[离散概率]
2020-04-16	2-8: 概率分析与随机算法	理解概率在算法设计中的作用 掌握基于概率的算法分析的基本方法	TC第5章 CS第5章: 5.6, 5.7节	随机变量在算法分析中的意义	2-8-probabilistic-analysis	[随机算法]
2020-04-23	2019-2-9-sorting and selection.pdf 2019-2-9-sorting_and_selection(handout).pdf	深入理解快速排序算法的设计思想与分析方法 通过排序理解问题复杂度的下界，并探索一些线性排序算法 掌握以中位数为代表的统计算法	TC第7、8、9章	如何证明问题复杂度的下界	2-9-sorting-selection	[排序与选择]
2020-04-30	2-10: 基本数据结构	掌握堆栈、队列、链表、指针、根树的概念、实现以及在算法设计中的应用	TC第10章 MA第2, 3章	基本数据结构	2-10-data-structures	[基础数据结构-1]
2020-05-07	2019-2-11_Heap&HeapSort ‎	理解并掌握堆的结构、实现以及算法应用 通过堆的应用与实现理解抽象数据类型的基本概念以及分层抽象的思想	TC第6章	从数据结构到抽象数据类型的思想发展	2-11-heapsort	[基础数据结构-2]
2020-05-14	2-12: Hashing方法	掌握Hashing方法的原理、处理冲突的方法以及分析方法	TC第11章 CS第5章第5节	Hashing方法中的冲突处理	2-12-hashing	[哈希]
2019-05-21	2-13：搜索树	掌握利用树结构存储与搜索数据的方法	MA 第4.1节 TC第12章	搜索树的结构与操作	2-13-bst	[搜索树]
2019-05-28	2-14：B 树	掌握 B 树的基本性质及其操作	TC第18章	如何在经典数据结构的基础上，针对应用特征，优化设计，提高效率	2-14-b-tree	[编程复习]
2019-06-04	2-15: 红黑树 (改为课堂练习)	掌握红黑树数据结构的基本性质及其操作	TC第13章	红黑树的概念	2-15-rb-tree
					2019-2-correction