算法设计与分析

课程性质：考试

学分：2

分数构成 = 20% 课程作业 + 20% 课程报告 + 60% 期末考试

关于课程

1. 总体介绍

课程内容：课程围绕算法展开，主干内容为时间复杂性分析、分治算法、动态规划算法、贪心算法、平摊分析、树搜索算法、图算法。
开设学期：基于当前培养方案（2021/2022），同一年级的学生会分成三个批次依次修读该课程。
课程难度：总体难度较大，且本质偏数学（算法推理、正确性证明等），与算法竞赛的侧重点不同，有OI/ACM经历 ≠ 本课程能轻松取得高分。

2. 关于授课

ZKQ：老师很和蔼，上课不点名，讲课耐心细致，通俗易懂，建议认真听老师讲课。

3. 关于作业

老师会挑选一些经典的习题留作作业，具体提交方式/作业量可能因老师而异。作业中题目风格很有可能是考试题目风格。

4. 关于考试

正常情况下，卷面布局如下（注意：不同课程组的老师出题风格有所不同，且未来可能会变动）：

判断题+简答题+算法设计题

判断题：知识点覆盖较为全面，从最初的时间复杂度分析到最后的网络流/匹配问题都可能会出判断题。题目难度较小，如果复习得当，大部分判断题都是送分题。
简答题：一般会出时间复杂度计算（master定理、递推等）、平摊分析（难度浮动较大）、树搜索算法（模拟搜索过程、叙述某搜索算法的流程等）、图算法（求最大流等），涉及的考点一般会是分治、贪心、动态规划算法以外的内容。
算法设计题：一般情况下为固定的三道题，分别考察分治、贪心、动态规划算法，难度浮动较大，不仅需要写出算法伪代码，还要给出数学上的正确性证明。23春算法期末考试贪心算法设计题为防晒；23秋算法期末考试分治算法设计题为最大字段和，动态规划设计题为编辑距离。

5. 分数参考

2021级内容编者 93分教学班第1（信安/网安专业）

学习经验

如果老师讲课通俗易懂，那建议平时认真听老师讲课，课下能够省下不少功夫。课下一定要勤加练习，复习时PPT上的内容要重点掌握。分治、贪心、动态规划三个章节知识点需要大量的练习（数学证明过程+代码，解题模板可参考PPT，考试可能会出PPT上题目的变形）。动态规划思想对于初学者难度较大，状态设计和状态转移方程的建立需要熟能生巧，有能力的同学可以去一些在线OJ网站进行进一步练习。

参考书目

[1] 《算法导论》 Thomas H. Cormen等编著机械工业出版社