跳转至

1755882721

高级数据结构与算法分析

课程学习内容

顾名思义，高级数据结构与算法分析（Advanced Data Structure & Algorithm Analysis，简称 ADS）主要分为两个部分：

  • 高级数据结构

    主要包括 AVL 树、Splay 树、红黑树、B+ 树、倒排索引、左式堆、斜堆和二项堆等。

  • 算法分析

    主要包括摊还分析、回溯、分治、动态规划、贪心、NP 问题、近似算法、局部搜索、随机算法、并行算法和外部排序等。

相较于数据结构，算法分析占据更主要的位置且难度更大。特别是 NP 问题、近似算法、局部搜索、随机算法等理论性强的章节等在考试时难度偏高，其中很多问题直到目前也受到众多理论计算机科学家的关心。

先修要求

  • 数据结构基础

课程教材

  • 《数据结构与算法分析：C 语言描述》Data Structures and Algorithm Analysis in C, [ 美 ] Mark Allen Weiss

    同数据结构基础教材。数据结构（AVL 树、Splay 树、左式堆、斜堆和二项堆等）以及部分的算法分析内容（回溯、分治和动态规划等）基本按照本教材思路进行。教材保持老外写书略啰嗦但比较清晰的特点，比 PPT 详细，如果只看 PPT 无法理解可以配合教材阅读。

  • 《算法导论》Introduction to Algorithms, [ 美 ] Thomas H. Cormen, Charles E. Leiserson. Ronald L. Rivest, Clifford Stein

    算法类图书的经典之作，也是 MIT 等名校算法课使用的教材，有的地方也将其根据作者姓氏首字母简称为 CLRS。在这门课中，摊还分析、红黑树、B+ 树、贪心算法、NP 和随机算法等章节基本参考本教材，除此之外，作业中也有难题源于此书，project 中关于斐波那契堆的内容也可以参考。相信很多同学对这本书早有耳闻且有敬畏之心，但个人不是非常推荐初学者阅读这本书，因为其中存在不少跳步或者写作不够清晰之处，并且内容太多可能让人无法在一学期内把握核心想法，更适合当个字典挑选部分与课程内容相关的章节、例子等阅读，至少比课程组的 PPT 详细许多。

  • 《算法设计》Algorithm Design, [ 美 ] Jon Kleinberg, Éva Tardos

    同样是算法类图书的经典之作，Jon Kleinberg 和 Éva Tardos 是康奈尔大学的教授，其中 Jon Kleinberg 不到四十岁就拿到了美国三院（美国科学院、工程院、艺术与科学院）院士，Éva Tardos 也是算法博弈论领域的开拓者之一，因此都是顶级大牛。在这门课中，近似算法、局部搜索等章节基本参考本教材，并且也有部分习题出自本教材。我个人非常推荐阅读这本教材，虽然偶尔有点啰嗦，但写作非常清楚且令人感到舒适，其中的例子和习题也都非常经典，也会介绍一些算法设计的思想。

除上述教材外，我个人也推荐基础比较薄弱的同学参考哥伦比亚大学教授（此前是斯坦福大学教授）Tim Roughgarden 的《算法详解》，这本书总共四卷（每卷都特别薄，所以可以看得很快），覆盖了 FDS 和 ADS 的较多内容。Tim 是前面提到的 Éva Tardos 的学生，同样也是算法博弈论领域的开拓者之一。这套书的特点就是相当简单易懂（绝对的入门书籍），作者已经把算法的设计思想、流程等给你嚼烂了喂嘴里了，所以读起来特别亲切（特别是动态规划部分，读者阅读后一定会有所体会）。特别是学 ADS 之前也可以用这本书再回顾一下 FDS 的内容，也会有所收获。

分数构成

