算法与复杂性 · 修读回执档案

课程内容： algorithms书上的内容，不过我没怎么看过书，书就是个摆设，我和它相敬如宾。 上课自由度： 高，完全不点名，点名是什么？不存在的。这门课是大二和大一致远一起上的好像，直到最后模拟考试我才发现这课有这么多人，人多到像开演唱会，而我一直在后台摸鱼。 考核标准： 30%平时 70%期末。平时作业的话有的还挺难的，难到我想当场退学，至少我不会，不过助教不会扣很多分，助教是活菩萨。今年期末只有5道题，往年证明题比较多，今年算法设计比较多，大多是课内稍微拓展了一点。 授课质量： 很高，是我进入学校两年以来听过最好的课，好到我想把这门课裱起来。老师真的巨好，好到闪闪发光，为人特和善，和善到像邻居家的大哥哥，下课也不拖拉，铃响人走。每次上课之前还会回顾上一节课的内容，而且这课知识分布比较散，散得像满天星，即使上节课没听，这节课也完全可以听得懂，这都能懂，你说神不神。我期末也就用一下午过了一遍ppt，本来觉得考得有点难，不过老师给分特别好，好到你怀疑他是不是算错了，像我这种菜鸡都能给到90分，真的吹爆，吹到气球都爆。

跑，别回头。 更新：果然很不幸。看看隔壁中文班吧，那边是天堂，这边是健身房的跑步机，跑断腿也追不上。

啊啊啊啊考得好难好难我人没了 陈老师真的很棒，讲得非常细致，非常推荐选，大学里为数不多上完真有收获的课。 就是我比较笨，学的时候总想喊一句：“妙~啊” 考试的时候只能哀嚎：“不妙” ______________________________________________ 好吧结果还不错，说难是因为4的欧拉和5的规约我都想了非常久最后才写上去，时间很紧，最后写上去也不知道自己写没写对那种，事后来看基本是没错的。今年和同学讨论下来整体给分是不高的，期末均分78不到，总评均分大概81，平时分基本要扣1分多吧，除非作业做得很好。

复习间隙摸个鱼，顺手给陈翌佳老师这学期的课堂饮水做个台账： * 第一节课：东方树叶乌龙茶口味(存疑，笔者没喝过不太了解) * 第二节课：东方树叶红茶口味（存疑，原因同上） * 第三节课：经典1升装康师傅原味冰红茶 * 第四节课：1升装康师傅冰绿茶 * 第五节课： 1升装康师傅蜂蜜柚子 * 第六节课： 1升装康师傅原味绿茶 * 第七节课： 1升装康师傅茉莉清茶 * 第八节课： 1升装康师傅茉莉蜜茶 * 第九节课： 1升装康师傅冰糖雪梨 * 第十节课： 450ml装统一阿萨姆奶茶，煎茶奶绿口味， 外加一罐可口可乐 * 第十一节课： 450ml装统一阿萨姆奶茶，岩盐芝士口味 * 第十二节课： 450ml装统一阿萨姆奶茶，茉莉青提口味 （笔者觉得阿萨姆还得是原味好喝） * 第十三节课：经典1升装康师傅原味冰红茶 * 第十四节课： 1升装康师傅热带风味冰红茶 * 第十五节课： 1升装康师傅茉莉柚茶 注：本学期由于清明节放假，周四的算法课被冲掉一节，所以一共只有十五节

课程内容：algorithms内容，建议一边抱着教材一边跟陈老师上课，一起食用更佳 上课自由度：极高，人完全可以不来，但陈老师的课确实很值得蹭一节； 考核标准： 作业和期末三七开，作业就是正常的书面题，去年的作业整体还是隐隐有难度的，不过助教最终给分大概都在9-10分？最后大体就是取个平均值发下去。 授课质量：现在回想，陈老师的算法课在计算机系真算难得一见：授课质量高，而且他非常在意你有没有接住知识点，几乎每讲完一个问题都要问大家懂了没有，这种好老师选上就纯属赚到呗。

- 课程内容：复杂度分析、归纳、几何算法、代数算法、图论算法、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，具体没法考证；至于本班，期末会出一两道非原题，因为分值的原因，这题不会做再叠加老师的高要求，很有可能直接不得分或者酌情扣分（如果你不会的那道正好是证明题，那连酌情扣分这条路都没有了）。

