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

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

课程内容：复杂性问题，图论，贪心，二分，DP，LP，网络流，NPC问题及规约——一句话，全是硬菜，端上来就是让你当场把脑细胞按斤往外卖的。 上课自由度：极高。没有**任何形式**的签到，属于是老师给你自由到你怀疑自己是不是走错教室了，来不来全靠自觉，签到？签什么到，签到在这门课是不存在的物种。 考核标准：平时/作业 + 期中 + 期末——经典三件套，一个都跑不掉。 期末考试比较困难。我的印象里面比较难的问题有： 1.clique到dominating set的规约。 2.subset sum到partition的规约。 3.O(|V| + |E|)时间内网络流的eliminating edge问题。 4.一个区间 [0,n-1] 上有若干个点p1 ~ pm。每次选择一个点 pi，就把当前区间在 pi 处分裂成左右两个区间，同时 cost 增加刚才选择的pi分裂之前所在的区间长度，直到无可再分。求cost最小值。 ——就这么说吧，考场上看到这几道题，你会怀疑自己复习的是不是另一门课。 but给分**非常**捞——捞到什么程度呢，就是前面被题目锤得人事不省，出来一看分数又感觉自己好像还行。 一定要好好复习作业！很多原题或类似思路——这行字请刻进DNA里，作业就是你的复活甲。 授课质量：高。陈老师讲课思路很清晰——清晰到你会一度产生"我好像懂了"的错觉，然后考试把你打回原形。

课程内容：各种算法，分治、贪心、dp、图论、P、NP，一锅算法大乱炖全给你端上来。 上课自由度：高，但有线下宣布的考试，不来可能直接缺考，属于自由过了火。 考核标准：期中、期末、平时成绩。 授课质量：高。期中比较简单，期末有点难，也可能是早八考试脑子还在被窝里没醒。给分很捞，就算想不出来，把学过的步骤写一写也能薅到不少分。

课程内容：好难啊，复习破防了…，已经在破防和重新破防之间做往复运动 上课自由度： 考核标准： 授课质量：

线性代数先修用户返场报道。这门课的评价区一看，期末给分总体貌似不太行，但陈老师那就是一台永动机式的讲课机器，讲课足够好、人格魅力足够大，对数学和计算机科学热爱得离谱，听说数十年如一日每天工作时间不小于8小时，课是真的能学到东西，甚至有其他专业的同学来蹭课。这个学期加了一次期中小测，还比较简单，而且有二十分的附加题。之前上线性代数就清楚陈老师从来不会点名，所以我经常上课时间睡午觉然后之后看回放www。Chen Sir经常说的一句话就是：**如果你没有理解，千万相信那是因为我没讲明白。** 想划水的不建议选，毕竟无论是理解slides还是考试都需要一定平时的努力。但是谁会不想听水平高且温文尔雅Chen Sir的课呢。二编：期末有点难，但是老师给分非常捞，赞！给后来人的建议：自个去按照slides的内容找几道动态规划和规约做一下。感觉考场上要做一道比较难的规约很难想出来...

课程内容：凑合能用 上课自由度：放养级别 考核标准：作业扣分不讲武德。本期考试差不多是全师门里最难的那套。成绩出得像难民徒步，愣是一点分都没捞。

