2023秋 课程号：COMP6001P02
- 课程难度：困难
- 作业多少：中等
- 给分好坏：一般
- 收获大小：很多
| 选课类别：基础 | 教学类型：理论课 |
| 课程类别：研究生课程 | 开课单位：计算机科学与技术系 |
| 课程层次：硕士 | 学分：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选举、生成树构造、广播和敛播、广度/深度优先搜索、最短路径、最大独立集等分布式算法；介绍异步共享存储器和网络算法、重点介绍互斥和资源分配问题，介绍哲学家用餐算法、着色算法、有向无环图算法以及哲学家饮水算法等。
- 课程难度：困难
- 作业多少：很少
- 给分好坏：一般
- 收获大小：很多
- 难度：困难
- 作业：很少
- 给分：一般
- 收获：很多
给彭老师拉一下平均分
我是隔壁徐老师班的，但是全程使用彭老师的课件学习，没有参加徐老师的习题课，更没有复习徐老师给的习题课讲义，所以至少最后一题（设计算法证明1/2-近似）没有做出来，并不是既得利益者。彭老师的PPT做得很条理，适合学习，（而且讲了很多不考但挺有用的，比如面试常问的布隆过滤器）彭老师本身是研究TCS的，算是专业对口了。这种用心教学的青年教师值得鼓励。
今年的题目出得很不好，严重偏向徐老师。但是除了最后一道题外，其他题目的思想彭老师的课件里都有。最小Vertex Cover的2-近似算法及其分析，彭老师的课件里也涉及了，不是原题但是思想一模一样。希望来年各位老师出题要做到公平公正。
- 课程难度：困难
- 作业多少：中等
- 给分好坏：杀手
- 收获大小：很多
- 难度：困难
- 作业：中等
- 给分：杀手
- 收获：很多
快跑！！！！
复习的时候你就知道pp班ppt量大又基本没有原题（0分），隔壁xxh班ppt量少且考试原题接近大半都讲过。
ppt内容确实多，我整整复习了三天，感到非常充实，但是我觉得对我未来发展并不会起到什么作用。
对pp老师没有恶意。
但是一个班级大半原题都见过，另一个班级一题都没有，出卷人对彭老师班级的学生的恶意是不是有点大了？
附助教原话：
“老师说按照我们的上课内容准备”，“题目不会很难，大家以ppt为主”。
如果真听了助教的话去复习，那么你就错过了最优复习路径：看隔壁班的算法习题。
2024.2.21
给的分数还不错，加分
- 课程难度：困难
- 作业多少：中等
- 给分好坏：一般
- 收获大小：一般
- 难度：困难
- 作业：中等
- 给分：一般
- 收获：一般
先给个8分吧，等出分了再更
这门课一共分为三个章节，分别是汪炀老师教的分布式算法，彭攀老师教的近似算法和随机算法。其中分布式算法那一部分从2014年起就没太多的变化，B站上有相关的讲课视频，个人感觉听1.25倍速视频比听老师本人讲课要更容易听明白一点，（分布式算法的PPT不搭配讲课看起来就跟天书一样）；近似算法和随机算法的slides内容是比较新的，没有什么往年资料可以参考，挺多都是一大段一大段的证明，但观感上比分布式算法的PPT要好一点，许多深入一点的证明不需要搞明白。
每一章节都会有一次作业，整个学习一共三次作业，作业量不算大，分布式算法的作业两个班都是一样的，而且往年可参考的资料也不少；近似算法和随机算法三个平行班有挺大一部分是重合的，但是作业难度也不小，有的需要查证论文，需要发挥群众的力量.....
今年考试的题型据说非常偏向xxh班，往年考试题很重要很重要很重要！！！（重要的事情说三遍）
2.26 出分更新，给分很好，加一分，
PS:据同学说英文班也给分很好。
- 课程难度：中等
- 作业多少：中等
- 给分好坏：超好
- 收获大小：很多
- 难度：中等
- 作业：中等
- 给分：超好
- 收获：很多
这学期这个课堂是两位老师上课，前半部分是汪炀老师讲分布式算法，后半部分是彭攀老师讲近似算法和随机算法。
个人比较喜欢彭攀老师的讲课、slides和作业题。
1）首先是slides很赞，是用beamer做的简洁素雅风格，slides的内容很充实（多），但是相比去年彭攀老师自己一个人带的课已经有所删减了，知识点和例子的步骤、公式推导写得都很清楚，写作业的时候看着很舒服，遗憾的是复习备考时间紧，没有时间细看，反而因为内容多，对很多知识都是印象不深；
2）老师讲课也是讲得很细致（虽然一个学期没听过几次课），有同学说老师讲课就是念ppt，这个其实我觉得不太贴切，毕竟ppt本来就写得好，那讲课的时候把ppt上的内容讲清楚了不能说是缺点吧；
3）作业题使用Latex写的，发布的时候老师会和源码一起发布，感谢老师，让我完善了自己的作业模板，题量是两次＋每次4~5题，作业题难度比考试题难度大。
4）考试的话个人觉得这次期末老师也没有为难大家，复习的时候是很担心很多内容不熟考到不会，但是考试的时候发现是比较基础的内容，不会挑slides最难的那些东西考（再次认识到考前焦虑、考前很多人追着最难的内容复习的meaningless），虽然没有原题，但是把老师slides看了也可以做出来。
而汪老师的分布式算法部分就觉得有点boring了，内容是延续了好多年都没有改过的，slides做得也不是很好（黑底白、黄字），有一章是完全看不懂，作业题也是经典老题，有往年前辈参考答案这一点可能是能省一些时间吧，期末考试也基本都是曾经出现过的题目。
