关于选课的注意事项

1. 请不要被本课程的名字所迷惑。很多同学在本科阶段所学习的算法课也叫“算法设计与分析”（包括科大其他院系开设的同名的研究生算法课），但计算机学院开设的这门“算法设计与分析”讲授的并不是算法基础。这门课默认大家在本科阶段已经学习过数据结构与算法基础（如《算法导论》），讲授的内容实际上相当于“高级/高等算法” (Advanced Algorithms)。如果想学习算法基础的同学请选修其他院系开设的算法课（如CONT6411P、EIEN6004P）。

2. 本课堂的授课内容、大纲、考核方式与平行班略有不同，具体请仔细阅读下面的内容。

3. 本课堂是全英文课堂。Everything (class meeting, slides, homework, exams, etc.) will be in English.

4. 请理性看待本页面的“好评”，谨慎入坑。评课社区中大多数同学对于课程的评价与自己得到的成绩呈正相关，所以请理性看待以往的课程评价。本课堂一定程度上还起到了对理论组的同学做科研打基础的作用，所以授课内容的广度和深度会高于平行班。本课堂会努力给大家提供一个好的学习体验，也不会在给分上为难大家，但前提是付出了肉眼可见的努力（对于想划水摸鱼/混学分/不愿意在课后花时间的同学很不友好，比如作业会查重）。

我是2022年秋季学期课程助教，刚刚完成了这学期的全部助教工作。以下点评既是对这学期助教工作的总结，同时也希望能对后续选课的同学有所帮助。本页面上方的“简介”中已经对本课程的基本信息作了介绍。需要指出的是，由于彭老师班本学期是第一次开课，“简介”中“(Tentative) Topics”部分是参照平行班往年的课程内容给出的，与实际授课内容略有差异，具体请参考下方“课程内容”部分。

课程基本情况

1. 课程定位：本课程是计算机学院研究生的必修课、基础课，同时也是若干相关学科（如网安、大数据、电子信息等）研究生基础课。

2. 课程目的：随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。本课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。

3. 先修课程：离散数学、线性代数、概率论、数据结构与算法基础

4. 考核方式（2022秋）：出勤率（5%）+作业（30%）+闭卷期中考试（30%）+闭卷期末考试（35%）

课程内容                                        

本课程包括随机算法 (Randomized Algorithms)、近似算法 (Approximation Algorithms) 和分布式算法 (Distributed Algorithms) 三部分。本学期的授课内容如下（我认为从广度和深度上都要优于平行班）：

Randomized Algorithms

• Review of Some Basic Probability Theory
• Concentration Bounds: Markov, Chebyshev, Chernoff
• Types of Randomized Algorithms: Las Vegas, Monte Carlo
• Techniques: Balls into Bins, Hashing, Fingerprint, Boosting the Success Probability, …
• Algorithms for Min Cut, Estimating the Average, Finding the \(k\)-th Element, Distinct Elements in Streaming, Verifying Equality of Strings, …

Approximation Algorithms

• Basic Definitions of Approximation Algorithms and Hardness of Approximation; Classes P, NP, Reductions
• Greedy: Knapsack, Vertex Cover, Set Cover, \(k\)-center, Metric TSP, Correlation Clustering (minimization)
• Rounding Data and Dynamic Programming: Knapsack
• LP + Rounding: Weighted Vertex Cover
• Random Sampling: Max 2-SAT
• Local Search: Max Cut, \(k\)-median, \(k\)-means
• LP + Primal Dual: Uncapacitated Facility Location (UFL)
• SDP + Rounding: Max Cut, Correlation Clustering (maximization)
• LP + Metric Embedding: Sparsest Cut

Distributed Algorithms

