任庆生 · 算法与复杂性修读档案

老师讲得挺好，思路好歹算条明路，可这中午一节接着一节连上三节是真的顶不住啊……认真听的话应该能不小白地收获一波。老师本人偏严肃挂，上课基本就是知识点端出来讲解。今年这考试好像还挺简单？（？）

**课程内容：** 期末对着书和笔记复习的，基本上是按《**算法引论：一种创造性方法**》来的 第1章 引论（一带而过） 第2章 数学归纳法（书里一些简单例子被删掉了） 第3章 算法分析（跟书差不多） 第4章 数据结构（没讲） 第5章 基于归纳的算法设计（跟书差不多） 第6章 序列和集合算法（跟书差不多） 第7章 图算法（补了美术馆和多边形三角划分） 第7.5章 机器学习基础（书上没有）（不考） 第8章 几何算法（补了Voronoi图） 第9章 代数算法（补了不少内容） 第10章 归约（跟书差不多） 第10.5章 线性规划的求解（书上没有）（不考） 第11章 P=NP问题（跟书差不多） 第12章 并行算法（不考） **上课自由度：** **100**，不考勤不签到不点名不提问 后半学期事多，课听不进去，于是好多周干脆摆烂没去，全靠追回放。 **考核标准：** **50%平时成绩** 纯个人瞎猜：本学期布置2次头歌编程题，10道序列和集合算法+8道图算法，每次20分；本学期布置7次书面作业，2周1次，除了16周课没布置以及五一冲掉11周课，去掉1个最低分后，每次10分；编程题按通过题数算分，平时作业按助教给的分数等比例换算；照这套规则算出的平时成绩跟我对上了，所以胆大妄为地猜是这样。 **50%期末成绩** 1.极小点定义为：给出点集(x_1, y_1)(x_2, y_2)……(x_n, y_n)，对于点(x_i, y_i)，若不存在(x_j, y_j)使得x_i>x_j且y_i>y_j，则称(x_i, y_i)为点集的极小点。设计算法求极小点【作业原题：求极大点，20分】 2.设一个序列A[1..n]满足：存在i，A[1]到A[i]递增，A[i]到A[n]递减（存在i=1和i=n的边界情况），求i【新题，15分】 3.杨氏矩阵定义为：每个元素都比它的右邻元素和它的下邻元素都小，允许某些元素为∞，（1）O(m+n)删除元素，（2）O(m+n)插入元素，（3）O(n^3)排序n^2个元素，（4）O(m+n)查找元素【作业原题，20分】 4.G(V, E)满足：|V|=2n，对所有的结点v_i，d(v_i)≥n，设计算法求图的完美匹配并证明其正确性【上课原题，15分】 5.（1）写出快速排序的split函数，返回值t满足A[1..t-1]均小于A[t]，A[t+1..n]均大于A[t]；（2）如果数组中所有元素都相等，求快速排序算法的时间复杂度；（3）修改split函数，使其返回值p, q满足A[1..p-1]都小于A[p]，A[p..q]都相等，A[q+1..n]都大于A[q]；（4）根据（3），重写快速排序算法【快排优化，跟作业里的归并优化有点撞脸，但优化方法其实关系不大，20分】 6.证明顶点覆盖问题是NP完全问题【上课原题，10分】 **授课质量：** 老师人很好，讲得也还算清楚；算法引论这本书本身写得不错，水源社区还有电子版，平时要是有时间，可以把课堂内容和书上内容对着看~当然，我没有这时间，典型的平时造火箭+期末速通流思维，不过最后大体还是把书溜了一遍~ 书面作业只要写思路就行，我个人是磕磕绊绊遇到点困难，但借着AI也拿了相当不错的分数；编程题不算特别难，至少AI能替你写出来，想练码力就自己敲一敲，而靠AI薅分数也是相当轻松~比起CS2309那位神人出的编程题，无论质量还是通过难度，任老师的编程题都算亲民了。鉴于作业分数会直接折算平时分，建议先跟AI对一遍答案再交。 期末卷子延续了5道原题+1道扩展的老配方，打分也依旧严得很，详见楼上。