在这学期专业课给分拉满、人均起飞的环境里，我喜提3.7哈😓排名像坐了滑梯一路俯冲。 来，细说：高老师上课确实干货满到溢出，跟着听也会产生一种“我掉进知识缸里了”的错觉，但想凭这一学期就把那些精妙算法全盘刻进DNA，难如登天，最后还是变成一套面向真题的求生模式。 我每节都人模人样地听，自认脑回路也不是二手货，可能是这门课的仙气我吸不动吧。作业难度在地狱层，考试照样满屏写不出来的尴尬，作为一个标准人类不是天选之子，真的很抱歉。 感觉这课没捞人，平时成绩难顶、考试成绩更是冰凉。作业按完成情况扣分，可我认真做的才会错啊，这不明摆的吗？难道要我冲平时分去抱ai大腿当复读机，回回交100%正确版吗，那这作业的存在是用来看的吗，手还练不练了？ 考试更是，干瞪眼的题我都写满上坟式堆砌了，最后卷面一坨原味[目测连捞的游标卡尺都卡不住]。是我写得真就这么烂吗？您这是捞都嫌我太滑手。还是那句，作为一个凡人，点亮了灯熬了夜还是没达标，again我很抱歉😓 绩点出来后，我整个人道心破碎得像拉满缺口的马克杯，我只想做个自带幸运色光环的普通学生，没点祖传天赋难道就永久失去抢奖学和保研资格的门票了吗，复习夜熬的每一滴油仿佛都成了群嘲。 总之，天才随便进，终归能啃点东西下来。纯度跟本人一样挤普通池的在意给分的请谨慎摇号，看评论说别的老师给分更温和，老高的场子是献祭流玩法——适合那种拿知识不回城、分随它去的公开课。

纯纯细节怪兽，平时作业那是小处见真章，一毫米一毫米地贴着你扣分；考前谁说的不会特别抠细节，我信了，估摸着也就是安慰性地说说吧。

**课程内容：** 期末对着书和笔记复习的，基本上是按《**算法引论：一种创造性方法**》来的 第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道扩展的老配方，打分也依旧严得很，详见楼上。

课程内容：Algorithm书（UCB CS170），一直干到NP问题 上课自由度：很高，点名这事儿不管（我个人觉得刷回放能把老师讲的一些推导细节嚼透） 考核标准：30平时分+70期末，平时分按作业给，作业均分9.8/10左右；期末感觉卷子出得不算难，均分大概82多一点，Chen Sir挺捞的 授课质量：非常高！Chen Sir讲得非常好到离谱，我感觉是把数据结构和相关算法全用一套新皮肤在我面前重刷了一遍，复习的时候捋了一捋才发现讲了那么多、背后居然一条逻辑串着~虽然没有算法导论那么硬核，但真的让我一个数学很差的人尝到了算法的巧妙 Chen Sir特别喜欢严谨证明，还爱捉书上的小bug或是书上没证的自己证给我们看，好让我们理解更深（不过Chen Sir自己出的证明也都挺难的），尤其偏爱LP/Dual和Reduction，讲得也贼清晰，最后两章大家可以认真听听

课程内容： 讲得非常好，一堆东西直接从数学的观念给你凿穿，不是喂饭是帮你开天眼。 上课自由度： 考核标准： 给分很高，高到像在做慈善。 授课质量：

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

平时成绩生抠硬扣4分（签到那是满的，应该是作业背的锅），一路扣到90以下，哈哈。平时作业批改可太“认真”了啊。人生头一回见到这么负责任的老师和助教！👍那真叫一个可敬！👍👍👍

给分低，跑，腿给你跑细了都别回头

都2025年了AI coder满街跑，这个班还坚持全手写证明，任务量比隔壁头歌上写代码大一圈，硬核到像拿毛笔填机读卡。 另外课上不知道为什么飘来很多大一学生，画风堪比幼儿园开放日，于是大量时间花在复读离散数学和数据结构里已经讲得贼详细的内容，仿佛在给大学生补胎。 但讲得比较清晰，也会安排习题课。为了陈老师全部课5.0的评分，勉强给个5，属于信仰充值。

课程内容：高老师slides上那套（详情请翻阅前面同学的发言，我这儿不搞重复投喂） 上课自由度：高到离谱，这学期签到？不存在的。就一次课上做了一次quiz，属于“你只要知道自己在干嘛就能顺手做掉”的那种。不过大多数同学还是乖乖去上课了，可能大家骨子里都是自律型选手。 考核标准：42作业+10平时+48考试。平时作业量不算大，就是有时候脑细胞要加个班，助教改得可能比较严，但最后登成绩作业部分应该没怎么扣分。 授课质量：还行。老师是擅长授课的，但可能效果并没她想象得那么好，属于那种“我讲得很嗨，台下静得像深夜图书馆”。个人感觉大部分地方偏慢（老师还怕大家跟不上，然而没人回应，空气都替她尴尬），个别地方又突然飙车，比如斐波那契堆（虽然不考）。 考试和给分：今年考完大家都挺破防的，题量比较大，部分选择题和大题有一定难度，相比中文班成绩可能不占优势。最后出分之后了解了一下身边的同学，感觉有捞但是没有期待得那么捞。个人建议这门课在卷子比较难的时候首先保证选择题正确率，大题写了有捞人空间（我大抵就是这样被捞起来的

