type
status
slug
summary
tags
category
password
date
icon
杨洋老师yyds！
资料汇总：
课程学习内容
主要分为两个部分：
- 高级数据结构
主要包括 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 等。不同于 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。
学习建议
这门课可能有一些温水煮青蛙的感觉，平常作业不多，并且大都是判断、选择，因此给了很多摸鱼划水的机会。经常是似乎上课听懂了，但是面对考试题又是经常无从下手的状态。建议平常上课如果老师讲课一般可以看其他优秀老师的录播，课后作业不能摸鱼划水，有问题要查阅资料或者问同学老师尽力解决，也可以在最难的 NP、近似、随机等章节看算法导论等了解更多的例子。
对于平时分，期中考试充分复习并且做好历年题可以拿到比较满意的分数，project 展示的一次比重较大需要认真对待，bonus 根据实际情况完成，一般额外完成 3-4 个是正常的。对于期末，除了刚刚提到的注重平时，也可以稍微做一下历年题找感觉。数据结构部分一定保证尽量不失分，因为这是最简单的一部分。算法部分基础题同样如此，否则成绩可能不是很好看。算法部分难题大佬得心应手，一般的同学可以从平常做过的题和上课的问题找灵感尝试解决，但不要花太多时间，否则得不偿失。后面的部分一般程序填空和编程是数据结构 + 动态规划，但 20 年最后编程是数据结构（AVL 树），程序填空是动态规划。动态规划一般而言不会特别刁难，掌握上课的例子和作业题就能拿到大部分分数，数据结构如果在程序填空则一定要熟悉 PPT 上的代码，实际上考察的面也不广，全部过一遍是很快的，历年卷基本也覆盖了大部分可以出的题。
当然也不必过度焦虑，20 级开始，笔者认为 ads 期末考的难度有适当的下调，题目也更加贴近上课的例子，因此平时认真会有好的结果。并且最近两年 yds 老师也慢慢收手不再出一些很恶心的近似和局部搜索，难题部分由 myc 和 yy 老师合作命题。祝各位好运 ~
AVL Trees, Splay Trees, and Amortized AnalysisRed-Black Trees and B+ TreesInverted File IndexLeftist Heapsand Skew HeapsBinomial QueueBacktrackingDivide and ConquerDynamic Programming期中复习计划Greedy Algorithms- 作者:fufu酱
- 链接:https://csfufu.life/article/7e7fb575-3944-47cb-80c6-c192b468ba52
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。