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

基本要求

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

考核方法

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

• 作业 (10%)
• OJ (10%)
• Open topics (10%)
  • 成绩: A (10), B (8), C (6) 三档
  • 每人至少做一次
  • 做多次报告，取最高分
  • 不做计 0 分
• 期末: (70%)
  • 机试 (20%)
  • 笔试 (50%)

2017-2-final-exam.pdf ( 2017-2-final-exam-src.zip)

指定教材

• 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
• SB: Sara Baase et al.: Computer Algorithms - Introduction to Design and Analysis, 3rd ed. Addison-Wesley, 1999 (第2章：抽象数据类型)

推荐课外阅读材料

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

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

• Donald E. Knuth: The Art of Computer Programming Vol4A: Combinatorial Algorithms Part 1, 2011

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

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

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

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

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

学习周历

日期	论题	学习目的	阅读材料	引导要点	书面作业	Open Topics
2018-03-07	2-1: 算法正确性	理解并能够区分算法错误与程序错误 理解算法正确性的概念及其证明方法	DH第5章	算法正确性证明与一般数学定理证明的异同	DH 第5章练习 6, 9, 10, 12 证明 Euclid (欧几里德) 算法的部分正确性	Insertion Sort 刘恩萌 姜勇刚 张天昀 Cyclic Hanoi 李凯旭 郑奘巍 董杨静
2018-03-14	2-2: 算法的效率	理解算法的时间复杂性的概念与渐近表示方式	DH第6章 TC 2.1节, 2.2节, 3.1节	从无限与有限的角度正确理解算法复杂度	DH 第6章练习 1, 8, 10, 13, 18	Algorithmic Gap 王腾 李顶为 肖江 Asymptotic Notations 马常风 黄秉焜 吕云哲
2018-03-21	2-3: 组合与计数	掌握在算法分析中常用的计数原理与方法	CS第1章	为什么算法分析中需要计数	CS 1.1 节 13 CS 1.2 节 5, 15 CS 1.5 节 4, 12, 14	The twelvefold way (1) 高天朗 谢逸 何伟 The twelvefold way (2) 张廷昊 匡舒磊 殷天润
2018-03-28	2-4: 分治法与递归	掌握利用分治法设计算法的思路 深入理解递归在算法设计中的作用	TC第4章	策略在计算机算法设计中的意义	TC第4.1节练习5 TC第4.3节练习3 TC第4.4节练习2 TC第4.5节练习3 TC第4章问题4	证明 The Master Theorem 兰兆炜 邱凯 (改次) 吕云哲 介绍 Akra–Bazzi Method 李博文 何润雨 (改次) 刘寒
2018-04-04	2-5: 递归及其数学基础	进一步理解递归的数学基础 更深入地掌握递归算法的分析方法	CS第4章	如何解递归式	CS第4.1节问题 16, 17 CS第4.2节问题 8, 11 CS第4.3节问题 9 CS第4.4节问题 1, 6 CS第4.5节问题 8, 9, 10	Josephus Problem 裴一凡 戴若石 毕秋宇 Generating Function 张灵毓 何润雨 丁保荣
2018-04-09	2-6: 算法方法	通过具体示例了解算法设计的基本策略	DH第4章	理解复杂算法背后的简单原理	DH 第4章练习 1, 8, 9, 12, 14	Alpha-Beta 剪枝 张博乔 郑奘巍 张天昀 SAT 求解算法 袁彦 李顶为 杨欣然
2018-04-18	2-7: 离散概率基础	理解离散概率的基本概念 掌握简单离散概率计算的基本方法	CS第5章: 5.1, 5.2, 5.3, 5.4 节	正确理解“期望”的概念，为理解平均情况时间复杂度分析建立基础	CS第5.1节问题 10, 12 CS第5.2节问题 4, 10 CS第5.3节问题 2, 6, 12 CS第5.4节问题 4, 10, 12 ("Solve Problem 10" 改为 "Solve Problem 11"), 15	无
2018-04-25	2-8: 概率分析与随机算法	理解概率在算法设计中的作用 掌握基于概率的算法分析的基本方法	TC第5章 CS第5章: 5.6, 5.7节	随机变量在算法分析中的意义	CS第5.6节问题 4, 8 CS第5.7节问题 2, 4, 6, 12 TC第5.2节练习 4, 5 TC第5.3节练习 2, 3, 4	Monty Hall Problem 李博文 毛一鸣 毕秋宇 TC Problem 5.2: Searching an unsorted array 许致明 何润雨 殷兆恒
2018-05-02	2-9: 排序与选择	深入理解快速排序算法的设计思想与分析方法 通过排序理解问题复杂度的下界，并探索一些线性排序算法 掌握以中位数为代表的统计算法	TC第7、8、9章	如何证明问题复杂度的下界	TC 第七章: Exercises: 7.1-3, 7.2-4, 7.3-2, 7.4-2 Problem: 7.5 TC 第八章: Exercises: 8.1-4, 8.2-4, 8.3-4, 8.4-2 Problem: 8.2 TC 第九章 Exercises: 9.1-1, 9.3-7	TC Problem 7.4 徐臣 陈昱名 谢乃容 Random-Selection 算法的期望时间复杂度 鄢振宇 张扬播 韩博
2018-05-09	2-10: 基本数据结构	掌握堆栈、队列、链表、指针、根树的概念、实现以及在算法设计中的应用	TC第10章 MA第2, 3章	数据结构的算法支撑(???)与实现效率的平衡	MA 2.6 (只要求考察 Push 操作) 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	A stack, two queues 杜星亮 (改次) 陶绍诚 丁保荣 (改次) 正确性 姜勇刚
2018-05-14	2-11: 堆与堆排序	理解并掌握堆的结构、实现以及算法应用 通过堆的应用与实现理解抽象数据类型的基本概念以及分层抽象的思想	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	Heapsort vs. Quicksort 性能 张灵毓 凌晨宇 廖玺然 Binary tree => Heap => Priority queue 马常风 邱凯 肖江
2018-05-21	2-12: Hashing方法	掌握Hashing方法的原理、处理冲突的方法以及分析方法	TC第11章 CS第5章第5节	Hashing方法中的冲突处理	CS第5.5节问题 8、14 TC第11.2节练习 3、6 TC第11.3节练习 3、4 TC第11.4节练习 2、3 TC第11章问题 1、2	Universal Hashing 周涛 Hash 故事会 陈巍
2018-06-04	2-13：搜索树	掌握利用树结构存储与搜索数据的方法	TC第12、13章	树的平衡与搜索效率的关系	TC第12.1节练习 2、5 TC第12.2节练习 5、9 TC第12.3节练习 5 TC第13.1节练习 5、7 TC第13.2节练习 2 TC第13.3节练习 1、5 TC第13.4节练习 1、7	Splay tree 杜星亮 (一班) 孙旭东 (一班) 中序遍历的正确性 银加 (二班) 鄢振宇 (一班)
2018-06-11	2-14：B 树	掌握 B 树的基本性质及其操作	TC第18章	如何在经典数据结构的基础上，针对应用特征，优化设计，提高效率	TC 练习 18.1.1,18.1.4 TC 练习 18.2.3,18.2.4 TC 练习 18.3.1	B 树插入算法对高度的影响 殷兆恒 (三班) 黄秉焜 (二班) 介绍 B* 树 邱凯 (二班) 谢乃容 (三班)