课程内容： #9421 那套菜单再塞进去 近似算法、在线算法和随机算法，活像自助餐最后还硬给你加三盘硬菜，主打一个知识量管饱。 上课自由度： 偶尔签到但貌似不影响分数，上课基本没有点名回答问题，但你要是不听课，大概率会对着slides进行一个眼神死的阅读理解，字都认识，连起来像天书。 考核标准： 42%平时作业+10%课堂表现+48%期末，这三件套摆出来，命运的齿轮从选课那一刻就开始转了。 授课质量： **上课方面**，老师讲课逻辑很清晰，内容也庞杂丰富，如果当成讲座型课程（没有作业没有考试），那绝对可以打5分，一学期认真听下来基础算法给你焊死，高阶算法还能顺手摸两把，内容编排的质量是真高，堪称知识界的军火展示。 **作业方面**，如前面的评论所说，有几次助教对我们的知识掌握程度认知并不清晰，导致根本无从下手，这是我上这门课比较折磨的点。作业在canvas上评分普遍比较低，但统计提交的时候分数挺高的，应该是有调分，属于先给你一刀再偷偷贴创可贴。 **考试方面**，期末基本覆盖所有slides和作业内容，很大一部分是作业和slides原题换模型，另外还考基本概念。每部分知识点占的题目基本平均，最好不要只押自己以为的重点，虽然最后几天疯狂翻动辄上百页的PPT也有点痛苦，那叫一个键盘翻页翻到手抽筋。 **给分方面**，平时作业调分，课堂表现出勤应该给满，期末改卷也比较宽松，整体给分对得起平时的忙碌程度，算是一份汗水换一份收获，没让你白熬。 整个课程助教参与度是我上过所有课程中最高的，课程整体难度也比较高，不适合水过去，但认真参与分数不会低。

课程内容： 算法加《计算复杂性·入门摄影版》。具体到分治、贪心、动态规划、搜索、最短路、最小生成树、网络流、图灵机、NP 完全性、近似算法、在线算法一锅端了，内容量大到后面越厚越像导游解说：来我们快速路过一下。有四次课后作业比较困难，跟硬核证明扎了堆，幸运的是助教巨热情，抓住助教老李一通问就能薅到精妙思路，大局观足够的人确实能从中收一堆技法圣遗物。 上课自由度： 有签到，但据说不计分；旷课可能整条学习进度直接断档，想飞掉是错觉。尤其某些浑身是劲的卷王，课上抢着答题，课间还追着助教狂聊超纲问题，必然把老师对大众真实水平的理解带沟里。 考核标准： 有过几次签到，算不算分不清楚。传言平时42%考试58%，组成比有点像减肥餐。作业共6次，每次均摊约4道大题，小题还会下崽。有些题是那种描述像小绵羊实际是暴龙的，有些题是看着像变形金刚其实是纸盒，作业和考试的压迫感不小。隔空提醒某位卷王同学别再催难，偶尔低头怜悯一下后进生。考试总计10道选择加4道大题，难度比作业体贴多了，但题量有点猛，手写了能当健身。这题比剑还致远的。 授课质量： 老师知识点覆盖到位，就是被卷王的超快抢答带成了“全村人都懂了”的错觉，语速直接起飞。习题形式多种多样，教具好玩得像拆盲盒，助教随机拉人上台当场传授，据说那是苏格拉底式的互动。感觉作业不是在课堂知识上盖楼，是在上面加修天线，平时放羊可能习题课就听雨声。总结： 综上，不太推荐水平没那么硬的选手往里挤，此课绝不是普度众生的水课。不过底子强的仍能在里头淘到不菲，等成绩放榜再来续写。

课程内容：算法与复杂度大礼包，贪心、分治、近似算法等等都往里塞。 上课自由度：低，有小测有签到，虽说不点人。 考核标准：42平时分，58考试。 授课质量：中。 高老师讲课其实还可以，但咱班蹲着个竞赛生，上课老爱接老师话，高老师就老以为他听懂了=全世界都听懂了，我上课大部分时间脑袋里全是问号，得靠回放才能勉强吊住。 必须吐槽一句这轮的助教李某某，出lab题目纯靠自己脑补，一次作业我肝十几个小时都想不出，一问竞赛生才知道这叫竞赛初级难度。还不给答案，恶心之最——出这么狠的作业，没做出来就咔咔扣一堆分，都眼瞅要期末考了还不给个答案解析。还好后面高老师出手，他才没接着甩那些鬼题目。