课程组统一安排如下，具体各班执行细则可能略有差别，详见任课教师栏：

  • 作业（10%）

    作业在 PTA 上布置完成，与 fds 不同的是理论题比例更高，只有部分章节有编程题。

  • 期中考试（10%）

    期中考试时间一般在夏学期初，不同班级试卷一般不同。难度相对于期末比较适中，可以通过做历年卷感受题目风格。期中考试分数可以由更高的期末考试分数覆盖，但这一般是不现实的。

  • 讨论（10%）

    这一部分不同班级差别较大，习题来源以及提交方式都有很大差别，但大部分老师以此方式进行点名。

  • 实验（30%）

    不同班级可能有 7-8 个实验题，实验涉及倒排索引，不同树、不同堆的比较，最大团算法，二维装箱问题，跳表，Map reduce 等。不同于 fds，ads 的实验可以组队完成（一般 3 人），并且有很多班级取消互评。每组需要从这些实验中选择 1 个课堂进行展示（很多时候要靠抢），一般在 ads 三节连堂的第一节课进行，并且为了避免摸鱼采取上台前抽签的方式决定展示人。进行展示的 project 占据 20 分，还有 10 分部分班级需要在布置时自主选择，部分班级挑选其他做过的 project 中分数最高计入分数。

  • 期末考试（40%）

    这门课的期末考试是出名的折磨，斩杀线为 40 分。历年有因为试卷太难分数太低下调斩杀或者调低期末比例的情况。期末同样有一些历年题，可以做一下感受难度，但是心理安慰因素居多。考试和 fds 类似，理论题为主，然后是一个程序填空 + 一个函数 / 编程题。

除此之外还有可以补充平时分的 bonus，获得方法为做两次计分 project 之外的其他 project，每做一个根据不同老师规则获得 1 或 2 分加分，当然需要乘以获得分数的百分比（例如获得 90 分将会获得 0.9 或 1.8 分），部分班级 bonus 可能设置上限 5 分，但所有班级都统一要求期末考之外的分数上限为 60。

任课教师

纵观 ads 各教学班教学风格，大致可分为“原理派”和“实现派”，其中陈越、何钦铭是“实现派”的代表，从陈越的 PPT 就可以看出，侧重代码逻辑，原理并没有非常清楚深入；而张国川、叶德仕、毛宇尘是“原理派”的代表，他们几乎不讲代码实现，但是会把原理讲得非常深入，甚至会拓展。

毛宇尘老师年轻且负责，并且理解学生，各项任务给分也很慷慨，非常值得推荐。

  1. 上课采用手写投影的方式，所有步骤都会细致推导，讲课很清楚，并且经常询问同学们听课情况，当然这也导致有几次课拖堂较长时间（连堂到实验课时间）；
  2. Project 采取选择剩余 project 中的最高分计入，并且每个 project 他都会用重新叙述要求，并且取消互评，报告上也脱离了传统的陈越老师的模板，并且设置上限。当然毛宇尘老师 bonus 上限只有 5 分，且一个 project 只加 1 分，但是你也可以在 project 中选择用多种方法或者提出创新思路等申请 0.5-1 分的额外 bonus；
  3. 毛老师作业会有部分自己出的题，讨论题也有自己准备的问题，并且期中考试也基本都是自己的题。除此之外，他下课后也会再等半个小时进行答疑后才会离开，也经常在群里转发他回答其他同学的一些比较好的问题，并且回答问题也非常耐心，可以说是非常体贴用心了；
  4. 毛老师期中期末考前都会免费公开 3 套理念卷供大家练习，可谓非常良心；
  5. 毛老师本人是做算法理论方向的，因此重视理论，代码实现讲解偏少，代码作业他也声称不会查重，但是他也会经常提醒同学要参考 PPT 上的代码，因为考试的程序填空是按照上面的代码命题。

