算法设计与分析

诶，为什么这门课都没人给评价…

我觉得这门课挺好的，唯一一点不太好的地方就是考试占比略大，占40。即便前面60拿满，想要满绩也是比较困难的。我期末比较菜，最后期末82总评92.8压线飘过险些A-…

可能有的同学会想问这门课和DSAA比起来怎么样。从任务量角度来说这门课肯定是远低于dsaa的，6次纸质作业，学期初可能会布置得勤快一些，后面就很久才布置一次。oj作业是一周两题，总共十次+一次bonus lab（一次两题，一学期总共22题），十次作业都会讲，bonus lab不讲，oj会罚分，你的得分=100-5*max{0, 提交次数-2}，oj题目的难度低于dsaa，第一题大概是dsaa的a b题难度，第二题大概是dsaa的c d题难度，基本不会出现e f这种题目的难度，也没有avl树这种特别恶心难写的东西。

期末考试15选择20判断3大题，前面的选择判断基本送分，看看课件就行，后面三道大题有点头疼，尤其是对我这样的菜菜来说。这个学期考了两道算法设计，一道图论，另一道动归（这个实验课上讲过几乎一样的，但是考试的时候我没想起来呜呜呜），还有一道考察bipartite perfect matching的，比较送分。

总的来说我觉得挺好的（不过就算不好也没得选哈哈哈哈

这门课应该是水课，史老师的英语偏日系，有点听不懂（没事，摆烂了，反正大家都听不懂）

• 10% 随机签到，基本是两节课中间签到，由学助负责，大概隔一周一次（也有连续签的），前三周也可能有。
• 20% 6次理论课作业，都是祖传题，github上随便找找都能找到原题的，但只能提交一次，别错过提交时间或者一不小心交错了，提交前要反复检查。
• 30% 11次lab（+1次bonus lab），每次2道题，建议每次听老师讲解后写代码。lab出勤也算分，记得在签到纸上签名。
• 40% 期末，题型是单选（20题，40%）、判断（15题，30%）、大题（3题，30%），单选、判断复习就嗯看祖传ppt，祖传ppt上全有（大概有颜色的地方是重点吧），大题没考算法证明，考解决问题，写一点伪代码之类，不难。

如果前面全拿满了，期末要92才能A+，美美的进行了一个绩的卡。

说实话，这门课相当于半个水课了。

-首先，这门课的听课体验相当不好，史老师的英语口语比较难绷，而且课程节奏有些奇怪，有时候会在一个简单的代码demo的讲解上来回肘击一整节课。总之建议自学，但是课程PPT自学起来又比较难受，感觉是无意义+低意义内容占比较多且难以识别导致的。

+虽然但是，我个人分析，史老师是一个性格相当好的老师。老师上课的时候经常会询问“Follow me？”“Any questions？”来看看有没有人在听课，除了学期最开始的那几周基本上就是完全没有人回应了。然后史老师就只能环顾没有一个人抬头看他的教室，沉默个几秒，说一句“Good.”然后接着讲课…说实话我时常觉得挺对不起史老师的，虽然就凭史老师的上课情况，让同学想要跟着他的节奏同频共振几乎不可能，但还是觉得我们一直这样不理他确实有些不厚道。然而史老师情绪稳定，从来没有动用任何手段强迫我们跟上他的节奏，他最接近采取手段的一次是课上嘀咕了一句“要不课前不把课件发到bb上吧…”，但最后还是没有采取任何强制措施。（对不起，史老师！谢谢你，史老师！>^<）综上所述，在史老师的课上自习，不会受到任何干扰。

+本课程相比DSAA，最大的特色在于每次OJ的两题中的第二题会罚分（从第三次提交开始，每次都会多扣5分，比如你第四次交过了95%的样例，他就会给你计85分）。但其实这点几乎无需担心，首先，是本课程的OJ题目难度几乎没有赶得上DSAA的EF题难度的；其次，除了bonus OJ以外，都是A题占一次OJ作业分数的60%，B题占40%（bonus OJ的两题是各占50%）而会罚分的是占40%的B题，换句话说你B题十分之一的样例没过也才给一次OJ作业扣4分；最后，我们有一次bonus OJ，bonus的分可以1：1地填给所有OJ作业，而且bonus OJ的两题都不会罚分。我是到最后所有OJ一共只扣了11分，然后bonus OJ写第一题拿个暴力算法直接超时了一半的样例，bonus OJ豪夺25分直接填满了之前扣的分。最后的最后，每次OJ作业基本上都是在周日截止，而在那周的实验课上老师就会讲解OJ作业的标准解法，听了再写毫无压力。

