陈玉福和马菲菲老师秋季学期的算法课结束了，算法课的内容中规中矩，像是本科课程内容的重复加强版（多了很多算法证明）
2019-12-24上午考的试，前后复习了大概有大半个多月，考题的内容大部分也是常见的题型，但是也有两道意想不到的很偏的题目。
题目回忆如下
一、给定多项式f(x)和g(x)，各有n项和m项。使用快速傅里叶变换求h(x)=f(x)*g(x)。
设计O(NlogN)的算法求解，并证明复杂度为O(NlogN)。需要写出算法的步骤（不用到伪代码的程度）。
二、动态规划求矩阵连乘最小值。写出步骤和求解给定实例的最优方案
三、LC分支限界求背包问题，（1）优先级函数（2）解空间树（3）最优解
四、证明当有2台机器时的多机调度问题的贪心选择性质
五、独立集问题的NPC证明
六、AC4值域消减
复习感受
先是从头到尾的看了一遍书和ppt，这一遍比较全面，但是贪心性质的证明当初复习的时候就笃定不会考，结果被现实狠狠的打了脸。
好在其他的题目和书本上的例子都比较契合，所以讲义真的很重要。
然后网上（CSDN）各种找试卷，做了一遍，然而发现并没有什么卵用。尤其是简答题，害老子最后复习时间都花在上面了。
而且里面的题多是什么Prim，Cruskal，多段图。。。
最后就是马老师的重点画的真的很准，考前说关注复杂度低的AC，NPC考的是大家比较熟悉的例子，然后就考了作业原题。