讲课风格：高老师属于推土机式推进，slides从A点到B点脉络堪比高速护栏，配套资料塞得跟搬家纸箱一样满，备课那叫一个内功深厚，经常PPT都不翻就把下页要讲啥直接口头咏唱，稳得像老狗。不过偶尔对数学之美上头，硬给你布道，我这边个人信条就是Understanding is all you need，抓住核心idea就收工走人；还有她爱反复问“跟得上吗”，但班里气氛龟息成那样，这反问基本等于往一潭死水里扔石头——咕咚一声，更安静了。 作业：难度适中，听懂了基本能砍掉大半，但每次都要埋一道题卡你脖子，而且每两周一次，workload算是毛毛雨。 考试：题型直接换皮，和往年题长得跟失散多年的亲戚一样对不上号，难度体感是陡增的，我本人速通复习只捞了个大概，上场发挥堪称灾难片现场，好在老师也捞了一把，再加上平时分，最后分还不算难看。 速通看回放那会儿才发现，好多东西一旦整明白了是真有意思，认真听能薅到不少真货。

这门课的内容和MIT的算法课简直是双胞胎，只不过多塞了个拟阵讲座和图灵机，作业整体难度还行（其实就算真实作业分不高也会调整），平时分上来看老师比较仁慈没怎么扣，但期末卷子属于是火星难度，没做完（期末85），导致总评不高。总而言之不建议除了永强班以外的同学选这门课，任老师班上的分都会比这略高。大佬可以忽视我的评价，因为班上确实有不少同学95+（大概有个7，8个同学满G），那些同学水平非常高他们的评论也会与真实体验相差很远，我的评论算是站在一般水平同学的角度进行评价（总评的均分在90左右）。

课程内容： 基本就是抱着《算法》这本书念经 上课自由度： 自由度冲破天花板，我记得下半学期有几回教室就来了20个人左右，空得能打羽毛球。 考核标准： 三七开，30%作业，70%期末 授课质量： 没得黑，讲得确实好，清楚到像开了字幕，老师本人也魅力外溢。 但对我这水平来说，考试和作业都带点凶，我每次算法作业得磨半天，时间黑洞实锤。期末当时体感还行，成绩一出来直接拔凉，后来去问助教，助教也超细地把每个扣分点一条条摆出来，我看完确实心服口服，不过话说回来，我觉得期末是真没捞，就是实事求是甚至有点严地批，这次期末平时分好像在77左右，期末在81左右，我觉得不算高。 另一个美中不足：助教没给作业标答。我其实跟助教反映过，可能我俩沟通岔了频道，我本意就是想让他把自己写的证明或者伪代码掏出来当答案给大家看，这样期末答伪代码也能更规范更有章法，大伙复习也能轻松点。 总之这门课瑕不掩瑜，非常推荐。

课程内容：大致按算法书的目录顺序往下推，导航一丝不乱 上课自由度：极高，从不签到。老师中途说教室摄像头能看见出勤率（可能对教师有影响之类），但依然咬牙不签，硬气 考核标准：30平时加70期末，平时作业好像截止后还有一天补交，再没交上就等期末一起清账，补交按百分之八十计成绩。平时作业个别题是真的阴间，但主要按完成度计分，没写出来写上思路后十分给了我九点三。考试不算难，想满绩可能有点难，今年五道大题各20分，两道半可以算原题，给分还算慷慨，有思路就有分（虽然我们班均分好像没往年那么高，但是过应该很容易。总之能选陈老师基本必选 授课质量：极高，听课基本不会出现老师讲完你还一脸雾水的情况，主要因为讲得有意思，不会听着听着魂就飘走了。老师人也特别好，会问学生要不要慢点快点、哪里没听懂这样