• Synchronous Network Model: Leader Election in a Ring Network (LCR, HS, etc.), Maximal Independent Set (Luby's Algorithm), Breadth-First Search, Shortest Path Trees, Coloring Trees and General Graphs
• Asynchronous Network Model: Leader Election in a Ring Network, Breadth-First Search, Shortest Path Trees

作业

这学期共有6次作业（每个部分各2次），每次作业2-3道题。其中，3次作业难度中等偏下，3次作业难度较大。作业要求使用英文完成（事实上用中文也没影响成绩），推荐（但不强制）使用LaTeX排版。作业的主要目的一方面是巩固上课所学内容，另一方面是起到一个拓展的作用（可能需要大家检索相关资料）。虽然作业的总体难度较大，但助教在给分的时候是非常宽松的。

学术诚信：对于所有从事学术活动的学生和学者而言，学术诚信不应是底线，而应是“自发的要求”。有些行为可能使你得到分数，但失去应有的训练。本课程将不遗余力地维护学术诚信规范，违反这一底线的行为将不会被容忍。我们鼓励大家在完成作业的过程中与同学讨论或上网搜集资料，但作业文本的写作必须独立完成，且需要在提交的作业中致谢所有参与讨论的人、引用相关参考资料。如果发现雷同的作业，抄袭者和被抄袭者当次作业的成绩都将被取消，因此请主动防止自己的作业被他人抄袭，不要把自己的作业发给其他同学。在本学期中，累计有8人次被查到违反学术诚信。

考试

与平行班不同，本班有期中考试和期末考试。期中考前半部分，期末考后半部分，使用中文或英文作答都可以。两次考试的难度都远远小于作业和上课内容，题型包括判断、填空、选择和若干大题（算法设计/分析），内容大部分来自于PPT和作业（当然，不是原模原样，但只要理解了肯定能做出来）。在两次考试之前都会安排一次习题课（由于上学期期末提前安排了离校，且春季学期返校后没几天就考试了，所以没有安排期末习题课，在此表示抱歉）。

参考资料

在本页面上方“简介”中“References”部分已经列出了本课程的7本主要参考教材，并且附上了电子书的链接。本课程的内容大多来自这些参考教材，大家在学习的过程中可以参考阅读（PPT中也会列出来自某本书的某章节）。

除此之外，大家也可以参考国内外高校开设的类似课程（视频、课件、讲义）：

• Advanced Algorithms by Yitong Yin at Nanjing University（特别推荐，对应本课程随机算法和近似算法部分，课程主页有中文授课视频）
• Advanced Algorithms by Ankur Moitra at MIT
• Advanced Algorithms by David Karger and Aleksander Mądry at MIT
• Advanced Algorithms by Jelani Nelson at Harvard
• Advanced Algorithm Design by Sanjeev Arora at Princeton
• The Modern Algorithmic Toolbox by Tim Roughgarden and Gregory Valiant at Stanford
• Linear and Semidefinite Programming (Advanced Algorithms) by Anupam Gupta and Ryan O’Donnell at CMU
• Distributed Algorithms by Mohsen Ghaffari and Nancy Lynch at MIT
• Principles of Distributed Computing by Roger Wattenhofer, Goran Zuzic and Michal Dory at ETH Zurich

后记

这学期是彭老师第一次在科大上这门课（之前应该在国外上过），课程内容与我当年学的还是有较大差异的，所以做助教的过程实际上也是我与同学们共同学习的过程。在学期中间，彭老师多次收集我和同学们的反馈和建议（甚至包括粉笔颜色），并及时在课程中进行调整。非常感谢班上的91位同学（还有学期中间陆续退课的几位同学）对本课程提出的许多宝贵意见和建议，我们在之后的学期中会不断改进。

在计算机学院的几年间，令我感到欣慰的是，课程质量肉眼可见地在提高，新开了很多优质的课程，引进了许多优秀的老师开课，填补了以前培养方案中许多方向的空白，例如：

理论/算法方向：大数据算法、高级算法设计与分析、形式化方法导引、形式语言与计算复杂性、最优化导论/优化理论

系统方向：计算机系统、存储与文件系统、数据中心网络与系统

但很多事情都是相对的，往往优质的课程并不“水”，需要同学们投入较多时间，特别是对于研究生同学来说，很多同学并不愿意这样，这也完全可以理解。大家之所以觉得一门课难/硬，或许是因为确实缺乏相关的训练，而这正是这些课程试图想弥补大家的。从另一方面来讲，对于学院/学科而言，能开出更多的优质课程实际上也说明了学院/学科在进步，这可能将来也会反过来作用在大家身上（提升大家今后作为毕业生的口碑）。

常见问题

最后这一部分来回答一些常见的问题并分享一些自己的看法，仅代表个人观点。

[Q] 为什么这门课是必修课/基础课？我是做AI/ML/DM/…的，学这么多高等的算法理论对我有啥用？这门课对找工作有帮助吗？

[A] 关于课程设置的问题，或许应该由学院的相关老师来回答，但至少我认为科大计算机相关专业的同学应该具备一些计算机专业人基本的“素养”和“内功”，应该了解一些计算机科学中美好的事物。我承认，从功利层面讲，这门课并不能给大家带来什么直接的好处（例如，找工作），这门课的出发点也根本不在于此。相信大家学完这门课、考完试之后很多东西都会忘掉，但只要这门课当中的一点点东西（或是工具，或是思想）给大家在日后遇到其他问题时带来一点点启发，这门课的目的也就达到了。（个人认为，大部分研究生课程的主要目的都是拓展视野）

这里引用数学学院梁永祺老师主页上的一段话（请注意：仅是引用，并不完全代表个人观点，请有选择性地看待）：

如果你讨厌一门课，那你可以不修。如果它又是必修而你又觉得课程设置不合理，你可以提出你的建设性的建议。但是，请你先考一个像样的分数，至少得及格，否则你的意见不会有人重视的。我记得我出国第一年参加的一个代数和数论的项目，但是必修一门辛几何的课程，我很不喜欢很不乐意且意见很大。但我最后考试拿了满分，而我也不知道最后我的意见有否被采纳。你要想提出能得到重视的建议首先要排除掉“你太弱了不想修那门课才提意见来避免修课”的因素，因为或许这门课程的设置就是为了锻炼你数学的某方面的能力而这方面正是你所欠缺的而又是必须的。

[Q] 这门课好过吗？可以不带脑子可可爱爱拿个75吗？

[A] 如前文所述，这门课并不是一门水课，对大家的数学基础和算法基础也有一定要求。但只要付出了肉眼可见的努力，想挂科（指低于75分）也是非常难的（对于任意一门课程都是如此，特别是研究生课程）。全程躺着肯定是过不了的。

[Q] 听说这门课是英文授课，我英语不好，上课能听懂吗？

[A] 首先需要说明的是，本班之所以是英文授课，是学院考虑到留学生的需求，专门开设的一个英文班（大家也会发现最近几年学院开设了越来越多的英文/双语课程），并不是彭老师的主观意愿，事实上彭老师也多次向我表示担心英文授课的效果。在学期过程中通过我与同学们的交流发现，确实有很多同学表示难以接受英文授课（例如有同学表示每节课是在坐牢）。彭老师在学期中充分考虑了同学们的反馈，从学期初的全英文授课，逐渐转变为英文为主中文为辅，到后期逐渐加大中文比例，最后几节课基本上就是全中文授课。在期中期末考试中，由于试卷也是英文的，考场上有多位同学让我翻译单词、解释题意，在批改试卷的过程中也发现部分同学完全没能理解题意。综上，如果对自己的英语（主要是听力和阅读）没有信心的同学，建议去隔壁中文班。（当然，也希望大家可以多花一些时间学习英语，事实上本课程用到的英文词汇也都很基础，更不涉及到长难句）

[Q] 我本科没有学习过《算法导论》，学习这门课会吃力吗？

[A] 事实上，只要学习过概率论、数据结构，就能上这门课。但是，如果本科期间系统地学习过算法基础（如《算法导论》），特别是接触过算法的（复杂性与正确性）证明，会使本课程的体验更佳。

老师是非常好的，特别体贴，不点名，5%平时分直接送给大家，也全程直播可以在bb上在线听。

但是课程内容嘛，体验下来不是特别好，（不用担心分数了，尽力学就行）老师是有认真准备的，但是内容很难，和中文班的不一样之处在于英文班更加强调数学上的证明，涉及到的数学知识非常广泛，比如SDP等等，压力非常大。（压力大？那都是我庸人自扰了）

这学期总共做过6次作业，每次作业3道题，作业的难度非常大，3题想三五天都不一定想的出来。彭老师认为作业是为了开阔大家的知识面，为了给大家进行一个拔高，需要大家检索大量参考资料来完成，如果轻易就能完成了说明没有跳出舒适区，这样也学不到什么知识。我个人赞同彭老师的观点，但是考虑到平时作业会影响到成绩，这么做是否真的妥当有待商榷。（让我担惊受怕一个学期哈哈哈）如果实验室任务繁忙，那这一门课就足以折腾得人痛不欲生。

考试难度不低，有期中期末2次考试，占比分别为30%和35%，虽然比作业要简单一点，但是依然让人压力满满。

看到金老师的数据库系统有人评价为难，我个人的体会是这门课的难度要远超数据库系统，所耗费的精力至少是数据库系统的五到十倍。（但是这可是TCS！多花点精力也很正常嘛！）

个人认为这门课算是计院为数不多有含金量的好课了，看得出来老师真的很用心，光参考资料就推荐了6-7本，在课件中也标注了参考书目的章节。要是没有分数的压力，（确实没有分数的压力哈哈哈）我肯定给这门课打满分。但为了自己宝贵的头发和时间考虑，建议大家慎重选择。（不存在的，冲就完事了）

--------------------------------

出分后更新：妈呀老师真的超好，全班只有一个人没有75分，均分87分，中位数88分。给分给这么大方，难一点算什么！彭老师我吹爆！！！

再补充下，彭老师人在教学上真的非常nice

考试周结尾更新，做个小节，这时候回头看，才有一种“把点连起来”的体会。

老师最后会调一调分，难度也会有所调整，只要别太离谱应该还是能75飘过的。

这门课直到老师讲到近似算法中间一章的时候，这门课才对我稍微友好点，现在回过头来反思，其实就是少了一步“把点连起来”。这门课少不了大量的实例，一旦能跟着老师形成算法思维，收获将非常多。

彭老师是新开的这门课，一开始老师说有英语和数学门槛（主要还是数学）的时候，那时候没有对难度有个较为具体的认知，没太当回事结果就继续跟下去了，所以还是要提醒后来选的同学，门槛，那是真的有门槛，而且需要付出比较多的精力，但收获也正相关。

前半部分学概率算法的时候，一直陷入到case study的问题，那种学不明白+知识串不成网络的感觉真的血崩，但是在后面近似算法经过将近似算法和NP问题联系起来后，才稍稍有了些明白的体会，这时候才感觉稍稍有点收获了。

然而概率算法至今仍然一头雾水，这里面数学真的是我不配了orz，也一直没法形成系统的认识。

即使一开始吐槽这门课好难，有一点我是相信的，国内计算机教育想要走到下一阶段质变，对这种类型的课就更加需要，但黄金时期是在本科安排上（没再多打分还是因为和同类研究生课程相比所需要付出太多精力）。这种类型的课越多，国内计算机教育内卷可能也就能少一点，创造可以变得多一点。

从课程方方面面，大家都是能感受到彭老师和他的助教们对这门课用心程度，哪怕像我这样一个功利主义者都会承认，这门课仅仅学个大概都会有收获颇丰之感。

在此感谢下彭老师和师兄们为这门课付出的真心。

也许之后选这门课的同学们依然会抱怨很难，甚至更难orz。不过还是回到那句话，当你有一天回看将他们连在一起的，才会发现这门课的价值。

先说好的：

1. 老师备课什么还是很认真的，而且课程内容也非常硬核；

2. 知识的讲解会看录像也还是能搞懂的，老师上课讲的也算清楚；

再说个人不太能接受的，注意仅陈述个人感受：

1. 结合老师的出身，这门课数理方面的要求还是比较高的，喜欢挑战这些难题的同学可能都不是问题；

2. 老师是第一年开课，所以对于课程难度的把握，个人体会真的不太好，而且分数也卡的比较严；

3. 想水过的，把精力投入到其他事情上的慎重吧，这点每个人都有自己的观点。但仅分享下个人对此意见：对于工科生来说，这门课算法理论学的多扎实，从功利角度上来说，在你的简历、面试上体现不出分毫，说不好听的理论造火箭好不好，但市场决定了你面试做不出来题还是白瞎。有些课同样是有难度，但最起码那门课做出来的一些东西你是能反映到简历上作为加分项的。

给其他后来人留个参考，再次强调，仅分享个人意见做参考。

在上课的时候比较痛苦, 容易在一个个算法问题中溺水想不明白, 但一边复习一边发现整个课程的脉络还是十分清晰的, 从随机算法到近似算法再到分布式算法. 虽然上课教过的问题和具体算法流程大概率考试以后不会记得, 但是对随机算法是个什么东西, 近似算法尝试解决什么问题, 分布式算法是在什么情况下的考量至少有了概念, 个人认为这些认识对计算机相关的学生来说很有必要, 收获还是挺大的.

很多数学证明非常恐怖, 不过仅限于授课阶段, 老师出卷和给分都很友好, 基本涉及到的都是算法流程和一些简单的证明.

第一次写点评，冲着老师海底捞月还有助教的认真工作高低得来唠两句

·英文授课确实带来一定的困难，但老师和助教也在积极的改进。这课是目前CS的专硕必修，不管哪个老师的课，核心的算法内容这些的难度都低不了。如果英文不是太糟其实都可以试试，毕竟后面科研啥的英文这一关终归是逃不过的

·作业设置非常好，虽然有一定的难度和工作量，但是受益良多。内容上很多都是课堂内容的延申，鼓励进一步思考理解以及扩展阅读；形式上对于latex这一科研重要工具的学习使用大有脾益

·分数不用担心，这学期全班只有一个缺考的同学没有拿到75。认真做作业然后尽力考试都能拿到够用的分数

·助教非常认真负责，很耐心的讨论和解答问题。有一说一我是第一次见到老师不给答案助教也要自己写作业的课