NKUCS.ICU
NKUCS.ICU copied to clipboard
NKUCS-ICU
COSC0016 算法导论
https://nkucs.icu/#/courses/grade-2/COSC0016
NKUCS，一个充满了「神仙」和「神仙」课程的专业，本网站旨在记录 NKUCS 的信息以及历届学生的评价
上课时间：2020 年春，疫情线上授课
授课教师：苏老师
课程感受：
理论课：相比单纯阐述算法原理，可能苏老师更注重从数学的角度对一些算法的正确性进行阐述，能听懂算法正确性的证明我认为还是有好处的；理论课的讲授是可以给4.5/5.0分的。（最近系统学习了最大流的部分，感觉课件讲的真的是非常完善，只不过当时自己的能力不足以让自己完全理解课程内容，所以我决定过来加0.5分）
实验课：祖传习题，我个人认为对于提升学生的算法，尤其是编程能力这样的练习和作业量是绝对不够的。某个具体的模块只有一题的练习，非常建议同学们在实验课的基础上额外练习，若想完全掌握或许20-30题对于某个小专题并不夸张；实验课只能给2.0/5.0分。
期末：书后习题及PPT讲过的都要会，掌握程度要精细到每个算法的伪代码和逻辑都能清楚足以默写。附加题就摆了吧。
上课时间：2022spring
授课老师：苏老师
课程感受：
~写在前面：可能要先适应一下苏老师的语速。~
理论课的话个人感觉是广度还是可以的，但是缺乏一点深度，每个方面都介绍了几个比较经典的算法和例子，对于我这种小白来说内容还是不少，并且接受起来有一定难度。但可能要是真的想入门算法，课程内容还是不太够的。苏老师上课很喜欢讲算法正确性的证明之类的，可能理解起来不太容易，但是跟前面丁神所言，理解正确性还是很有必要的。课程所使用的PPT内容还是很详细的，个人认为作为期末复习的材料是可行的，但是作为期末突击的材料可能不太行（~硬背的可以忽略~）。P.S.算导这门课程的学习不应该只停留在把PPT学会
实验课的话我没有发言权~不好意思没去过~。但是上机作业次数不多，难度不大，不要担心。
有关考试：算导应该是大二下期末占比最高的了(70%)，不建议期末开摆，风险很大。题目内容基本涵盖在PPT和留过的习题里，会考证明题，还是要理解各类算法的思想。附加题开摆就行了(2022spring附加题是ICPC2015WF）
上课时间：2022spring
授课老师：苏老师
课程感受：
~写在前面：可能要先适应一下苏老师的语速。~
理论课的话个人感觉是广度还是可以的，但是缺乏一点深度，每个方面都介绍了几个比较经典的算法和例子，对于我这种小白来说内容还是不少，并且接受起来有一定难度。但可能要是真的想入门算法，课程内容还是不太够的。苏老师上课很喜欢讲算法正确性的证明之类的，可能理解起来不太容易，但是跟前面丁神所言，理解正确性还是很有必要的。课程所使用的PPT内容还是很详细的，个人认为作为期末复习的材料是可行的，但是作为期末突击的材料可能不太行（~硬背的可以忽略~）。P.S.算导这门课程的学习不应该只停留在把PPT学会
实验课的话我没有发言权~不好意思没去过~。但是上机作业次数不多，难度不大，不要担心。
有关考试：算导应该是大二下期末占比最高的了(70%)，不建议期末开摆，风险很大。题目内容基本涵盖在PPT和留过的习题里，会考证明题，还是要理解各类算法的思想。附加题开摆就行了(2022spring附加题是ICPC2015WF）
总有种莫名的感觉你的发言有点不太能逃脱我的框架hhhh 我的发言只是自己的感觉，没有任何的政治正确，所以畅所欲言！！好家伙，我才知道附加题是WF题目吗，一直以为是随便一个区域赛找的题，那确实就完全没有必要考虑了，看起来随便写点输入输出口胡一下暴力的思路拿点分就好了
@Emanual20
上课时间：2022spring
授课老师：苏老师
课程感受：
~写在前面：可能要先适应一下苏老师的语速。~
理论课的话个人感觉是广度还是可以的，但是缺乏一点深度，每个方面都介绍了几个比较经典的算法和例子，对于我这种小白来说内容还是不少，并且接受起来有一定难度。但可能要是真的想入门算法，课程内容还是不太够的。苏老师上课很喜欢讲算法正确性的证明之类的，可能理解起来不太容易，但是跟前面丁神所言，理解正确性还是很有必要的。课程所使用的PPT内容还是很详细的，个人认为作为期末复习的材料是可行的，但是作为期末突击的材料可能不太行（~硬背的可以忽略~）。P.S.算导这门课程的学习不应该只停留在把PPT学会
实验课的话我没有发言权~不好意思没去过~。但是上机作业次数不多，难度不大，不要担心。
有关考试：算导应该是大二下期末占比最高的了(70%)，不建议期末开摆，风险很大。题目内容基本涵盖在PPT和留过的习题里，会考证明题，还是要理解各类算法的思想。附加题开摆就行了(2022spring附加题是ICPC2015WF）
总有种莫名的感觉你的发言有点不太能逃脱我的框架hhhh 我的发言只是自己的感觉，没有任何的政治正确，所以畅所欲言！！好家伙，我才知道附加题是WF题目吗，一直以为是随便一个区域赛找的题，那确实就完全没有必要考虑了，看起来随便写点输入输出口胡一下暴力的思路拿点分就好了
hhhh，可能是因为上课前就看了丁神的评论/doge
算法导论2022课件.zip 苏明老师的课件，密码是Alg2022
上课时间：23spring
对于实验作业代码查重是会去查汇编代码的重复的，所以改变量名、改函数名、多写注释都是没用的。如果非要抄袭就去搜索一下如何避免代码查重吧...常见的有封装函数等方法。但是仍然不建议，因为期末考试的题和平时作业有很大关联。
期末考试：判断填空考的都是一些平时上课ppt里还算适中的知识点，60分大题几乎每道题都来自平时作业（书面+编程，所以都要自己好好做）以及每章ppt上比较基础的例题，也就是说每章最后那些很难的知识（比如动态规划里的基因问题、网络流最后的那些问题），如果平时上课没听懂，那复习的时候也就算了吧。考前复习应当着重看一下这学期留的书面和编程作业，对编程作业最好能稍微记一下伪代码，这次考试直接考了书面作业原题+让你写两道留的编程作业题的算法。
另外这门课确实没法速成...平时要好好听课。我个人感觉它也是这学期所有课里最清晰的一门了，因为它很数学，没有其他课那种奇奇怪怪的细节或需要记忆的东西。苏明老师上课也不讲废话，听起来还是很清晰的。
另外附加题不一定就只能摆，今年最后一题还挺友善的，至少能写点东西。
/上课时间：23spring
我不确定评论的另一位同学(water-00)是否确实是同一期课程。但基本说的都很准确，不再赘述。
需要注意的是今年好像把附加题纳入了总成绩，由于一直在算期末笔试成绩题目的构成：10判断+2填空（210+52=30）+5道大题（10+10+10+15+15=60）+1难度题（10）=100 大概是这样。附加题今年最后一题好像还挺友善的，至少能写点东西，但笔者时间比较紧，没有写完就收卷了。我没有做出那个比较简单的独立集dp,脑子里一直是考点贪心,没转过来.所以好像主观题我的一些细节分扣的不算多.最后的难度题看起来写了基本思路就会给一些分数,也算是很仁慈了.
考前复习应当着重看一下这学期留的书面和编程作业，明白主要的思路。
上课时间：2023Spring
授课教师：苏明老师
特意等到出分来评价一波，总体来说给分一般？由于平时分来到了40分，总评仍然差一点上90，合理怀疑大题扣分扣的很多。有一点需要注意的是，有不少判断题都是书上的原题，记得考试之前刚看到一个有关于稳定匹配的，不一定所有的稳定匹配都有一个优先度为1的匹配，等到考试的时候直接看错题完美错了...并且考试的判断题考察第八章：NP问题考察的还是比较多的，例如归约等，考了好像是三道题，一道题都没看...直接g掉了自己的判断题。仔细想想看，判断题-10，大题再扣一扣，感觉差不多这个分...
填空题是归并排序计数+带负边权的有向图最短路求法，直接手跑SPFA或者暴力枚举即可，难度不大。
大题第一题是摔瓶子，类似于祖传题了，基本每一年都考，而且考的很简单，只有两个瓶子，均值不等式都可以做出来；大题第二题神似2021年数据结构的最后一道题(与2014年的一样)，在logn的时间内查询中位数的问题，不同的是，数据结构中的那道题是两个有序数组，这道题中是可以查询第k大元素，具体直接二分即可；第三道题是一道看起来是独立集的DP问题，一条链，相邻的元素不能同时选取，求点权和最大，所以直接类似于背包问题，对于一个元素，选或者不选，dp[i]=max(dp[i-1],dp[i-2]+v[i])差不多是这样。第四题是给一个网络流，问它的最大流是不是一个值(好像是)，直接暴力增广路；第二问是让你写出一个st割，由于我写第二道大题用时有点长，所以就没多少时间来了，st割直接空着了。最后一道大题主要题意是给定一些字符，这些字符可以用另一些字符替代，最后会一些字符串，问你这些字符串能否被翻译出来。可以直接考虑并查集或者建个图跑个图联通，倾向于并查集为正解，来一个路径压缩时间复杂度就很低了。唯一的难度可能在于英文题面了。。。考试的时候到最后一道题只有10分钟了，勉勉强强写了思路，具体的伪代码都没有写，所以扣分也合理了。记得还有道题是最小二乘拟合的优化，需要用前缀和优化到O(n^2)的级别，具体的代码我放到仓库里了，各位可以看一下，还有部分作业的代码。
大作业我放了一份到github上，有需要的可以参考一下，灵感来自于人工智能导论，感觉还是不错的，各位自取哈，
上课时间：2023Spring
授课教师：苏明老师
特意等到出分来评价一波，总体来说给分一般？由于平时分来到了40分，总评仍然差一点上90，合理怀疑大题扣分扣的很多。有一点需要注意的是，有不少判断题都是书上的原题，记得考试之前刚看到一个有关于稳定匹配的，不一定所有的稳定匹配都有一个优先度为1的匹配，等到考试的时候直接看错题完美错了...并且考试的判断题考察第八章：NP问题考察的还是比较多的，例如归约等，考了好像是三道题，一道题都没看...直接g掉了自己的判断题。仔细想想看，判断题-10，大题再扣一扣，感觉差不多这个分...
填空题是归并排序计数+带负边权的有向图最短路求法，直接手跑SPFA或者暴力枚举即可，难度不大。
大题第一题是摔瓶子，类似于祖传题了，基本每一年都考，而且考的很简单，只有两个瓶子，均值不等式都可以做出来；大题第二题神似2021年数据结构的最后一道题(与2014年的一样)，在logn的时间内查询中位数的问题，不同的是，数据结构中的那道题是两个有序数组，这道题中是可以查询第k大元素，具体直接二分即可；第三道题是一道看起来是独立集的DP问题，一条链，相邻的元素不能同时选取，求点权和最大，所以直接类似于背包问题，对于一个元素，选或者不选，dp[i]=max(dp[i-1],dp[i-2]+v[i])差不多是这样。第四题是给一个网络流，问它的最大流是不是一个值(好像是)，直接暴力增广路；第二问是让你写出一个st割，由于我写第二道大题用时有点长，所以就没多少时间来了，st割直接空着了。最后一道大题主要题意是给定一些字符，这些字符可以用另一些字符替代，最后会一些字符串，问你这些字符串能否被翻译出来。可以直接考虑并查集或者建个图跑个图联通，倾向于并查集为正解，来一个路径压缩时间复杂度就很低了。唯一的难度可能在于英文题面了。。。考试的时候到最后一道题只有10分钟了，勉勉强强写了思路，具体的伪代码都没有写，所以扣分也合理了。记得还有道题是最小二乘拟合的优化，需要用前缀和优化到O(n^2)的级别，具体的代码我放到仓库里了，各位可以看一下，还有部分作业的代码。
大作业我放了一份到github上，有需要的可以参考一下，灵感来自于人工智能导论，感觉还是不错的，各位自取哈，
太详细了！我当时也觉得自己算法总评还不到90感觉非常低，但是想想自己好几个模棱两可的判断题和只写了输入输出的最后一题，这个成绩倒也合理（而且我还没复习到摔瓶子哈哈哈哈哈）。看起来这些大题还是需要有一些算法竞赛的思维在的，虽然可能并不是太难。
@Emanual20
上课时间：2023Spring
授课教师：苏明老师
特意等到出分来评价一波，总体来说给分一般？由于平时分来到了40分，总评仍然差一点上90，合理怀疑大题扣分扣的很多。有一点需要注意的是，有不少判断题都是书上的原题，记得考试之前刚看到一个有关于稳定匹配的，不一定所有的稳定匹配都有一个优先度为1的匹配，等到考试的时候直接看错题完美错了...并且考试的判断题考察第八章：NP问题考察的还是比较多的，例如归约等，考了好像是三道题，一道题都没看...直接g掉了自己的判断题。仔细想想看，判断题-10，大题再扣一扣，感觉差不多这个分...
填空题是归并排序计数+带负边权的有向图最短路求法，直接手跑SPFA或者暴力枚举即可，难度不大。
大题第一题是摔瓶子，类似于祖传题了，基本每一年都考，而且考的很简单，只有两个瓶子，均值不等式都可以做出来；大题第二题神似2021年数据结构的最后一道题(与2014年的一样)，在logn的时间内查询中位数的问题，不同的是，数据结构中的那道题是两个有序数组，这道题中是可以查询第k大元素，具体直接二分即可；第三道题是一道看起来是独立集的DP问题，一条链，相邻的元素不能同时选取，求点权和最大，所以直接类似于背包问题，对于一个元素，选或者不选，dp[i]=max(dp[i-1],dp[i-2]+v[i])差不多是这样。第四题是给一个网络流，问它的最大流是不是一个值(好像是)，直接暴力增广路；第二问是让你写出一个st割，由于我写第二道大题用时有点长，所以就没多少时间来了，st割直接空着了。最后一道大题主要题意是给定一些字符，这些字符可以用另一些字符替代，最后会一些字符串，问你这些字符串能否被翻译出来。可以直接考虑并查集或者建个图跑个图联通，倾向于并查集为正解，来一个路径压缩时间复杂度就很低了。唯一的难度可能在于英文题面了。。。考试的时候到最后一道题只有10分钟了，勉勉强强写了思路，具体的伪代码都没有写，所以扣分也合理了。记得还有道题是最小二乘拟合的优化，需要用前缀和优化到O(n^2)的级别，具体的代码我放到仓库里了，各位可以看一下，还有部分作业的代码。
大作业我放了一份到github上，有需要的可以参考一下，灵感来自于人工智能导论，感觉还是不错的，各位自取哈，
太详细了！我当时也觉得自己算法总评还不到90感觉非常低，但是想想自己好几个模棱两可的判断题和只写了输入输出的最后一题，这个成绩倒也合理（而且我还没复习到摔瓶子哈哈哈哈哈）。看起来这些大题还是需要有一些算法竞赛的思维在的，虽然可能并不是太难。
呜呜 仔细一想 苏明老师的平时分给的应该是比较大方的 都给的差不多满分 只不过可能卷面批改的比较严格
上课时间：2023Spring 授课教师：陈晨老师，刘贝贝老师~都是很可爱，讲的很好的老师 记忆中的考题： 填空： 1.不稳定匹配 2.上界传递性 3.二分图判定＋伪代码 4.贪心策略 最短路径伪代码＋手算 大题: 5.mster定理 6.动态规划概念 设计c[i,j] 7.广度深度优先搜索伪代码，判断二分图伪代码 7.分支定界手算 8.随机快排的描述，时间复杂度 其他填空：DAG,奇偶数边（第二章，第三章的一些定理) 让写伪代码的作业里都包括，填空都是课上练过的！ cc老师的ppt是英文的，考前抱佛脚不太可。
2024年春 苏明老师 今年没有上机，平时分也提升到了40%，算是比较友好了。有一次课后作业，期末考全出了，老师太好了。课后编程题还是祖传的。 期末考试： 选择题：大多来自PPT原话，熟悉的同学可以直接选，不熟悉的需要判断一下 填空题：dp和最大流的引例。 解答：摔瓶子，前缀和，最小延迟调度，二部图&最大流，带权区间调度。都是PPT的原题，比没有前辈们那么难。 难度题：可能看错题意了，就不瞎说了。 总体来说，今年期末比前辈们的简单，大多来自作业和PPT，希望分数好一点，谢谢苏giegie~
上课时间：2024春 授课老师：苏明老师 给分：很好（本人 90+，身边同学不少85+和90+） 总体评价：我个人给予这门课很高的评价，在我修读的课程中排行前三。 分数构成：作业30+大作业10+期末考试60（本学期也无上机考试） 上课签到：课上会点名提问和让上机作业写的好分享心得（虽然分数构成中无出勤，但老师表示点到不在会扣分，如果一次不在后面会被点好几次）。实验课不点名且无授课内容，可以找助教答疑。 上课内容：算法的各方面内容，个人感觉质量是非常高的，涵盖各种基本算法，老师的水平也很高，非常推荐认真学习，特别是网络流部分。主要缺点可能是编程练习较少，推荐把PPT里的算法都自己写一遍。 课程安排 o 第 1 章：GS匹配 o 第 2 章：时间复杂度 o 第 3 章：图论 o 第 4 章：贪心算法 o 第 5 章：分治算法 o 第 6 章：动态规划 o 第 7 章：网络流 o 第 8 章：NP问题
作业：（老师每年可能会改变作业内容，本学期是1次纸质作业，6次编程作业） 理论作业：前缀和和摔瓶子（两道题考试都考到了，并且理论作业分数的占比疑似不低，所以一定重视理论作业） 编程作业：
- 稳定匹配
- 拓扑排序（图论）
- 磁带储存（贪心）
- FFT（分治算法）
- 分段直线拟合（动态规划）
- 飞行员配对问题（最大流/匈牙利算法） FFT和飞行员配对问题比较难，其他的题中规中矩，会者不难，但注意一定一定不要抄袭，每周都有被抓的。 大作业：写一篇与算法相关的论文（虽然理论上可以与并行打通，但个人认为不太现实） 老师建议：串行算法，确定性问题，与生活实际相结合，展示了一篇往年优秀作业，是一道课本课后题，一般给7-8分 助教建议（因为助教不一样了所以仅供参考）：10页以内，不推荐去洛谷等网站找道题写题解 个人建议：可以考虑有背景的课本课后题或者去网站找道有多种不同复杂度的题写题解。
考试：题型与流传的22年卷子很相似 判断：大部分中规中矩，有一两道比较难的，主要是课堂内容，PPT和书本课后题。 填空：一道带负权的最短路（动态规划，计算两稍大），一道最大流。 解答：一道摔瓶子（k=3），一道前缀和（两道都是理论作业） 应用：一道最小延迟调度（说明贪心策略并证明，交换论证证明，PPT原题），一道背包问题（不太确定，但差不多，分析伪代码时间复杂度和优化，它是递归的O（2^n），用记忆化搜索优化为O（n），PPT上知识点），一道二部图和二分匹配（第一问bfs，PPT上原题，第二问最大流/匈牙利算法，上机原题） 困难：英文题，貌似是概率论+高数（？不太确定，随便写点骗骗分） PS：可以在考试前问苏明老师一下题目，会有点作用（）
上课时间：2024春 授课老师：苏明老师 给分：很好（本人 90+，身边同学不少85+和90+） 总体评价：我个人给予这门课很高的评价，在我修读的课程中排行前三。 分数构成：作业30+大作业10+期末考试60（本学期也无上机考试） 上课签到：课上会点名提问和让上机作业写的好分享心得（虽然分数构成中无出勤，但老师表示点到不在会扣分，如果一次不在后面会被点好几次）。实验课不点名且无授课内容，可以找助教答疑。 上课内容：算法的各方面内容，个人感觉质量是非常高的，涵盖各种基本算法，老师的水平也很高，非常推荐认真学习，特别是网络流部分。主要缺点可能是编程练习较少，推荐把PPT里的算法都自己写一遍。 课程安排 o 第 1 章：GS匹配 o 第 2 章：时间复杂度 o 第 3 章：图论 o 第 4 章：贪心算法 o 第 5 章：分治算法 o 第 6 章：动态规划 o 第 7 章：网络流 o 第 8 章：NP问题
作业：（老师每年可能会改变作业内容，本学期是1次纸质作业，6次编程作业） 理论作业：前缀和和摔瓶子（两道题考试都考到了，并且理论作业分数的占比疑似不低，所以一定重视理论作业） 编程作业：
- 稳定匹配
- 拓扑排序（图论）
- 磁带储存（贪心）
- FFT（分治算法）
- 分段直线拟合（动态规划）
- 飞行员配对问题（最大流/匈牙利算法） FFT和飞行员配对问题比较难，其他的题中规中矩，会者不难，但注意一定一定不要抄袭，每周都有被抓的。 大作业：写一篇与算法相关的论文（虽然理论上可以与并行打通，但个人认为不太现实） 老师建议：串行算法，确定性问题，与生活实际相结合，展示了一篇往年优秀作业，是一道课本课后题，一般给7-8分 助教建议（因为助教不一样了所以仅供参考）：10页以内，不推荐去洛谷等网站找道题写题解 个人建议：可以考虑有背景的课本课后题或者去网站找道有多种不同复杂度的题写题解。
考试：题型与流传的22年卷子很相似 判断：大部分中规中矩，有一两道比较难的，主要是课堂内容，PPT和书本课后题。 填空：一道带负权的最短路（动态规划，计算两稍大），一道最大流。 解答：一道摔瓶子（k=3），一道前缀和（两道都是理论作业） 应用：一道最小延迟调度（说明贪心策略并证明，交换论证证明，PPT原题），一道背包问题（不太确定，但差不多，分析伪代码时间复杂度和优化，它是递归的O（2^n），用记忆化搜索优化为O（n），PPT上知识点），一道二部图和二分匹配（第一问bfs，PPT上原题，第二问最大流/匈牙利算法，上机原题） 困难：英文题，貌似是概率论+高数（？不太确定，随便写点骗骗分） PS：可以在考试前问苏明老师一下题目，会有点作用（）
所以摔瓶子真的可以连续考至少5年……