相信很多同学都对“ds, ads, yds, yyds”这条评论很熟悉了，这是对叶老师在作业和考试中贡献大量难题的肯定（错乱）。

  1. 叶老师也是做算法方向的。他真的很负责任，而且很真诚，每节课开始都会和大家鞠个躬说感谢大家来听我上课，尽管老师确实讲课没有那么清楚，但是能够感受到老师对于他自己领域的认真，会补充一些例子有助于完成他的题。
  2. 叶老师不是翻转课堂，没有举手发言，project 也取消了互评。project 的报告要求不低，但是给分较慷慨。讨论是学在浙大上几道题目，应该是用来点名。
  3. 在重难点内容结束后叶老师也会分享他独家的课程笔记，相当于是对 PPT 的总结概括，还有他自己补充的知识和例子，可以作为复习参考。
  4. 在期中考试 / 期末考试前，老师会让助教整理历年的考试题，并做成专题、模拟题的方式在 PTA 上发布。

人工智能系主任，因此连续两年预置人工智能专业的同学。杨洋老师也是相对年轻的老师，上课幽默风趣，也非常理解学生，非常推荐大家选杨洋老师的课。

  1. 杨洋老师讲解 PPT 非常清楚，无论是理论算法的推导还是具体代码的实现都讲解地相当细致。杨洋老师上课也会辅助许多生动形象的例子，即使是三节连堂的算法大课也不会犯困。
  2. 杨洋老师对平时分非常慷慨，presentation 只要做了就可以拿到所有的展示分。为了减轻同学们不必要的负担，杨洋老师也会砍掉部分相对复杂的 project，并提高每个 project 作为 bonus 的分数权重（别的班可能是 1 分，杨洋老师班会视 project 的工作量给 1.5 - 2 分不等） 此部分于 2023-24 春夏更新：杨洋老师的平时分政策视助教而改变，在这个学期就使用的是每个 project 最多可以获得 1 分 bonus 的政策，但是总体来说给分还是比较慷慨的，班上有半数的人获得了平时分的满分。 此部分于 2023-24 秋冬更新：杨洋老师的平时分政策改为需要完成一个 project 的展示和一个 project 的报告，此外每个 project 最多可以获得 2 分 bonus 的政策。一共有 8 个 project。
  3. 杨洋老师作为一名学生时代的 OIer，非常注重算法的具体实现与应用，他的 discussion 经常会是算法的推导或手写代码，可以帮助大家对于较难的算法有更深刻的认识。杨洋老师还有一个强大且负责的助教团队，从算法部分开始，每节课结束助教都会在群里提供 leetcode 对应算法的题目供大家练手（选做），如果觉得自己的代码能力还不够强，相信杨洋老师的 ads 一定能让你获得巨大的提升。 此部分于 2023-24 春夏更新：似乎今年 yy 的助教只在回溯，分治，dp 三个模块给出了 leetcode 的练习题，可能是不同年份助教不同的原因，但是今年 yy 老师在最后又重新开放了全部的作业题（你懂得），也是对平时分十分的慷慨。 此部分于 2023-24 秋冬更新：yy 老师的作业题目少于平行班，期末考前也不会和张国川老师一样发历年卷。
  4. 21 级杨洋老师班的期末考平均分最高，而且是所有教学班中唯一一个没有人被斩杀的班级，迷信一点的话选择杨洋老师肯定没错。
  5. 23 级杨洋老师班的期中难度高于张国川老师班，期中考试也晚于张国川老师班。

何钦铭老师也算得上是计院中比较出名的老师，但是 ads 这门课比较劝退，原因如下：

  1. 19 级的给分梦魇，一开始没有说清楚具体要求，比如一些 bonus 只能补充部分分数等，期末出分可以比平行班低 2-3 档，
  2. 与陈越老师一起，采取翻转课堂模式，即老师提前把教学视频上传要求同学们课堂观看，上课以讨论展示为主，部分较难的问题可能会再强调。何钦铭老师讲课能力本身比较出色，但 ads 他不讲课；
  3. 讨论环节大部分老师都是点名送分，只有他的班级 19 级 10 分满分平均 3-4 分，20 级稍有改进也只有 7 分，这也是导致他的班级分数比其他班级低很多的重要原因；
  4. 设置回答问题加分环节，这个环节水分多，没什么营养并且很卷。

