2023秋 课程号：COMP6001P01
- 课程难度：中等
- 作业多少：中等
- 给分好坏：超好
- 收获大小：一般
| 选课类别：基础 | 教学类型：理论课 |
| 课程类别：研究生课程 | 开课单位：计算机科学与技术系 |
| 课程层次：硕士 | 学分：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选举、生成树构造、广播和敛播、广度/深度优先搜索、最短路径、最大独立集等分布式算法；介绍异步共享存储器和网络算法、重点介绍互斥和资源分配问题，介绍哲学家用餐算法、着色算法、有向无环图算法以及哲学家饮水算法等。
- 课程难度：中等
- 作业多少：中等
- 给分好坏：超好
- 收获大小：一般
- 难度：中等
- 作业：中等
- 给分：超好
- 收获：一般
6分给汪老师。
徐老师…提前三四周结束课程，仅用四个课时就能讲完随机算法是什么含金量我就不多说了，感谢老师给我一个自学的机会，不然还真以为自己学会了。明天考试，家人们寄了。如果到时候出分不错，这条就当我没说。
二编（1月12日）：
感谢徐老师，感谢助教，昨天的我还是一具尸体，今天的我是一个阳光开朗的好青年。给分不知道，但是卷子真的太给力了！！留着上面评论是为了告诉大家今天的我到底有多感动。
三编：
看到有同学给的回忆版没找到某一题，这是我整理的徐老师用的教材的随机算法中文课后题以及英文答案，包括那题考试大题原题，来造福一下后人。随机算法课后答案.pdf
再次感谢老师和助教
四编（2月21日）
出分了，90+，非常非常满意的分数🥹
- 课程难度：中等
- 作业多少：很少
- 给分好坏：超好
- 收获大小：一般
- 难度：中等
- 作业：很少
- 给分：超好
- 收获：一般
今年课程换老师了, 所以上课内容很乱.
往年是黄刘生老师讲的概率算法和近似算法, 今年是彭攀和徐小华老师讲, 不过分布式算法这部分还是汪炀老师讲, 但是内容十年没变 ...
学校官方有往年的网课视频: http://wlkt.ustc.edu.cn/video/detail_2101_20993.htm
汪炀老师上课很有激情, 虽然他讲的很抽象, 但是如果把课件上东西理解了, 实际上也就那回事, 不是特别复杂, 只不过因为老师总是在讲某个定理之前定义一堆其它乍看不相关东西, 导致上课云里雾里, 很容易变成不知道在讲啥的情况.
徐小华老师的讲课水平一言难尽 ... 上课时讲两句话停顿半天, 10页ppt能讲一个半小时, 放b站视频, ppt上贴照片, 用英文课件上课, 考试前又偷偷把主页上课件换成中文课件 (所以为什么用英文课件上课?)
徐老师一般按照这个流程: 翻开新一页ppt, 看一会ppt内容, 给我们描述ppt内容, 问我们对这个ppt上有什么想法, 沉默5分钟, 每次课都让同一个同学起来回答问题, 然后进入下一页ppt, 循环.
我上课去了几次, 但是感觉太坐牢了, 所以后来就不去了, 干脆自己往年网课视频还有课件, 但是因为徐小华的ppt太简洁, 而且内容太少, 所以又找来彭攀老师的近似算法课件看, 但是因为有些内容看不懂, 所以又去找了其它的英文参考内容来看. 后来发现概率算法这部分和往年网课内容完全不一样, 所以又找来彭攀老师的课件看, 临考前又过了一遍徐小华老师的课件.
总之, 分布式算法是按汪炀老师讲的学的, 近似算法把黄刘生老师讲的过了一遍, 把彭攀老师的(除了SDP)的过了一遍, 把徐小华老师的过了一遍, 又自己看了英文教材. 概率算法把彭攀老师和徐小华老师的都过了一遍. 现在想想好像给自己添了不少任务量 ...
这里附上我认为很有用的参考内容:
1. Havard大学的Introduction to Theoretical Computer Science教材. 我总感觉我们老师就是参考这个做的课件 ... 如果让我从头来一遍的话, 我宁愿自己完整的看一遍这个教材, 也不愿意上我们的课, 知识体系零散, 缺乏前置知识和应用背景说明 ... 但是没办法, 如果我只看这个教材, 很可能错过课程部分内容, 导致考试考砸, 所以当时我只是看了第三部分 "Efficient Algorithms" (主要讲的近似算法). [垃圾制度限制了学生的学习能力啊]
2. 南京大学的https://tcs.nju.edu.cn/wiki/index.php?title=Main_Page上的相关课程. 从这里你能找到不少和我们课程相关的内容, 如果我们老师讲课太抽象, 可以把这个当网课看. 但是这部分我没有看很多, 所以不清楚参考性有多大.
尽管上课上的云里雾里, 但是最后考试并不难, 因为彭攀班和徐小华班的考核是统一的, 所以试卷内容必须取交集, 但是因为徐小华讲的东西贼少, 所以取完交集基本没剩下多少东西了, 这就导致考试的近似算法和随机算法部分内容非常少, 整体的考试难度相当低. (但是这不妨碍我给这课程低分!)
至于徐小华为什么讲成这样, 我不知道是有意为之, 为了减轻我们考试的负担, 或者说他在忙什么其它事, 所以没认真准备上课, 还是说他真的就只能做到这个程度. 不论如何, 不建议去听他的课, 要么去自学, 要么去隔壁彭攀老师那里听. 当然, 以后说不定徐老师会有改进, 但到时候就由后辈们自行决定了.
- 课程难度：困难
- 作业多少：很多
- 给分好坏：超好
- 收获大小：一般
- 难度：困难
- 作业：很多
- 给分：超好
- 收获：一般
汪炀老师给10分，汪老师和徐小华老师平均一下给5分= =
今年是两位老师主讲，前半段汪炀老师讲分布式，后半段徐小华老师讲随机算法等。汪老师讲课还是比较条理清晰和有激情的，量大管饱，虽然和自己的研究方向差得蛮多但还是觉得十分有收获；徐小华老师呃呃呃我称之为发呆式上课，后期没怎么去了。不过考试出卷确实是非常友好，考试内容为两个中文版交叉内容，而徐老师这边几乎没怎么讲= =抱着期待选的这门课，后期还是比较失望的，2022最后悔选课没有之一。
-=更新=-
考前我对这门课怨气巨大，但出题确实非常友好。话虽如此，改变不了后半段课程内容贫瘠的事实，给个7分。
- 课程难度：中等
- 作业多少：中等
- 给分好坏：超好
- 收获大小：一般
- 难度：中等
- 作业：中等
- 给分：超好
- 收获：一般
可能我是个摆子，由于不是这个方向的，所以我评价老师是按照讲课好考试好＞讲课差考试好＞讲课好考试差＞讲课差考试差这套标准，汪炀老师其实属于讲课不差不好，因为的确比较晦涩难懂，某些地方看了好久也看不明白，但是考试很好，出的都是往年题，基本上往年题过一遍就都可以答出来，徐小华老师就是属于讲课比较差但是考试比较好的，和彭攀老师相比，徐小华老师这边就比较简略，好处是最后考试也比较简单，大题基本上都是徐小华老师的题，简答大题是设计最小顶点覆盖，然后算法设计大题第一个是概率期望，第二个是第一次习题课ppt的最后一题原题，“给定正整数集合 A = {a1 ,a2 ,a3 ,…,an } 和正整数 b，b ≥ max {a1 ,a2 ,a3 ,…,an }。当集合 A 的子集 S∈A 中的 元素之和小于等于 b 时，即 ∑ai∈S[i] ai≤b，我们称 S 为可行集。请寻找元素之和最大的可行集 S 。例如，A = {8,2,4}，b= 11，则最优的可行集为 S = {8,2}，最优解为 8＋2=10。(1)下面是求解这个问题的算法。集合 S 初始为空集；按照下标 i 从小到大的顺序依次考察集合 A 中的每个整数 ai，如果 ai + ∑ak∈S ak＜b ，则将 ai 添加集合 S 中，即 S = S U {ai }。证明这个 算法不是1/2倍近似算法 (2)为该问题设计O(nlogn)时间复杂度的近似算法，并证明该算法 是1/2倍近似算法” 原封不动出来，所以说对于比较功利的我来说还是比较满意的，毕竟考试之前总怕出彭攀老师的那些题什么SDP啥的。最后评价8分不过分，大部分人应该和我一样吧，只是想要考试容易的。(PS,而且徐小华老师说会帮大家调分），所以我觉得8分蛮好，2分扣在的确讲课水平不是很高。
