《算法导论-2021秋》课程小结
本文最后更新于：2022年11月23日 11:09
适用人群：中国矿业大学计算机科学与技术专业学生
免责声明：
我是19级计科，不代表其他年级，不代表其他专业，不代表这个学科就该这么学。题干为个人回忆版本，同时，由黄凯同学提供第四题题干，并进行题干二次核对，已尽力与原题目描述保持一致。答案来自本人理解，不确保与老师理解完全一致。
校订记录：
2022年11月21日：@Estella @颗粒 等，对第一题答案提出疑问。
2021秋期末真题
第一题（10）
给出了一个大整数乘法算法的描述，对于n位乘法，仅作3次n/2位的乘法和1次n位的加法即可
- 根据题意写出递归公式（5）
- 求算法复杂度（5）
考概述-主定理法等。
不确定$O(n)$还是$O(1)$，欢迎评论区讨论。
第二题（10）
现有程序设计比赛公示名单，已经按照学号非降序排列好了，现在插入学号为x的学生
- 写出算法描述，如何找到x之前的学生的最大序号i和x之后的学生的最小序号j（5）
- 最坏情况下的算法复杂度（5）
考分治-二分搜索。
- 结合题目内容描述二分搜索即可。（但我不是很理解为什么要说非降序排列，直接说升序排列不可以吗，难道有一个人学号出现多次，有重复元素吗，考试我是按照无重复元素写的），最后有
i = mid - 1与j = mid + 1- $O(\log n)$
第三题（10）
开了个小卖部，给出1-12月各月的盈利，含负数，负数就是亏损，求连续月份的最大盈利和
- 写出算法描述（5）
- 最坏时间复杂度分析（5）
考动态规划-最大子段和。
- 结合题目内容描述最大子段和算法即可。
- $O(n)$
第四题（20）
体育馆预约，给出十个人预约的开始时间与结束时间，现在进行安排
- 写出算法描述（10）
- 能安排多少人（5）
- 能安排哪些人（5）
考贪心-活动安排问题。
- 结合题目内容描述活动安排算法即可。
- 算出来就出来了。
- 算出来就出来了。
第五题（20）
有五堆石子，数量已知
- 只能取得两个相邻石子合并，这一次合并的代价是两堆石子数量之和，求合并成一堆最小代价（题目链接）（10）
- 任意取得两个石子合并，这一次合并的代价是两堆石子数量之和，求合并成一堆的最小代价（10）
- 考动态规划-石子合并。
- 考贪心-哈夫曼。
- 对于先入为主与考试时间分配策略问题，见感悟部分。
第六题（15）
打算法比赛，还有五个小时，还有五个题目没做，给出题目价值和预计AC题目时间，利用回溯法求最优解
- 什么集合类型（5）
- 剪枝函数（5）
- 画树（5）
考回溯-01背包。
子集树。
都是定义
分支剪枝：$cw>c$
限界剪枝：$cp+cr \leq bestw$
都是定义，没啥说的。
第七题（15）
给出一个图，点是学生，线是学生存在闺蜜关系，求最大闺蜜团，要求利用分支限界法，利用优先队列。
- 什么集合类型（5）
- 剪枝函数（5）
- 画树（5）
考分支限界-最大团问题。
子集树（对于知识点记忆与考试时间分配策略问题，见感悟部分）
分支剪枝：存在当前加入的点与任意已成团的某个点在原图没有连线
限界剪枝：$num = c + r \leq best$
优先级：$num$
都是定义，没啥说的。（1,3,4,5）
关于考试常见问题
考不考证明？
不考，顶多问你证明复杂度多少，或者问你复杂度多少，不涉及证明
考不考代码？
不出题直接考，顶多问就是题目问你这个问题怎么解决，你只要描述算法 文字描述 框图 伪代码都行，没有限定。
计科算法和信安的考的不一样？
2016培养方案：
计科：专业主干：算法导论（M08106）
信安：专业主干：算法设计与分析A （M08307）
信科：专业选修： 算法设计与分析 B（M08335）
不一样，不是一张卷子，考试内容不一样，教学内容略有不一样。信安笔记和考试分析参见隔壁。
算法理论复习 | 秋月日常
http://lcy5201314.top/2021/11/18/suan-fa-li-lun-fu-xi/
CUMT算法考试总结 | 秋月日常
http://lcy5201314.top/2021/12/08/2021-12-8-suan-fa-zong-jie/
2020培养方案：
计科：专业主干：算法导论（M08106）
信安：专业主干：算法设计与分析A （M08307）
大数据：专业选修：算法导论（M08106）
人智：专业大类基础必修：数据结构与算法分析A（M04323）
关于考试的感想
- 考试整体时间感觉不是很充裕，如果每道题正常速度做完且不出错的话，应该只能预留出几分钟而已。
- 我的个人建议是，即便题干小问没有说明要你写出最后大题干计算得出答案，最好也要把大题干的实际问题答案给求出来，并且明示计算结果放在最后。
- ⚠关于第四大题：至于为什么第四题没有做，空白了，20分直接不要，是因为看到“合并石子”我就直接跳过了，其他的句子是一个字也没有多看，这是极为严重的错误。在我印象中很早就知道有合并石子这个题目，但是当时觉得很难，做不出来，后来学习算法之后也没有重新去学习该怎么做这个题（但是真的是很简单的…），因此条件反射看到“石子”我就认为自己不会做，导致直接跳题，甚至第二小问很简单的哈夫曼都没有注意到要去做。所以平时遇到不会的题目一定要及时去做，去分析相同点，多去遇见一些类似的题型，多刷题和总结，融会贯通。
- ⚠关于第七大题：首先是复习不认真，算法知识点记得不牢固，子集树还是排列树纠结了很久（特别是前面一题已经考了子集树为什么还是考子集树，我觉得不应该…导致误判，至少有20分钟我在研究怎么画排列数，节点的字母写到UVW的时候开始怀疑自己是不是弄错了，然后醒悟过来了…我的节点优先级一直都没有变（因为如果按照排列树的话，$num$一直都等于原图节点数量，不像子集树一样会减小）然后是明知道画树已经非常麻烦了，又要重画，为什么不再重新看看第四大题，哪怕看一看题目都好，不要这么固执，可能也是时间已经很紧张了，心理作用，过分看重考试结果了，所以心态愈发不稳定。
- 平时复习一定要全方位，第一是要课本知识记忆准确，第二是强调泛化能力，从课本脱离，应用到各个场景。
- 这波是真的寄了，战前准备和战术上都极其失误，预估考试卷面70左右，平时分看老师了，学弟学妹们一定要好好学啊，血泪教训已经摆在这里了。
关于课程的感想
- 上课的时候没有怎么认真听，注意力还是不够集中，其实认真听还是听得懂的，只是不能长期保持这种状态，老师教的还是不错的，就是不认真，课堂测验学压缩算法都是十分钟看ppt立马学会计算结果的，然后还算对了（所以感觉逼迫自己努力去学习的话，应该还是能学好的，也许不是自己学习能力的问题吧）基本上课程学会都是结课后看ppt，可能平时手机的影响确实是太大了…不够自律。上课时间还是要好好把握住的。
- 算法是计算机专业非常重要的一门课程，算法能力也体现一个计算机人的专业程度，程序设计竞赛考算法，面试需要算法，管饭碗的东西为什么不认真学呢。
- 也没有主动去多深入学习一下，特别是关于定理的证明，因为不考就不深入探究了，其实只是我们学校不考试，别的学校本科也会有考察的，可能研究生面试复试之类的也会考察。真要做只适应应试的做题家，肯定是走不远的。
- 算法虐我千百遍…哎…不会再爱了…挺不好受的，希望今后有空多看黑书，多看看MIT的算法导论课程，以及面试算法题，然后多加实践，多码代码，刷刷leetcode和acwing等面试相关算法题，加油。