董明凯 · 高级数据结构修读档案

PPT上的代码我原样Ctrl+C、Ctrl+V，跑不起来，真的谢谢你啊，临考试了给我整这出，并行的玩意儿你让我怎么debug，我拿头debug吗 这门课更绝，homework、lab、project三件套齐活，写代码我认了，可每一个都要配一份报告是不是有点过分，一学期下来13个hw，每周至少搭进去一个下午敲代码，还得杵在那儿硬测数据，我这是在复刻线上电路实验吗 哦对，还整了个什么作业倒扣分制，你也知道这课任务堆成山，hw的分都快塞不下了是吧

### 课程内容： 1. 负责嘴炮输出的是戚正伟老师 2. 负责真刀真枪上机的是董明凯老师 ### 上课自由度： wuli戚老师，属于点名的忠实信徒。canvas上点名（中间有一次还祭出了纸质点名版本）+课上随机抽取幸运观众开麦回答问题。 ### 考核标准： 1. 期末考试收官一刀 2. lab拦路虎*4 3. 神秘project*1 4. 周周有作业（做得不行还倒着给你扣分，阴间味儿很足） ### 授课质量： 第一堂课讲的是跳表，本人开着全力试图咬住节奏的尾灯，结果嘴角先松了，当场车毁；课下花了整整一个小时啃完隔壁清华的教科书，把作业叼回来完成。 从此往后，我和听课这件事就永久分手： 1. 老师给的饭本来也不是很好嚼，也许有口音加成（？），听感上老师的音节像是泡在果冻里，费劲，费劲。 2. 另外授课素材给人一种从隔壁借来的桌椅感觉（书和课件都），顺序也不是顺着来时路，东挖一锹西掏一筐，课堂就欠一个"为什么我现在要出现在这里"的注解，不过据说院里自己那套新讲义已经在编了，下一届或许就能抬着头看黑板了。自学路径大概是下课自己发起的搜宝之旅（清华教材/csdn/github随便哪个垃圾桶里翻武器）。 3. 抬头率低到什么地步呢——大概是这门课的默认背景线程了，码类的课通病，也不能说什么。 4. 某周的作业布置是kruskal的编码任务，还是并行的串行加并行版本，作业要求的原话是参考"授课内容"给答案 唯一的麻烦是你参考对方发的课件和讲义，抄完后能闻到里头的代码是可以自行烧焦的bug风味（并发错误已在原地等你签收。？？？）这逻辑课上不好解释吧？真要这么印版的讲义当传家宝传下去吗 【外部来声】见某学长说完这个才明白：这版本的代码去年就是bug阵地了，删啊修啊没有人手上来过吗喂…… 每周的作业量大概可以让每周日历密成写python模式的考试贴，每当刚开新课的时候尤其重听。lab和project拎上来后，在这门课上确实被"学分刺客"的标签紧紧地致敬了一遍。 不过既然讲到收获的后半句，撸完这些代码，感受上是开了技能上限的。（尤其是这个project，pain值拉爆但是practical地让你把它内化成为一种情绪价值。） 给学院的一点建议行李放在这里：如果这股工作量不减，那就每两周多给安排2节加餐制作习题秀吧，顺手把学分也往四分的格子上一抬。 —————————————————————— 在下头有位同学的评价，看完了我由衷地有点难绷，作为交过学费的过路人，往评论区磕一块小蛋糕： - 直接牵手和ics，就有些脱离坐标系了，ics的各位老师那个教学武当，放谁来我都是狠狠地点头。ics认真听讲课后回放的自修比例很高，而戚老师的课，即使是回放环节也能把你原地看到脑子没电，直接给出听不懂判决啊！确实是自学模式从开始到全章收尾。

上课自由度：低，每节课点名，哪怕点了十几个只来了一个，签到场堪比大型行为艺术 授课质量：一言难尽，不如听djh的网课