课程内容：5 上课自由度：4 授课质量：个人觉得高老师授课还是很可以的，讲的比较细致，讲课方面还是不错的，细得跟拿放大镜看代码一样。

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

课程内容： 1、Computation and Complexity, Sorting, Searching, and Selection. 2、Divide-and-Conquer：Mergesort, Selection, Master’s Theorem, Sorting Network, Zero-One Principle, etc. 3、Greedy Approach (1)：Interval Scheduling, Interval Partitioning, Minimum Lateness, etc. 4、Greedy Approach (2)：Optimal Caching, Coin Charging, etc. 5、Matroid (1)：Independent System, Matroid, Example: Greedy-Max Algorithm, etc. 6、Matroid (2)：Min-Max Conversion, Unit-Time Interval Scheduling, etc. 7、Dynamic Programming (1)：Weighted Interval Scheduling, RNA Secondary Structure, etc. 8、Dynamic Programming (2) & Linear Programming：String Similarity, Duality Theory, Simplex Algorithm, etc. 9、Amortized Analysis：Aggregate Analysis, Accounting Method, Potential Method, etc. 10、Graph Algorithms (1)：Basic Concepts, MST, DFS, BFS, etc. 11、Graph Algorithms (2)：SSSP (Greedy & DP), All-Pair Shortest Paths, Flow Problem, etc. 12、Graph Algorithms (3) & NP-Completeness (1)：Maximum Flow, Minimum Cut, P and NP class, etc. 13、NP-Completeness (2)：Reduction, Proofs. 14、NP-Completeness (3)：Reduction Examples. 线上学期的优点是老师用中文讲课了，换成英文我怕我会当场失聪。本来选的是中文班，没选上，所以只能含泪英文班。 作业本来有7次，因为线上教学进度滞后所以减少了一次，分数占比没变。这学期不硬性要求latex了，用markdown和word都行。每次作业3-4个大题，本人感觉还是很难的，经常需要四处抱大腿，但是不能抄袭会查重。错的不太多的都可以拿A，本人前4次是A，后两次错的有点多是B，像坐过山车。 Project是"Resource Scheduling Problem in Hadoop"，但实际上跟Hadoop关系不大，还是用C++，设计离线的调度算法。老师把建模做好了，助教把代码框架也给了，最简化的做法是只要设计函数、填函数，想卷也很有卷头，本人属于能力有限的那种。三个人一组，我们这组从第9-15周每周开一次组会，最后快做完的时候开得更勤，在这project上砸了不少时间。 期末考试题型为选择题和填空题，选择题3.5*10，大题4个，对我来说很难，卷面没及格，幸好期末占得少，属于小命保住了。 最后总评的平均分应该是低于陈昱佳高于任庆生。 老师人还是很好的，我觉得作业折不折磨人取决于助教。我们这学期中途换了一个助教，新助教出的两次作业都有编程题，交的代码他会放在OJ上测，还会查重，简直是双重拷打。 上课自由度：低，老师讲一段就问大家懂了吗，懂了的在评论区刷数字。每次上课都会开摄像头签到，主打一个云上盯防。 考核标准： 10% 课堂参与 35% 作业 15% Project 40% 期末考试 讲课质量：简单的地方我能听懂，讲得不错；难的地方因为听不懂，所以我也不知道他讲得怎么样，薛定谔的讲课质量。

课程内容：Sanjoy Dasgupta的Algorithms，就是这本。 上课自由度：高到可以原地蒸发，从不点名签到，你不来它也不知道你来没来过。 考核标准：作业30%，考试70%。作业大部分都是Algorithms的课后题，小部分自己出，有点难度，但最后只按完成程度给分——也就是说交了就赢了。考试比较简单，把作业题都掌握了绝对没问题，这学期就考了非常基本的东西，老师原话是“（每道题）重要的是知道考的是什么，哪怕没有做出来，也能得很高的分数”，翻译一下：看懂题目比做出来更值钱。 讲课质量：非常非常高，高到能拿去发电那种。Algorithms这本书本身脉络很清晰，前后呼应，内容不多但是很细致，insightful的观点多到能开盲盒。老师每次上课都会用一节课左右复习上次课，上课极其注重同学感受，随反馈调速度，经常“如果觉得哪里有不明白的地方可以随时打断我”“有没有什么问题”。因为讲的就是这本书，推荐先看书，没看懂的地方再听老师解释，会盥顶——哦不，醍醐灌顶。 另外这门课是和john班合上的，陈老师很多年前开过，但最近几年算法课都是另外两个老师在上，今年属于强势回归。不得不感慨致远的师资是真的好啊，完全碾压cs。

