基本要求
- 掌握典型应用中抽象出来的重要算法问题的求解方法
- 理解并能够应用支持上述内容的离散数学工具与方法
- 面向对象程序设计
考核方法
所有形式的考核,均不准抄袭。
- 作业 (10%)
- A: 10
- A-: 9
- B: 8
- B-: 7
- C: 6
- OJ (10%)
- Open topics (10%)
- 成绩: A (10), B (8), C (6) 三档
- 每人至少做一次
- 做多次报告,取最高分
- 不做计 0 分
- 期末: (70%)
指定教材
- TC: Thomas Cormen et al.: Introduction to Algorithms, 3rd ed. MIT, 2009
- CZ: Gary Chartrand, Ping Zhang: Introduction to Graph Theory
推荐课外阅读材料
(可参照习题课扩展材料部分所给出的阅读建议)
Jon Kleinberg, Eva Tardos. "Algorithm Design".
更多阅读材料将随课堂进度添加。
学习周历
日期
|
论题
|
学习目的
|
阅读材料
|
引导要点
|
书面作业
|
Open Topics
|
2018-09-04
|
|
|
|
|
|
|
2018-09-11
|
|
|
|
|
- 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
|
- 吕云哲
- 谢逸
- Bitonic euclidean traveling-salesman problem
- 肖江
- 姜勇刚
|
2018-09-18
|
|
- 掌握利用贪心策略设计算法的思路与方法
- 掌握用分摊进行算法分析的思想与方法
|
|
|
- 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
|
- 张灵毓
- 郑奘巍 (改次)
- 黄秉焜 (改次)
- 鄢振宇
|
2018-09-25
|
|
|
- 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
|
- 凌晨宇
|
2018-10-09
|
|
- 理解动态等价关系的概念以及在问题求解中的意义
- 掌握以union-find为代表的相应数据结构
- 进一步理解抽象数据类型的意义
|
|
|
- TC第21.1节练习2、3
- TC第21.2节练习1、3、6
- TC第21.3节练习1、2、3
- TC第21章问题1
|
- 杜星亮
- 彭翔宇
- 袁彦
- 马常风
|
2018-10-16
|
|
- 理解树的基本数学性质
- 掌握用带权树建立数学模型的方法
- 最小生成树算法
|
|
- 树的数学性质在计算机问题求解中的意义
- 理解贪心算法策略在最小生成树问题上的应用
|
- 练习 4.4、4.8、4.14、4.22、4.26、4.28、4.30、4.36
|
- Kruskal 算法和 Prim 算法的实现及其效率
- 谢乃容
- 刘恩萌
- 何润雨
- 殷兆恒
|
2018-10-25
|
|
- 掌握在计算机中表示图的方式
- 掌握图的深度优先与广度优先遍历方法
|
|
|
- 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
|
- 桑百惠
- 梁宇方
- 王腾
- 郑奘巍
|
2018-10-30
|
|
- 掌握单源最短路径问题的解决方法
- 理解最短路径的数学性质并理解其在算法正确性证明中的作用
|
|
|
- TC第24.1节练习 2、3、4
- TC第24.2节练习 2
- TC第24.3节练习 2、4、7
- TC第24.5节练习 2、5
- TC第24章问题 2、3
|
- 张天昀
- 丁保荣
- 使用 Fibonacci Heap 的 Dijkstra 算法的复杂度分析
- 毛一鸣
- 李顶为
|
2018-11-05
|
- [[Media: | 3-8: 多源最短路径算法]]
|
|
|
- 不同领域表面上完全不同的问题如何归结为同一个模型上的问题
|
- TC第25.1节练习 4、5、6、9、10
- TC第25.2节练习 2、4、6、8
- TC第25.3节练习 2、3
- TC第25章问题 2
|
-
-
-
-
|