课程内容： 100 上课自由度： 100 考核标准： lab project hw test 授课质量： 较低 我就纳了闷了，用清华的ppt，那为什么不直接把邓俊辉的课放出来，人家讲得清楚多了，这操作好比用米其林菜谱炒了个糊锅巴

不怎么地，感觉不如我上我讲。 2023.4.20 口头点名，点了十来人到了一个，差评如潮，出席率比我早八的意志力还稀薄。

讲台上的输出大约是在用摩尔电码授课——听不懂，只能点头，并被猝然点名回答空气；人也被逮到黑板上罚站。lab文档写得比用过的草稿纸还朦胧，无旋treap这东西纯属本人靠各路论坛考古才拼出它是棵什么树，代码量天杀地多，辛辛苦苦点灯熬油学完之后发现掌握的不过一点点边角料。

### 太真实了这老师真的疯狂热爱点名，对于自学的真的不友好（而且自己看书比他讲的明白多了，看了刚刚的一个评论有感）但是后面好像已经就软了，认清了自己讲课质量的事实和学生作业写不来的现实 ### 2023..4.20 那个点名啊，点十个来一个，再点下去老师自己都得尴尬到脚趾抠穿地砖，这个操作真的建议立刻纯元皇后级下线。 课程内容：跳表、红黑树、kv-store、等等持续更新，一个不落。 上课自由度：签到、点人回答问题，答不答的上来应该没关系人来了就行，主打一个到场就有分，灵魂可以暂时寄存寝室的被窝里。 考核标准：平时作业不算分，不做扣分、4个lab+kv-store、听到没，作业的命是白干。 授课质量：这老师（戚老哥）讲的不太行啊，反正在我这里是真顶不住，就前面也有个评价说了，我回来看回放看不懂的地方琢磨半天，才发现他说的前言不搭后语。严重怀疑上课前连ppt看一眼都没有看，然后上课就赶鸭子上架去讲，尤其是数学公式的推导不知所云，那个程度就像是拿外卖小哥的配送路线给你证微积分。所以不如自己看书，他给的这个路线还是值得参考的，这些数据结构都是之前那平台班没有的数据结构内容，正好补上了。【补一句ppt也好丑，严重拼凑hhh，美观交大倒数级ppt，像是三天没睡觉临时切的好几份论文往外倒】 但是这课lab质量摆在那的，是另外一个老师设计的，刚写完kv-store（预告：文档里面有些没说的东西要自己思考，多看几遍文档，但是要思考什么我这里就不说了(*^▽^*)，我de了一个周末才发现的几个问题略略略~ 才不在这里说呢~，最难的是归并，那的bug最容易出现~，解决方法把level-0开到正无穷，测试没有归并的情况，否则就是归并的锅，我怎么说了这么多了呜呜不说啦~）这一part我尊之为“良心全押lab上了”。 但是把你要说那个文档，他写的真心不好，尤其是在最后跟你提一个要求kv-store要适应不同的缓存策略，幸亏看了一眼不然写完了发现那是真的要爆炸，直接重构起飞，起飞到平流层那种。还有平时的lab，昨天刚发布了⽆旋Treap的lab，文档写的真心不咋样，我在那个机房看了一下午都没看懂，东西说不明白全靠我自己猜测（也不知道哪位大神想出来分割树还有多种情况的，反正我在机房看的是一脸懵逼跟着这个PDF文档），下午跟一个石头画符一样，晚上一口气debug到四点钟发现搞不定，第二天拿着笔纸画了半天模拟各种情况，中午路上脑子突现灵感一现才想起一个可能的问题，成功Commit，仿佛在硬盘门口捡到了一张二维码。 然后吧吐槽一下，就你会发现他lab做的跟上课讲的，那突出一个：**关系不大**，两拨人一个住火星、一个住水星。 - 首先lab0不做跳表，也不知道是怕抄袭还是怎么滴，导致我kv-store严重负担++，之前跳表写的bug修了半天才修好，他这学期整个什么稀疏矩阵当lab0，这不连个普通的oj题都不算嘛，还不如扎实写个跳表，还能有帮助，像是一份温暖的点到点的扎实感情，愣是不做。 - lab1写的一个什么东西啊，那个⽆旋Treap，唯一的关系就是lab做的是个树，然后课上讲过红黑树和伸展树，重复点就是tree仅此而已，没了。[还我豆豆龙]你懂那个心情么。怀疑可能是看了个论文然后把人家代码挖空了然后就发下来让我们写，好吧，也不是不行，但好歹把文档写清楚点啊喂，不然人家跑测试还得从纸片里扒作业边角料呢。 - 后面的待更新 测试数据、评测脚本什么的都很齐全，设计很好（但是第一次lab的评测脚本有bug，有人群里面提出之后才反馈，作业里面的模板代码也有一次有问题，怎么感觉写的不太行的样子，摆上去的盘子和吃完之后的盘子不是一回事啊兄弟。 哪怕高中学过信息学奥赛的我觉得可能也不是觉得这课这么简单吧，有点考验代码功底的，代码量全课程推测一下可能~4000+，还算不错的一个课，也有很多人旁听。**平均每周起码半天时间写代码debug加报告，有点难顶**，一学期下来键盘的键帽都快焊上手了。 课程结束后来更新仓库链接 ~ （自认为是git管理的最好的一次仓库了，可以理解这个自信是硬核手工给的） ## 补充吐槽 15周来个什么并发的Kruskal算法作业，上课讲的代码都是错的，跑十几次就一次能出结果，其他都是死循环。这一周的体验可以简称灵异事件：给你材料指望你搭棺材本山。**真的不会并发可以不讲，别拿个错误的代码分析整半天**，还耽误我期末周的时间给你的讲义code去debug（我他喵的信誓旦旦的复制代码复制了半个小时，本以为一路顺风结果还没跑几千的数据集，跑个9个点的直接卡死了，再运行了十几次才有一次能出结果，好比用榨汁机运行跑酷游戏），一天天的熬到早上三点的人生，一箩筐苦说不尽[微笑]。本来大二下的压力就大，你还来个错误的东西考验我来一点一点改。。。。下降到2星了，顺便祭出经典艺能：跑第一个在跑代码的同学大概是有罪过。 哎哟你干嘛~ ### 吐槽教材 首先那个清华的数据结构教材也就那样，楼下有个说的有理，花里胡哨的，古龙玄虚，我又不是来上哲学的，一堆引经据典，我随便找个知乎博客都能讲的比你这书清晰易懂。关键是这个电子书还一堆缺页的。看着看着一半就没了，这就有点多了吧老师。唯独你要说内容全一点详细一点，是那确实，跟个箱子一样基础的就不要撑着了，交大那平台数据结构一本书讲了几个最基础的直接不讲了，后面关键的算法数据结构都直接没了。 再吐槽这个自编的教材，每次复制代码都在考验我删除行号的能力，直到我发现了用正则表达式删行号那是真的快，人生打开一扇窗。然后这个自编的教材，我还是建议找几个有并发编程经验的，把你程序多跑几次再出书吧，你自己的代码你自己拿过来跑一次都得红温。 ### 吐槽作业 烦的一批作业多，每次都有有一种要交作业的压力，一周接着一周平均普通每周放炸弹似的。心里由衷的热爱都被打压打成粉底，有的烦的几次作业还要写代码。写完代码可能还不给分半个啊，那到底。写的时间不算长，但是提交还要再写个报告，基本上是下午没了或者一个晚上直接过去了，周末是用来清摊子的，不是用来玩的，这种最想报警。作业前前后后一共12还是14次，你说算算也行哈，数字和堆得似铺得山压得。而且最离谱的是**作业不算分**，不写会扣分，这不是自助吗还是监狱累加链？最后一周还整个错的代码。。。要是平时分给60我还乐意一些，这剧我真的不想这样开播。 ### 期末寄巧 总结了一点小规律和寄巧，不保证可以用，但是仅供参考 - 选择题必考一题KMP next数组，记得复习，时间复杂度也得看，今年考了跳表 - 排除法做选择题非常快乐，有些错误一眼就看得出来。基本都是特别基础的概念，倒不会有ppt上面很抽象的东西。（比如BF过滤器也不可以直接删除元素什么扯淡一眼就可以过了。老师说不作就不会死。 - 红黑树真的没必要死磕插入删除，几乎不会考，了解概念算法就好。 - 问答题六个，第一个考跳表/AVL/红黑树那几个几种数据结构优缺点比较装盘里，认真在作业里就好，大可能。二、那个伸展树旋转，本质就是花式搬家具或物归原位，转到取出来的所有父边旋转图上升到底就好，。第三题KD-Tree那几个题几乎都有，即画分界线，等送分的路过，只能期望它是每年例行公事走过本就有给分宝丽来的转，算法会转但要尽力爱过必见眷顾就好；。大第大题送就班不只有 Dijs 那种的取路径拿手及会打眼睛看着点得“这条路的办法办法。”等最末题随机个题随机气的话分。大题好好复习包括Project，基本上来自小的考点问题和项目还有再拿出着到考点那些走者再来一个个老题你的概念或学习已讲过到抓黑黑白什么的看ppt里都能；画个圆啥的那就很稳当得相当拉满，来点天时对地利用看project的算法随来像那看看lsm和...反正存够讲就大概率得了会懂的自己推东西比如L&Merge节点去log压缩拉很类似的题目。那个计算与推理一被拉伸做，白夜也都通通过这类几个课且讲算证难值已为都顺自动写下来没毛病当全过已得的思虑好能拿分和试出来，因为都要确保各种消息才能并起来，后面的大题都是几碗怎么s三去。像拉练习只lab细节熟悉一遍上课堂必要没问题基学一下什么都过的打走！ （本人是过来标记去得差不多只写刚好考场看几句几乎这道题比较白担心后面翻Lab就能写不太表完个比如写压个SSt，项目结构，丢分；比如LAB就个人也经验计算题等体表如信息L内但整个数结构和推与并行的大类项等考试到最其实就很多相关者题都哪必须搞定。白小推导慢慢做进推导量也大多能顺。像已总结。） - 并发的东西基本上ics好好听了就没什么大问题，包括课这次布谷鸟哈希的考变用等伪代码这里学勤分就来自那一些多的位。 - 这么一说一张卷子都快回忆出来了乖进去 - 总结：**且，认真写平时的作业，上课听不听无所谓，听到多点听当然多听一点也不妨，反正课件内容也未必能有多大区别收获的。你可以听你就去听，不想听想摆烂你去改命前事记得看。想拿学分绩点先写作业不要去睡觉保平时的完成而且多半考试题平常道作业好和易参考命！作业写写完打完作业最后的先讲着只你能答开动过。把学习学好它平常扎实的写随大可能不需过多计算细究，都能依把存基知领过去** > 记得Lab趁早开始写哦~不要最后差点再让自己人生节奏突然崩塌谢谢，否则赶期末苦等到班白发。

