《算法基础》课程主页 ( 信息安全本科16级，2019.3～2019.6)

• 课程情况

授课教师：庄连生 辅导老师：沈三景，唐明宇，白建峰

上课教室：3C103 上课时间：每周2(6,7)和5(3,4) (3～16周)

课程学时：60/30 课程学分：3.5

• 课程通知

1) 欢迎同学们参加本课程的学习；(2.27)

• 教材信息

1)《算法导论》(原书第2版), T.H.Cormen等著,潘金贵等译，机械工业出版社，2006.9;

2)《计算机算法设计与分析》(第3版)，王晓东著，电子工业出版社，2007.5；

3)《算法设计与分析基础》，Anany Levitin著，潘彦译，清华大学出版社，2007;

• 教学内容

第1讲 算法入门（下载PDF）

第2讲 函数增长（下载PDF）

第3讲 递归式（下载PDF）

第4讲 递归和分治策略（下载PDF）

第5讲 概率分析和随机算法（下载PDF）

第6讲 排序算法（下载PDF）

第7讲 顺序统计学（下载PDF）

第8讲 红黑树及其扩张（下载PDF）

第9讲 动态规划（下载PDF）

第10讲 贪心算法（下载PDF）

第11讲 回溯法（下载PDF, 补充课件PPT）

第12讲 分支限界法（下载PDF, 补充课件PPT）

第13讲 随机算法（下载PDF）

阶段复习（下载PDF）

第14讲 有关数论的算法（下载PDF）

第15讲 字符串匹配（下载PDF）

• 课程作业

作业1：2.3-3, 2.3-4, 2.3-6, 3.1-1, 3.1-3, 3.1-4

作业2：4.3-3, 4.3-8, 4.3-9, 4.4-1, 4.4-7, 4,5-1, 4,5-4

作业3：6.1-3, 6.2-1, 6.3-1, 6.4-1, 7.2-5, 8.1-1, 8.2-4, 8.3-2, 8.3-4, 8.4-4

作业4：9.3-6, 9.3-7, 9.3-9, 12.1-1, 12.1-2, 12.4-2

作业5：13.1-6, 13.2-3, 13.3-2, 13.3-3, 13.4-3, 14.1-5, 14.3-4

作业6：15.2-1, 15.4-1, 15.4-5

• 实验题目

实验1：排序算法性能比较实验。实验要求：(1)至少包含插入排序、归并排序、堆排序、快速排序算法;（2）待排序数组规模（50万，100万，200万，300万，400万，500万），每种规模下随机产生10次，观察运行时间的均值和方差。

实验2：请利用区间树实现简易课表管理系统，支持：1）插入一门新课；2）删除课程；3）查询特定时间区间的所有课程名称。注意：每门课信息包括课程编号、课程名称、上课时间。

实验3：请利用穷举法、自顶向下的备忘录法、动态规划算法、回溯法、分支限界法、拉斯维加斯算法以及融合回溯法的拉斯维加斯算法来求解0-1背包问题，比较不同算法的时间复杂度和空间复杂度。关于0-1背包问题描述如下：有一个包和n个物品，包的容量为m，每个物品都有各自的体积和价值，问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时，能够得到的最大价值是多少？[对于每个物品不可以取多次，最多只能取一次，之所以叫做01背包，0表示不取，1表示取]

实验5：请实现最小生成树的Prim算法和Kruskal算法

最后更新：2018年2月23日 访问人次：