“2017级--学期安排 (第三学期)”的版本间的差异

• 3-0: 红黑树

2018-09-11

• 3-1：动态规划

• 通过实例掌握动态规划的基本思想与算法设计方法

• 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

• 通信系统

1. 吕云哲
2. 谢逸

• Bitonic euclidean traveling-salesman problem

1. 肖江
2. 姜勇刚

2018-09-18

• 3-2: 贪心算法

• 掌握利用贪心策略设计算法的思路与方法
• 掌握用分摊进行算法分析的思想与方法

• 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

• Huffman Codes

1. 张灵毓
2. 郑奘巍 (改次)

• Tiling Path

1. 黄秉焜 (改次)
2. 鄢振宇

2018-09-25

• 3-3：图的基本概念

• 掌握图的基本概念以及图论的基本证明方式

• CZ第一章
• CZ第二章2.1;2.2;2.3
• CZ第三章3.1

• 图论应用的广泛性以及图论证明方法的独特性
• 理解图与关系的联系

• CZ 练习1.2、1.3、1.11、1.12、1.24
• CZ 练习2.1、2.19、2.31
• CZ 练习3.1、3.2

• Merge 算法

1. 凌晨宇

2018-10-09

• 3-4：用于动态等价关系的数据结构

• 理解动态等价关系的概念以及在问题求解中的意义
• 掌握以union-find为代表的相应数据结构
• 进一步理解抽象数据类型的意义

• TC第21章

• 算法分析的困难性

• TC第21.1节练习2、3
• TC第21.2节练习1、3、6
• TC第21.3节练习1、2、3
• TC第21章问题1

• LCA

1. 杜星亮
2. 彭翔宇

• Partition Refinement

1. 袁彦
2. 马常风

2018-10-16

• 3-5: 树

• 理解树的基本数学性质
• 掌握用带权树建立数学模型的方法
• 最小生成树算法

• CZ 第4章

• 树的数学性质在计算机问题求解中的意义
• 理解贪心算法策略在最小生成树问题上的应用

• 练习 4.4、4.8、4.14、4.22、4.26、4.28、4.30、4.36

• Kruskal 算法和 Prim 算法的实现及其效率

1. 谢乃容
2. 刘恩萌

• 使用矩阵表示实现最小生成树算法

1. 何润雨
2. 殷兆恒

2018-10-25

• 3-6: 图的计算机表示以及遍历

• 掌握在计算机中表示图的方式
• 掌握图的深度优先与广度优先遍历方法

• TC第22章

• 图表示中形式与效率的关系
• 不同遍历方法的算法意义

• TC第22.1节练习 3、8
• TC第22.2节练习 3 ("lines 5 and 14" 修改为 "line 18")、4、5
• TC第22.3节练习 6、7、8、9、12
• TC第22.4节练习 2、3
• TC第22.5节练习 5、7

• DFS算法及其正确性

1. 桑百惠
2. 梁宇方

• SCC算法正确性

1. 王腾
2. 郑奘巍