刚上完跳表，我觉得这是我上过讲的最差的课。怀疑是老师已经忘记了自己ppt上的内容，仿佛ppt是别人的，我只是个代读的。 后面有所改观了再回来重评。 观察了将近一个学期了，是真的讲的不行啊。。。ppt从一开始的把清华那本书的ppt截图到自己的ppt上变成了直接用配套ppt，这进化方向怎么越走越省事。 说实话，我是真没发现这本教材好在哪里，有很多故弄玄虚、硬铺垫、硬复用代码的内容，读起来非常痛苦，痛苦得像在嚼一本加密的说明书。

讲得稀碎不说，还每节课都点名，属于既不进化还要抓人次数的那种。

别点名了，真的求求你，放我一条生路吧 老师能不能体谅一下咱们这些不想听你课、选择自学的人啊 ———————— 今天又纸质点名，绝了，6 ———————— 你说的虽然是中文，但翻译过来是这样的： 2.实验要求及评分规则 念在大家这学期已经快被作业喂饱了，本次 Lab 里那个算法并行化框架的实现——选做，不！计！分！Lab 的分全看文档，文档写好了你就赢了。想动手的作品家请自便，评测接口我们照常提供，你想验证程序正确性随时来。 你得先读懂并理解上面那套算法并行化框架，然后在文档里把下面俩问题回答了 1.针对上面两个问题，分别讲清楚该怎么任务划分，才能靠这个算法并行化框架解决它们。只说思路就行，代码什么的不用写。 2.除了上面两个问题，这套算法并行化框架还能拿去解决别的啥问题？请举出一个，并描述怎么用这个框架解决，同样无需实现。 虽说不需要大家去实现上面这套算法并行化框架，但为了让大家对并行化到底能把性能拉多高有点身临其3.其境的感受，需要你们交出任意某个问题在并行化前后的性能差异（用运行时间或者时钟周期都行）。细则如下：1)麻烦描述一下这个问题；哪个2)描述并行化的做法（不限于上面那套框架、任意并行化方法都行）；3)最后把并行化前后的性能数据摆出来做个对比。这一小问是真的要你写程序跑性能的，不过代码/问题随你挑（建议扒自己以前写过的码），只要能把并行化对性能的提升效果秀出来就行。

