2022春 2021秋 2020秋 2019秋 2018秋 2017秋 2016秋 2015秋 课程号：COMP6001P04
- 课程难度：困难
- 作业多少：中等
- 给分好坏：一般
- 收获大小：一般
| 选课类别：基础 | 教学类型：理论课 |
| 课程类别：研究生课程 | 开课单位：计算机科学与技术系 |
| 课程层次：硕士 | 学分：3.0 |
算法设计与分析是计算机科学与技术各专业硕士研究生必修的基础课。本课程主要介绍概率算法、近似算法和分布式算法基础，使学生掌握概率算法、近似算法和分布式算法设计及分析的基本方法。主要内容分为如下三个部分。
一. 概率算法，主要包括：
1．基本概念：主要介绍概率算法的特点、意义、分类、复杂性分析方法；2．数字概率算法：重点介绍π值计算、数值积分、概率计数以及其它数值算法的设计和分析；3．Sherwood算法：以选择和排序、随机预处理、有序表搜索等问题为例重点介绍Sherwood算法的概念和特点，以及算法设计和分析的方法；4．Las Vegas算法：以n－皇后、模p平方根、整数的因式分解等问题为例重点介绍Las Vegas算法的概念和特点，以及算法设计和分析的方法；5．Monte Carlo算法：重点介绍一致、有偏、精度分析等基本概念，以主元素、素性判定、矩阵相乘等问题为例，重点介绍Monte Carlo算法设计、分析和改进的方法。
二、近似算法，主要包括：
1．NP完全性理论：主要介绍图灵机等计算模型、问题变换及计算复杂性规约、P类问题、NP类问题、NP-hard和NPC问题、Cook定理等；2.基本概念：介绍优化问题的近似解分类、近似算法的绝对性能保证、相对性能保证（包括绝对性能比、渐近性能比、最佳可达性能比）、近似模式（多项式近似模式、完全多项式近似模式）、绝对近似算法之否定、相对近似算法之否定等；3.基本算法：图的顶点着色、图的边着色、多机调度、装箱、旅行商、顶点覆盖和最大独立集问题等问题的近似算法。
三、分布式算法基础，主要包括：
1．基本概念：介绍分布式系统、计算模型、复杂性度量标准等分布式计算的基本概念；2．分布式算法基础：主要介绍同步和异步网络模型，同步/异步环中的Leader选举、一般网络中的Leader选举、生成树构造、广播和敛播、广度/深度优先搜索、最短路径、最大独立集等分布式算法；介绍异步共享存储器和网络算法、重点介绍互斥和资源分配问题，介绍哲学家用餐算法、着色算法、有向无环图算法以及哲学家饮水算法等。
- 课程难度：中等
- 作业多少：很多
- 给分好坏：一般
- 收获大小：很多
- 难度：中等
- 作业：很多
- 给分：一般
- 收获：很多
助教总结的课程提纲（推荐）：中科大算法设计与分析.pdf
课程由分布式算法和随机算法两部分组成。
分布式算法 PPT：
- 第一次课(Modified).ppt
- 第二次课(Modified).ppt
- 第三次课(Modified).ppt
- 第四次课(Modified).ppt
- 第五次课(Modified).ppt
- 第六次课(Modified).ppt
- 第七次课(Modifier).ppt
- 第八次课(Modified).ppt
期末考试是开卷，建议下载打印这个：中科大_分布式算法_白色打印版.pdf
随机算法 PPT：
只有两次作业。第一次作业是编程题，第二次作业是证明题。
- 我的作业：第一次作业-SA14011026-李博杰.docx 第二次作业-SA14011026-李博杰.docx （之前传错了，多谢 ＠负一的平方根 指正）
- 助教的第二次作业答案：分布式算法作业答案.pdf
2013 年试卷：算法设计与分析试卷.zip
这个课程的分布式算法部分比较抽象，但是挺有用的。
分布式算法部分建议参考陈国良院士的《并行算法设计与分析》（第二学期的并行算法课程也要用，算法设计与分析这门课的分布式算法都是从这本书上摘出来的，书上讲得更清楚）。
- 课程难度：困难
- 作业多少：很多
- 给分好坏：超好
- 收获大小：很多
- 难度：困难
- 作业：很多
- 给分：超好
- 收获：很多
黄老师挑染真帅（
我感觉老师们讲的都不错，就是稍微跑点神就听不懂了，今年是全网课，所以会稍微好一点。
感觉三个方向的算法都有其意义和重要性，学后或多或少有收获吧，绝对不算是没有用的课。
推测往后卷子基本就是个55开，一半真题出现过，讲过，留过作业，另一半为需要基于ppt内容自行分析解答的新题。
估计结课后就用不了了
自己整理的复习资料 + 历年真题 + 22回忆真题
有用留个赞吧~
- 课程难度：困难
- 作业多少：中等
- 给分好坏：超好
- 收获大小：一般
- 难度：困难
- 作业：中等
- 给分：超好
- 收获：一般
2024.2.3 更新：祝贺黄刘生老师光荣退休！（图源杨威老师，新闻稿见链接）
2022.7.26 更新
这门课是2020新版培养方案中 计算机科学与技术专业 硕士生唯一一门必修的学科基础课，也是许多其他学院培养方案中列出的基础课。由于今年扩招，选课人数达到了460人，因此开了3个班。
课程的内容包括概率算法、近似算法和分布式算法三部分（具体内容在上面的课程简介中已经写得很清楚了），由黄刘生老师和汪炀老师共同讲授。黄刘生老师负责概率算法和近似算法，汪炀老师负责分布式算法的部分，两位老师的实验室都是在苏州，每周来合肥上课。（据说黄老师明年退休，所以2021级算法课应该是他带的最后一届了）
这门课相比于大部分同学本科学过的算法而言，应该属于进阶的内容了，课程的出发点也是非常好的，但是由于很多的知识点过于抽象，因此上课的时候我基本上是跟不上（加上今年在先研院上课，效果非常糟糕），体验并不是太好，全靠课下自学。这里强烈推荐科大网络课堂的教学视频，是两位老师2014年上课时的录像，我觉得讲得会更清楚一些：http://wlkt.ustc.edu.cn/video/detail_2101_20993.htm 这门课能坚持下来全靠这个视频，看完这个视频我觉得课上讲得好像也没那么难？
概率算法部分中会涉及很多的数论知识，主要是在举例子的时候会用到，这里对一些本科没接触过数论知识的同学可能不太友好。近似算法部分讲了NP完全性理论（今年新开的“形式语言与计算复杂性”课程会更详细地介绍这部分内容）和一些基本的近似算法。这两部分黄老师讲得都很认真。汪炀老师负责的分布式算法部分更为抽象，而且汪老师上课写字非常小，总感觉不太耐心的样子，好像大部分同学都没听明白。
课程没有指定教材，所以都是靠用了十几年的PPT，两位老师基本上都是照着PPT讲，也很少会拓展一些东西。课程考核包括作业+最后的期末考试，平时没有点名。作业就是PPT上面的题目，每年都不会变。期末考试好像是黄老师一个人负责吧，每年都有很多重题，特别是概率算法和分布式算法的部分。但是这两年黄老师特别喜欢考近似算法（包括简答+算法设计），所以这两年的新题都出自近似算法的部分。所以大家复习的时候只要把PPT消化，看好往年卷子应该就没问题了。
这里吐槽一下，这门课的10位助教几乎没什么存在感，除了发布一下作业提交情况和一些通知。有时候同学们在群里问一些问题也不能及时解答，私聊有时候也不会。最后只安排了一次习题课，三位助教千辛万苦从苏州过来只讲了20分钟。但是今年给分超好，大部分同学都有90+。
综合来看，黄老师的部分可以给8分，汪老师的部分只能给6分，助教-1分，给分好+1分。所以我觉得这门课可以给到8分。
- 课程难度：困难
- 作业多少：很少
- 给分好坏：一般
- 收获大小：一般
- 难度：困难
- 作业：很少
- 给分：一般
- 收获：一般
2022考题有：
选择题（和往年重复题目很多，或者说一模一样，20分
简答题：
1，同步环选举算法，怎样修改使得一个阶段允许k个消息同时传输（10
2，匿名环不存在选举算法证明，O(n^2)算法复杂度分析，O(nlgn)算法描述与复杂性分析（15
3，给定错误率，MC算法运行次数计算（10
4，归约最大团问题（10
算法题：
1，（作业）sherwood算法搜索有序表，分析复杂度（15分
2，设计最小点覆盖的近似算法，近似比不大于2（20分）
---------------------------------
更新：9月份出分，90分，时间太久远了，就不额外评价了。老师最后一节课一定要听，会透露考试内容
- 课程难度：中等
- 作业多少：很少
- 给分好坏：一般
- 收获大小：一般
- 难度：中等
- 作业：很少
- 给分：一般
- 收获：一般
课程内容前面已经有人说的很清楚了，基本和往年没有变化，绝大部分内容参照的是MIT的6.046J，如果需要自学可以花点时间直接看MIT的lecture。
近似算法的ppt感觉写的不是很好，逻辑比较混乱，很多东西光看ppt感觉也没有解释的很清楚。尤其是今年作业里的一道证明题（多机调度的证明），建议直接去找文献。
今年考试题目画风突变，选择题小于等于10分==全是大题。第一题是为什么问题之间可以相互规约但是有无近似算法的情况不一样；第二题是为什么scaling性质的渐进和绝对是一致的；第三题是最短路径的规约问题；第四题是构造一个TSP问题的近似比是2的情况构造；第五题是flooding算法；第七题是LV算法；第八题是set cover的规约问题
以上题目仅供参考，顺序和题目可能因为记忆问题出现错乱，但是大概是这些题目。最后给分也还行，虽然也不是很高，但是研究生已经不太在乎绩点了，超过75就行，开摆。
- 课程难度：中等
- 作业多少：中等
- 给分好坏：一般
- 收获大小：一般
- 难度：中等
- 作业：中等
- 给分：一般
- 收获：一般
今年试卷题型变动，没有选择题了
基本没有往年原题了
老师说：选择题不超过十分
然后卷子上一条选择题没有
那确实是不超过十分
PPT和作业多年没变
- 课程难度：中等
- 作业多少：中等
- 给分好坏：杀手
- 收获大小：一般
- 难度：中等
- 作业：中等
- 给分：杀手
- 收获：一般
稀里糊涂一学期，稀里糊涂去考试，拖到9月份才出分，给分相当不咋地，不过也对得起在这门课上花的时间，至今我都不懂这门课为什么是基础课orz
- 课程难度：困难
- 作业多少：中等
- 给分好坏：一般
- 收获大小：没有
- 难度：困难
- 作业：中等
- 给分：一般
- 收获：没有
先打个八分吧，目前成绩没出来不好评价
难度、作业什么的之前同学也说了，这里简单介绍下22年春考试的范围吧（过了几天有的记不清了）
首先这次考试有20分的选择题，这些选择题大约6、7题都是历年的原题。
之后是简答题，简答题考了1.蒙特卡洛算法，55%的偏真算法，至少执行多少次才能达到95%准确率（历年原题）；2.环上选举问题；3.也是分布式的题，具体忘了；4.团问题怎么变为判定问题，需要的时间复杂度是多少
最后是算法题，1.静态链表的shrewood算法（就是ppt上的作业题）；2.给出一个性能比为2的覆盖集的算法，并进行证明，给出时间复杂度
- 课程难度：困难
- 作业多少：中等
- 给分好坏：超好
- 收获大小：一般
- 难度：困难
- 作业：中等
- 给分：超好
- 收获：一般
两位老师上课都算还行，问题是PPT很老，而且很多定义不清，没有教材无法对照形成体系。课程名字是算法设计与分析，基本就是给一个算法然后分析时间复杂度，除了概率算法那一块我不知道设计体现在哪。
今年全是大题，近似算法占了极大比例。
给分，看群里大部分人应该都还不错（except me）。综上，个人体验不佳（仅代表个人）
- 课程难度：中等
- 作业多少：很少
- 给分好坏：一般
- 收获大小：一般
- 难度：中等
- 作业：很少
- 给分：一般
- 收获：一般
两位老师的上课体验都还不错。今年是汪老师先讲的，个人觉得讲的很细致；黄老师也讲的很好，但到近似算法那里还是接受不了。复习的时候觉得自己作为非计科的，为什么要看这些东西。艰难的过程后，把PPT上的东西都搞懂了，考试题自认为答得不错，最后3.3。以后试卷都不出往年题的话，这门课还是有难度的。
- 课程难度：困难
- 作业多少：中等
- 给分好坏：一般
- 收获大小：一般
- 难度：困难
- 作业：中等
- 给分：一般
- 收获：一般
自认为算学的认真的。直到考试。。
题型变化太大了，往年题压根没考，运气很不好，题型改革过渡期给人带来了太大的痛苦！！！（谁也没想到怎么全是大题）
考前：充分复习了两遍，往年题都做了也争取搞懂了
考时：这都啥啊。尤其是本来就抽象的近似算法部分，怎么考了这么多？？？
- 课程难度：困难
- 作业多少：中等
- 给分好坏：一般
- 收获大小：一般
- 难度：困难
- 作业：中等
- 给分：一般
- 收获：一般
计院必修课，对于其他学院的同学，还是快逃吧！内容很难，委婉的说是没什么用，复习的时候很崩溃！我觉得如果不是最后调分把总评调的高很多，这课的评价要低很多。及格分是考虑到黄老师的辛苦教学，汪老师的教学态度我觉得是负分，板书字写得那么小，同学们提意见，态度很不耐烦也没有改变。
- 课程难度：简单
- 作业多少：很少
- 给分好坏：超好
- 收获大小：一般
- 难度：简单
- 作业：很少
- 给分：超好
- 收获：一般
总体推荐。（不过这门课是计院必修，没法选
上课风格：
- hls：还不错（虽然他明年开始就不带了），一些概率算法看着就很难很麻烦，感觉肯定不会考（比如求离散对数，离散二次根号）
- wy：两级分化较为严重。有人说他讲的很抽象，有人表示讲的挺好。
- 不过这门课就算不去，课后啃ppt也足够应付考试了。
- 不点名。
作业：全是往年题。答案可以自行搜索。
考试：今年概率算法的比例与近似算法相当，少部分是分布式算法。往年题有一定价值，选择和简答有大量往年题。（不过明年hls不教了，情况可能有变
给分：很好。75+有95%，不及格率在1%左右。（选课四百多人，群里共486人）
- 课程难度：困难
- 作业多少：很少
- 给分好坏：超好
- 收获大小：一般
- 难度：困难
- 作业：很少
- 给分：超好
- 收获：一般
- 课程内容：概率算法、近似算法、分布式算法。其中分布式算法由于时间问题讲得很仓促。
- 讲课：黄老师负责概率+近似，讲得很细致，基本都能听懂。汪老师虽然讲得快一些，但会配上自己的画图帮助理解。但分布式算法有些抽象，到后面同步环选举那块还是一头雾水。
- 考试：选择简答和往年试卷重复度非常高，两道算法设计题是：求图的最小匹配集算法+最大独立集近似算法设计。
- 给分：超级能奶。本人两道算法设计题都是无脑贪心，最后总评4.3。看出分后群里同学的反应，最终分应该都要比预估高不少。
- 收获：对我而言很少。
往年试卷下载地址：https://download.csdn.net/download/qq_33254440/12679999?utm_source=bbsseo
2019秋试卷：2019秋算法.pdf
另外，黄老师照片真的帅