课程内容：好东西，属于是算法界的原味鸡，啃得动就香。 上课自由度：高，高到你可以在教室后排参禅，老师也不太管。 考核标准：严，严得像机场安检，你兜里有一粒灰都得掏出来。 授课质量：蛮好的，老师人蛮好的，讲得也蛮好的，整体就是那种“你说不出毛病但也不想给他磕一个”的好。 就是课件也较为完整，就是课件上有写表述过于口语化，口语化到什么程度呢，得供起来发给gpt翻译一遍才看得懂，属于是加密通话里混了点知识。 期末考试给分低，给分非常非常严，我6大题里面只有一个小题没做出来，别的都是一些小问题，都给我扣到79，79啊，这不是分数，这是拿小刀在我绩点上雕花。平时分只要作业好好做，还可以。但是作业做错是会扣平时分的，去和gpt对一下答案再交吧，别让手滑变成手刃自己。我作业成绩是98。

- 课程内容：复杂度分析、归纳、几何算法、代数算法、图论算法、P/NP问题等一整桌硬菜 - 上课自由度：极高，签到？什么是签到？所以一次都不去纯看回放也没人管你（x - 考核标准：30%平时（把最低的两道踹出去）+70%期末（6道大题全写伪代码，其中5道是作业原题或者课堂上唠过的） - 授课质量：高，老师上课就杵在黑板上画图推证明，讲得也挺清楚，可惜语速慢得像0.75倍速，再加上中午三节连堂，简直是催眠套餐，搞得我个人还是更配得上倍速刷回放 另外这个班居然连近些年的往年卷都扒拉不到，连线上版本都没在江湖流传，把老师自己都整惊讶了，复习起来属于是纯肉搏。下面就靠回忆今年的题来普度后来人，好歹让你知道题长个啥样： 1. （1）在单调序列里查某个数在不在；（2）在单调序列里抠出绝对值最小的元素【二分查找，送分到手软】 2. 整数n可以写成 n = x_1 + x_2 + ... + x_k 的形式，其中 x_1 ≥ x_2 ≥ ... ≥ x_k，这就叫一个划分。（1）把6的所有划分方案统统交出来；（2）求整数n的划分方案数【动态规划，作业原题】 3. （1）汉诺塔怎么搬；（2）给你圆盘当前的位置状态，算出它是最优移动方案的第几步，如果压根不在最优方案里就输出-1【递归，作业原题】 4. （1）一堆宽高已知的信封最多能套几层；（2）信封允许90°旋转时最多能套几层【排序+最长单调子序列，（1）是作业原题，（2）是加料版】 5. 已知顶点覆盖是NPC问题，问树顶点覆盖和偶度数图顶点覆盖是否有多项式时间算法【多项式规约，上课内容+作业题】 6. 给一大堆通话记录，两人有直接或间接通话就往一个关系网里扔，求所有关系网【建图+dfs，新题一枚】

课程内容：算法引论，就是把你请进算法的门，然后门在你身后缓缓关上。 上课自由度：高到老师根本不管你人来不来，签到更是查无此物，突出一个爱来不来、来了也行。 考核标准：70%期末考试+30%平时作业，平时分和期末分坐同一张桌子但分量明显不一样。 授课质量：不错，别的不吹，这点是稳的。 平时作业的难度不高，大多是拿课堂知识直接糊上去就能交的东西，得分也挺好看。老师不让补交，于是反手把最低分抠掉，剩下的取平均，等于白送你一次容错，而这学期直接给了两次容错，主打一个慈悲。除了平时作业，老师还会在头歌上布置编程题，这学期一共布置三次，每次5道左右，印象中老师说过占比5%，但成绩查询里查不到确切分数，这一点可能是记忆串台了。对比英文班和cyj班的同学，我听说的那几位说他们班平时分基本满分，而我们班的平时分是拿作业分数硬算出来的，可能会扣1到2分。 期末考核的题目基本全是作业题，所以老师给分严得像拿卡尺量你，每道题按算法的时间复杂度给分，时间复杂度不到位就酌情扣。作答要求写算法的简要思路、伪代码、时间复杂度，具体看题干怎么说。老师考前强调字尽量写小，不然空白处根本塞不下，卷面观感直接稀碎。每道题分值有10、15、20三种，所以要是哪道题没复习到位、正好不会做，这场考试就可能直接寄。 主观评价：老师讲课不错，每过两周会讲一次作业题，课前也会做准备，算是很敬业了。但对于分数要求较高的同学，建议去英文班或cyj班。英文班这学期期末考比较难，但平时分占比百分之五十，而且捞人力度很大；cyj班的平时成绩就不用多说了，期末成绩据说平均分85，具体没法考证；至于本班，期末会出一两道非原题，因为分值的原因，这题不会做再叠加老师的高要求，很有可能直接不得分或者酌情扣分（如果你不会的那道正好是证明题，那连酌情扣分这条路都没有了）。