一年前上的这个课，刚看了看点评发现并发Kruskal的错竟然还没有改，实在无语。 当时发现错误之后和助教讨论了一下，之后上课的时候助教也向老师提了这个问题，老师原话大概是“一年前也有同学发现了这个错误，怎么解决留给有兴趣的同学当作业了”，翻译成人话就是这错至少两年前就存在在讲义上了，搁这儿年年岁岁坑同一波学生？？ 希望之后看见这个点评的同学可以提前意识到这个算法给的代码是错的，少走弯路:(

课程内容：跳表、Bloom Filter、AVL 树、Splay 树、B 树、红黑树、KD 树这堆树开武林大会，拓扑排序、Dijkstra、KMP 来串场，外加一些并行编程知识来撑场面。部分内容会参考清华的《数据结构（C++语言版）》第三版，属于是武林秘籍有据可查。 上课自由度：每节课（理论课和上机课都算）课前签到，课堂上偶尔给你来个随机提问，属于开盲盒式点名，坐下之前先拜个佛。 考核标准： 1. Project（实现 LSM Tree，代码+答辩+报告三件套全上）和 4 个 Lab（实现哈希表和跳表、实现替罪羊树、实现过顶点最短路算法、实现过顶点最短路算法的并行化）合起来共 40% 2. 期末考试 60%，一考定生死那一卦 3. 每周一个 Homework，完成得不好或者不交会倒扣分（基本上是实现当周所学的算法/数据结构），属于作业界的负债利息，越拖越穷。 讲课质量：很高。很有意思的是，每节课前会发课程内容的原始论文，说是让同学们阅读一下，体会这个数据结构/算法是在怎么提出的（虽然我一次都没看过2333，论文发来我当壁纸）。理论课是戚老师讲，上机课是董老师讲，都挺不错的。 我是交叉课选到这门课的🤡，前半学期还是学到了挺多东西，但后半学期因为本专业的作业压力变大+在这门课积压了太多作业没写完，于是在考试周前新增的退课阶段把这门课退掉了（这里感谢教务处加了一次退课机会orz，救命恩人级别的操作）。这门课的 Project 和 Lab 质量确实高，都给了框架、详细的文档以及测试数据，助教也能很及时地答疑。要是完整地跟上这门课应该能学到很多东西吧，可惜了🥲，属于是菜上齐了我先跑了。