跳转至

1706762267

高级数据结构与算法分析

CS 专业基础 AI 专业基础 IS 专业基础

课程学习内容

主要分为两个部分:

  • 高级数据结构

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

  • 算法分析

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

相较于数据结构,算法分析占据更主要的位置且难度更大。特别是 NP 问题、近似算法、局部搜索、随机算法等在考试时难度偏高,并且直到目前也是算法界关心的问题,因此 ads 这门课也称得上是一门“活着的学科”。

先修要求

  • 数据结构基础

课程教材

  • 《数据结构与算法分析:C 语言描述》Data Structures and Algorithm Analysis in C

    同数据结构基础教材。虽然官方指定教材是接下来要介绍的《算法导论》,但实际上数据结构以及很多的算法分析内容基本按照本教材思路进行。比 PPT 详细,如果只看 PPT 无法理解可以配合教材阅读。

  • 《算法导论》Introduction to Algorithms

    算法类图书的经典之作,相信很多同学对这本书早有耳闻且有敬畏之心,但实际上这门课用到的机会不是很多。在 NP、近似算法、随机算法等理论性强的章节会有部分例子参考本教材。除此之外,作业中也有难题源于此书,project 中关于斐波那契堆的内容也可以参考。

分数构成

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

  • 作业(10%)

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

  • 期中考试(10%)

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

  • 讨论(10%)

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

  • 实验(30%)

    不同班级可能有 7-8 个实验题,实验涉及倒排索引,不同树、不同堆的比较,最大团算法,二维装箱问题,跳表,Map reduce 等。不同于 fdsads 的实验可以组队完成(一般 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 分不等)
  3. 杨洋老师作为一名学生时代的 oier ,非常注重算法的具体实现与应用,他的 discussion 经常会是算法的推导或手写代码,可以帮助大家对于较难的算法有更深刻的认识。杨洋老师还有一个强大且负责的助教团队,从算法部分开始,每节课结束助教都会在群里提供 leetcode 对应算法的题目供大家练手(选做),如果觉得自己的代码能力还不够强,相信杨洋老师的 ads 一定能让你获得巨大的提升。
  4. 21 级杨洋老师班的期末考平均分最高,而且是所有教学班中唯一一个没有人被斩杀的班级,迷信一点的话选择杨洋老师肯定没错。

何钦铭老师也算得上是计院中比较出名的老师,但是 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. 如果想找王灿老师答疑,需要抓紧机会,因为一下课他就会急忙跑路(他很忙)。找助教也很不错,王灿老师的助教大多是强大的 acmdlads 对他们来说是小 case 。另外考试前会有一个答疑时间,王灿老师和 acm 队的一部分同学会组成豪华答疑团队,笔者去过一次,氛围不错的,一些自己搞不清的超高难度问题也能得到解答。
  5. 令王灿老师很自豪的是他的 ads 班成绩总是各个教学班最好的,考试 90+ 的几乎被王灿班(的 acmdl)锁死,虽然有 acmdl 带飞的原因,但是王灿班也有相当数量基础不是很好的同学,因此王灿老师的教学质量可见一斑。

21 级的新老师,很年轻,教的也不错,给分也可以,比较推荐,具体情况:

  1. ljf 老师讲课基本上就是 PPT 的内容,会举一些例子,整体感觉是可以听懂的,不过对于应付考试那种题目可能不太够
  2. ljf 老师非常 nice,知道考试会比较难,想尽心思鼓动同学多发言加 bonus21 级期中考试后还请全班同学喝了奶茶;据说 21 期末考试很水的函数题也是他出的,为了降难度还特意加了 hint(我哭死)
  3. project 要求比较松,有互评但不占分(个人认为就应该这样),展示名额需要强,而且展示其实没什么压力,助教也不会问什么难的问题,不过多做 project 的加分很少,不太划算

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

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

参考资料

学习建议

这门课可能有一些温水煮青蛙的感觉,平常作业不多,并且大都是判断、选择,因此给了很多摸鱼划水的机会。经常是似乎上课听懂了,但是面对考试题又是经常无从下手的状态。建议平常上课如果老师讲课一般可以看其他优秀老师的录播,课后作业不能摸鱼划水,有问题要查阅资料或者问同学老师尽力解决,也可以在最难的 NP、近似、随机等章节看算法导论等了解更多的例子。

对于平时分,期中考试充分复习并且做好历年题可以拿到比较满意的分数,project 展示的一次比重较大需要认真对待,bonus 根据实际情况完成,一般额外完成 3-4 个是正常的。对于期末,除了刚刚提到的注重平时,也可以稍微做一下历年题找感觉。数据结构部分一定保证尽量不失分,因为这是最简单的一部分。算法部分基础题同样如此,否则成绩可能不是很好看。算法部分难题大佬得心应手,一般的同学可以从平常做过的题和上课的问题找灵感尝试解决,但不要花太多时间,否则得不偿失。后面的部分一般程序填空和编程是数据结构 + 动态规划,但 20 年最后编程是数据结构(AVL 树),程序填空是动态规划。动态规划一般而言不会特别刁难,掌握上课的例子和作业题就能拿到大部分分数,数据结构如果在程序填空则一定要熟悉 PPT 上的代码,实际上考察的面也不广,全部过一遍是很快的,历年卷基本也覆盖了大部分可以出的题。

当然也不必过度焦虑,20 级开始,笔者认为 ads 期末考的难度有适当的下调,题目也更加贴近上课的例子,因此平时认真会有好的结果。并且最近两年 yds 老师也慢慢收手不再出一些很恶心的近似和局部搜索,难题部分由 myc yy 老师合作命题。祝各位好运 ~