课程内容： 一进教室，瞄见那块纯白的ppt, 就知道这是个好老师 上课自由度： 考核标准： 授课质量： 边想边讲，语速和板书都好跟得上拍子

自由度很高，平时作业是算法题，写大致思路即可，像在交解题意图而非作业。 教学内容多且杂，教学质量＝念ppt，ppt＝抄教材且不配图，跟白开水里泡了张说明书一个效果。 最重要的一点，给分低，很多同学八十出头七十多分，在意分数慎选。 选rqs基本是平时忙碌程度和期末分数的trade-off。

课程内容：算法引论，开门见山就是这味儿 上课自由度：极高，高到你可以把课当成背景音，人不听魂不听，教室里的你和宿舍里的你量子纠缠 考核标准：平时（30）+期末（70），ratio摆在这儿，别装看不见 讲课质量：中规中矩，属于那种挑不出大毛病但也别想立地成佛的水平 我拿算法和yyu的数据结构横向对比，两位老师上课质量其实差不多，没基础的同学认真听能听懂，但想熟练掌握还得自己下去疯狂内卷（大佬勿喷，喷了也是你对）。算法的平时作业跟数据结构差得不是一星半点，任老师平时作业只有书面伪代码，而且助教后期改作业其实不是特别细致，我复习时翻开自己之前写错的地方，好家伙满分，助教我哭死。任老师期末试卷还算仁慈，但给分较严，我提前较长时间写完还检查多遍，照样扣了不少，可能是改卷子时比较注意细节（雾）。总之作为一门算法引论课是不错的，但你要是想熟练掌握，还得self-driven，没人能把内功直接灌进你丹田。相较隔壁gxf的反馈，还是推荐中文班。

课程内容： 1. 《算法引论》整本，一字不落，全本，跟追剧追到大结局一样。 2. 机器学习基本概念（应该不考，属于买一送一的那种赠送品） 3. Computational Geometry 这块直接给你上强度：三角形划分、Voronoi 图，扩展得比我妈塞行李箱还多。 上课自由度：不点名，自由，来去如风，教室是你家客厅。 考核标准：还没考，薛定谔的成绩单。 讲课质量：emm，听不懂。虽然觉得老师讲得不差，但我一走神就断线，每节课都在神游，走神走的比WiFi还稳。 《算法引论》课本写得很好，一定要看课本！可以配套《算法导论》一起食用，双厨狂喜。 作业还是比较多的，每周 3 ~ 6 题，难度中等，很多题目你可以在 Leetcode 找到，属于是给你留了后门。 作业形式全为书面（文字描述思路 + 伪代码），没有 OJ，就硬手写，主打一个返璞归真。

课程内容：图算法、多项式算法、FFT等等常用算法轮番上阵，参考《算法导论》，大致就是照着那本书念。 上课自由度：高，不点名不签到，电子设备随便玩，来不来、听不听课都不扣平时分，简直是自由飞翔。 考核标准：作业分+期末考试，作业都是当天讲过的算法的应用，比较简单，作业分基本给得贼高或者直接拉满；期末考试六七道算法题，很多是课上讲过的或者课后作业原题(课后作业还会给解法)，但是改卷比较严格，一分都不多给，所以考试还得老老实实准备(我就是没好好准备，天真地以为能给点可怜分的那位)。 讲课质量：一般，基本全程对着PPT念经，所以你直接翘课看PPT也没什么关系，他也表示允许。