讲课非常清晰，学到的东西够打包带走，只是今年线上没有把课上完，最后缺了一节课讲量子计算的（不过量子物理补上了，赢！）。最后考得也比较简单，有部分原题和一些简单题，但不是简单直接copy，是那种包了层皮的简单。最后大家均分都很高，选到就是赚到，属于是购物车清仓价捡到宝。

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

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

课程内容：算法概论那一摊东西 上课自由度：高 考核标准：3 7开 讲课质量：高

课程内容：时间复杂度计算、分治法、贪心、动态规划、线性规划、摊还分析、图算法（DFS、BFS、最短路、最大流）、NP与规约——一句话，算法全家桶，NP规约是那根最后压垮你的薯条。 上课自由度：疫情期间线上上课，那自由度当然是拉满，人躺被窝里都能听NP规约在你耳边念经；线下期间嘛，不敢保证，别问，问就是薛定谔的自由。 考核标准：10%课堂参与+15%project+35%作业+40%期末考试，这配比一看就是给你留了活路。 讲课质量： 当初看19级学长学姐对高晓沨老师的评价，低到我以为这课是荒野求生，本来选了另一个老师，结果手速不够没抢到，兜兜转转还是落回高老师手里，一学期下来——嗯？没想象中那么地狱啊。 先说6次lab，跟去年比简直是良心发现：每次lab大约只有3道题，个别题目下挂2到3个小问；latex是鼓励项，你用word也不会被扣分；没有任何可视化要求；也没有那种能把人送走的繁杂作业（比如去年那个图灵机。。）。我盲猜lab是助教出题，上一年那位助教大概是放飞自我放到平流层了，才整出那种恐怖难度。这一年只有第4次和第5次带编程题，比较繁杂，我两次都写了400行+，第4次lab编程难得离谱，跟大佬对完线才有思路，第5次lab编程较难，基本是书上若干算法叠罗汉，不过也算是这学期为数不多的编程体验了。每次lab只要没错得太抽象，都是给A；但抄袭这事千万别碰，有查重，查重面前人人平等。 project方面，光题目描述就7页！全力做的话，三人合力，编程加论文加可视化（可选），大概要三天完全投入，做起来一股美赛既视感。project的ddl不是硬ddl，后面还有个约15min的pre（听的人只有助教），感觉只要pre前交都问题不大。大多数同学走的是贪心+随机算法路线。做着是烦了点，但换来期末只占40%（另一个班好像60%），总评直接有了安全感（高晓沨：“如果不出意外的话，大家总评都能达到80+的”——希望不要出意外，flag我先立为敬）。 上课方面，我个人觉得有些地方讲得不算非常清楚，偶尔也有讲错的时候。课上经常问听没听懂，没人回就再讲一遍，最后几节课直接点名问哪里不懂（NP规约，太难了。。）。总体课程难度较高，不认真听或者课下不额外花时间，基本拿不下。很多同学的状态是：上课勉强能跟上老师思路，一做题就想不出来，期末复习更是难上加难。可能算法本来就这样，毕竟也是前人智慧的结晶，上完这门课，自己以后适不适合做算法，那真是明牌了。本人亲测：平时不听讲，想靠期末三天掌握全部内容，不太现实。。。。 多次拿best lab的话，会收到加入高老师实验室的邀请。 每节课前都有签到，我举着自己的卡片，被老师或助教拍照截屏签到，仪式感拉满。本学期一共三次小测，其中两次属于有手就行，另外一次——有手也不行。。。。不过还是比较好蒙的） 这条评论写在算法考试前一晚，等出分后再来补考试和分数的评价。 出分了，期末扣了4.4分（换算成卷面是11分），project扣了0.7分，整体已经很满足了。期末考题不算很难，相当一部分是PPT例子换个表达，或者平时作业题直接拿来考。但我没复习好，很多东西没想起来，最后的NP规约有点难，也没做出来。分数导向上，比较推荐高老师。期末占比很小，分数很有保证。 听说隔壁平均分更高一些。

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