因为种种原因 21 级何钦铭老师没有开成课，不知道后续何老师会不会有所反思（x）。

王灿老师是浙大 acm 队的教练，教 ads 算是相当专业对口了。总体是比较推荐的，具体情况描述如下：

  1. 王灿老师非常 nice 的，平时分尽量会往高了打，没有翻转课堂，讲解 PPT 非常清楚，但是也有声音比较轻可能带有一点点催眠属性的小缺点。
  2. 由于王灿老师是 acm 教练，因此他的 ads 课可能会是 acmdl 聚集地，你可能会在 presentation 时见到 acmdls 八仙过海、神魔乱舞。（不过不用担心，acmdls 自然是强大的，但你只要认真准备了并不会影响到你的 pre 得分，王灿老师班平时分还是容易高的）
  3. 王灿的优势在于他可以分入“实现派”阵营（使用陈越 ppt），但是在很多地方会给出额外的很清晰（比陈越 PPT 清晰很多）的原理证明，使得你既能对代码实现很清楚（这正是 acm 干的事啊！），又能理解很多关键的原理。（他也会吐槽某些地方陈越的 PPT 写得不清楚）
  4. 如果想找王灿老师答疑，需要抓紧机会，因为一下课他就会急忙跑路（他很忙）。找助教也很不错，王灿老师的助教大多是强大的 acmdl，ads 对他们来说是小 case。另外考试前会有一个答疑时间，王灿老师和 acm 队的一部分同学会组成豪华答疑团队，笔者去过一次，氛围不错的，一些自己搞不清的超高难度问题也能得到解答。
  5. 令王灿老师很自豪的是他的 ads 班成绩总是各个教学班最好的，考试 90+ 的几乎被王灿班（的 acmdl）锁死，虽然有 acmdl 带飞的原因，但是王灿班也有相当数量基础不是很好的同学，因此王灿老师的教学质量可见一斑。

整体而言教学比较上心，给分也不错，具体情况：

  1. ljf 老师讲课基本上就是 PPT 的内容（偶尔可能会讲一些写在助教讲义里的拓展内容），虽然讲课比较磕磕绊绊，但你可以选择看助教的讲义
  2. ljf 老师非常 nice，知道考试会比较难，想尽心思鼓动同学多发言加 bonus；21 级期中考试后还请全班同学喝了奶茶；据说 21 期末考试很水的函数题也是他出的，为了降难度还特意加了 hint（我哭死）
  3. project 要求比较松，没有互评，展示名额需要抢，而且展示其实没什么压力，助教也不会问什么难的问题

2023 年春夏学期第一次开课的新老师，人很好能听取学生们的意见，知识丰富。但是讲课缺少自己的理解，整体不雷但是比较平淡。

  1. 2023 年春夏学期时，ch 老师应该是接的姥姥和 hqm 的那一套，即翻转课堂，但是他积极和同学们讨论，最后尊重同学们的意愿改回了正常授课，改回正常授课后的分数组成等都会和同学们讨论，人非常 nice。
  2. 翻转课堂的 discussions 仍然会留一道作为当堂小组讨论，讨论完会请同学讲，所以肯定是能写的出来的，助教也比较 nice，没有在 discussion 的分数上为难大家（感觉写了，且有理有据应该都给满了）。
  3. 正常授课时他还是使用姥姥留下来的那一套 PPT，上课基本对着那个 PPT 的内容进行教学，那份 PPT 还是太“实现派”了一点，上课的时候总是感觉原理学的印象不是很深刻，在面对难题时感觉不太够。
  4. ch 老师就是很典型的“年轻老师”，知识非常丰富，思维敏捷，思路清晰，和老师交流、讨论问题的过程感觉受益匪浅。但讲课就比较平淡而且偏快，基本是在平推 PPT，让人摸不清主次重点。遇到比较难的原理时会板书，但板书比较随性，字比较歪，字体也比较小，有时候得多看一遍智云才看的明白板书。
  5. 期末前老师也主动发了几套题在 PTA 上给大家模拟练手，最后一节课还给大家简单讲解了一下。