-本课程的OJ作业中，卡常的情况特别多。应该是我个人问题，我写的代码比较史山，所以我真的是被卡常问题搞疯过好几次。我最离谱的一次是优化一个用了哈希表的A题，我特么拼命优化自己的算法，自己优化到没办法了去问了DS老师，DS老师优化一次我交一次，交到后面DS老师给的方案都开始是负优化了还是被卡常，最后，我发现开局给哈希表开n容量的时候样例9，10会超时，开局给哈希表开m容量的时候样例7会超时，所以我写了一个随机数生成器，让程序⅔的概率给哈希表开m容量，⅓的概率给哈希表开n容量，这样又凹了好几次凹过了。最后我交了四五十次这题才终于拿满分。（不要学我，真卡常了该放弃几分就放弃几分，该大改代码就大改代码。我纯是杀红眼了，讲出来给各位当个笑话听）不过，看互助群里，哪怕不是我这种史山选手，大家也多多少少会碰到卡常的沟槽问题，只能说这门课OJ时限开得确实挺极限的:(

-注意！本课程的OJ最沟槽的一点，是它根本不会报runtime error！你数组越界了它说wrong answer，你DFS爆栈了它也说wrong answer，你访问null变量内容它还说wrong answer！debug的时候注意别被他的沟槽报错给误导了！

-本课程相比DSAA还有一大特色，就是额外的签到题，叫lab practice，这个东西的检查力度和难度和工作量的浮动都很大，而且都需要课上给老师或助教当面检查。举例来说，第一次practice是纯书面的，要你画图追踪一个递归算法的流程，还有让你简单叙述另外两个问题的思路（这次practice甚至还有大概0.2分bonus，具体几分bonus记不清了，反正一次practice一般是1分满分，然后这个bonus也是挺好拿的）；然后第二次practice的工作量出奇的大，又要写代码又要自己设计测试样例（还要把样例展示给老师看）还要写暴力算法代码还要写验证算法正确性的程序代码，最后还要总结成一个report文件给老师看，不过老师也意识到这次practice工作量确实大了，所以这一次practice好像算了2分还是3分来着；之后的practice的工作就基本正常了，有时候要写代码，有时候要证明算法，有时候要写报告，反正工作量和难度都不大。但是老师检查的力度又开始放飞自我，我们实验课是赵耀老师，有时候赵老师看着没啥问题就给你过了，有时候老师开始给你抠细节，你跟她解释她还半天她还不大听得懂，我是听说过有人检查一次practice跟她argue二十多分钟的…总体上这个practice算是小烦。

+最后就是期末考了，整体上期末考可以说是有惊无险。考前我们对着考点不明确的PPT复习半天，感觉东西又多，又不知道他到底要考啥，不过实际考试的时候就安心了，考试难度格外简单：15道选择+20道判断+3道大题，会考许多基本概念（我印象比较深的是他考了递归和归纳的定义的区别，图中循环的定义，细到了环中包含的是简单路径还是非简单路径，之类的），基本上对课件上的内容保有一定印象就能答对，算法证明算是考了，不过都是在选择判断题里问你某个步骤或者证明过程中涉及的某个定理，也是有点印象就能答对。大题纯送人头，一个分析算法时间复杂度的，一个网络流的，一个画BFS树的，都是最基础的东西，他考网络流甚至不问你算法的细节，就问你这个图里边还有没有增广路径，然后又问你这个增广路径被用掉以后图中的流是多少。总之考试难度非常简单，考试开始一个小时一大半人都提前交卷走了，我上次在非思政课见到这种盛况还是生概（

ADA的内容绝对是硬的，每个theorem和算法的optimal证明，让本人从原来oi式的“知道正确”到现在的“知道为什么正确”，对思维也是很好的锻炼。可以说，如果不是不知道期末怎么考，我不会细致的把证明都过一遍，收获颇多。

因此，ppt上不算少的的证明才应当是这门课的核心。然而，考试却毫无要求，可以说即使冒着gpa变低的风险，我也希望在大题看到证明（如graph）与程序设计题（如dp），而不仅是将算法过程过一遍。考完回头看，好像学会原理未必比不学考得高……

最重要的dp，印象中只考了加权日程表间隔问题的做法…… 好歹也考个状态转移方程吧；有些题甚至不需要知道算法过程，如问你有负边权该用什么算法，只要知道bellman-ford这个名字就可以！因为这样的难度，本人遇到纯定义的判断题，总认为syh想要害我，反手写上两个false，A+不保……

虽然但是，后选者也切忌掉以轻心，这样的考试应该会成为过去式的吧……