参考资料

学习建议

可以说这门课是理论计算机方向的入门课程，但显然完全不是一门合格的入门课程。第一课程设计并不合理，在短短一学期内讲清楚学清楚这么多的内容简直是天方夜谭，课特别是算法分析部分，每一章单独都可以扩展成一个学期的课程；第二，课程组授课老师水平参差不齐，很多老师自己也不没有专门学过这些理论，并不是做这些方向的，因此讲课也只能基本按照 PPT 来，但很遗憾，课程组的 PPT 非常简洁，只是列举一些例子和解法，没有逻辑关系的说明，也没有什么算法设计的思想，让人很难学明白，甚至不知道自己在学什么，只是看到几个例子，因此学生大部分也只能靠自学，或者不怎么学，总而言之学不明白；第三，这门课教考略分离，这是大课程组难以避免的现象（当然 ADS 至少比数据库、计网等课程要良心一点），因为期末考试是每个老师负责一个小部分，很多老师也不知道自己上课是希望给同学们传达什么重要的东西，所以考试无法与授课非常贴合，并且老师出题风格很随机，有的可能就喜欢出一些钻牛角尖的概念，有的喜欢挑难题。

总而言之，我相信大部分同学都认为这门课是梦魇，是计院最难学明白的专业课（之一），但我希望同学们认清一个事实，这不完全是你们的问题，整个课程安排和课程组都存在非常大的问题。如果同学们愿意跳出课程设计的种种缺陷，多花时间看一些前面推荐的教材还有一些学长写的讲义 / 笔记，整理一下这些算法背后的思想等，我认为会收获很多，并且会认识到这门课本质并不是非常难，而不是像现在一样学完之后压根不知道自己学了啥，只知道这些东西好像很难，以后再也不愿意碰理论计算机方向了。至于考试，除了部分老师抽风出的题之外，大部分题目应该也是不难的（特别是近年难度还下调了的情况）。

当然回到正题，还是需要写一些更贴合同学需要的学习建议。最优路径显然是多看教材，多看讲义，但显然大部分同学都做不到，那么就提一些更简单的学习策略。数据结构部分内容相对简单，因此把 PPT 学明白即可，这是因为数据结构你只需要知道“是什么”就可以了，考试基本就是一些概念和操作。算法分析部分，回溯、分治（包括主定理）、并行和外部排序理解课内内容即可（事实上也不难），动态规划和贪心需要在课内之外自己多找一些例子，特别是动态规划可以刷一下 leetcode 上面的经典题，因为考试的编程题大概率是动态规划。NP、近似、局部搜索和随机算法如果实在没有精力学习，就把课内的东西记住，作业题认真理解，但如果希望学明白的话，还是建议多看看前面推荐的教材，

更现实地，关于拿到这门课的分数有如下建议。对于平时分，期中考试充分复习并且做好历年题可以拿到比较满意的分数，project 展示的一次比重较大需要认真对待，bonus 根据实际情况完成，一般额外完成 3-4 个是正常的。对于期末，每个章节都会出题，题目分布也比较均匀，所以不用担心难题章节题目很多，其实和简单章节题量差不多。除了刚刚提到的注重平时积累，也可以稍微做一下历年题找感觉。数据结构部分一定保证尽量不失分，因为这是最简单的一部分。算法部分基础题同样如此，否则成绩可能不是很好看。算法部分难题如果认真学了其他材料的同学应该是能拿到不少分数的，如果只是学了 PPT 和作业则尽量从平常做过的题和上课的问题找灵感尝试解决，但不要花太多时间，否则得不偿失。后面的部分一般程序填空和编程是数据结构 + 动态规划，但 20 年最后编程是数据结构（AVL 树），程序填空是动态规划。动态规划一般而言不会特别刁难，掌握常用套路即可拿到大部分分数，数据结构如果在程序填空则一定要熟悉 PPT 上的代码。