※ 本文是否可提供台大同学转作其他非营利用途？（须保留原作者 ID） （是／否／其他条件）：是 (虽然同意转发，但目的是希望有选到这门课的同学不要走错棚，请不要对文章内与上述 目的无关的文字妄自评论。) 哪一学年度修课：111-2 ψ 授课教师 (若为多人合授请写开课教师，以方便收录) 陈和麟 λ 开课系所与授课对象 (是否为必修或通识课 / 内容是否与某些背景相关) 电机工程学研究所 δ 课程大概内容 Week 1 - Course Overview, Knapsack Problem, PTAS/FPTAS Week 2 - Approximation Algorithms: Subset Sum and Bin Packing Week 3 - Linear Programming, ILP, LP Relaxation, Vertex Cover, Set Cover Week 4 - Integrality Gap, Facility Location Problem, LP Duality Week 5 - Primal-Dual Algorithms (Set Cover, Facility Location) Week 6 - Greedy and Local Search Algorithms (Facility Location, k-Median) Week 7 - 2-Approximation Greedy MFLP Algorithm, HW Solutions, Midterm Hints Week 8 - Midterm Week 9 - Midterm solutions, Randomized Algorithms, Derandomization Week 10 - Randomized Rounding, Review of Hashing Week 11 - Hashing Week 12 - Markov Chain, Random Walk Week 13 - Counting and Sampling Week 14 - Counting, Online Algorithms Week 15 - Streaming Algorithms, HW3-4 solutions, Recap Week 16 - Final Exam 上述进度表是参考去年课程网上表定进度，再根据实际的上课进度微调而成。主要差别 在於 Week 7 原定要讲的 Solving Linear Programs (Simplex Method, Ellipsoid Method) 可能会因为时间不够而略过，跟期末考的 Online Algorithms 和 Streaming Algorithms 讲比较少，所以不纳入期末考范围。个人认为 Simplex Method 蛮容易自学 ，但 Ellipsoid Method 就复杂蛮多，如果把学期末的 Online Algorithms 和 Streaming Algorithms 直接改为 Simplex Method 和 Ellipsoid Method 也许是个不错 的主意？ 期中考范围是为 Approximation Algorithms，期末考范围是为 Randomized Algorithms 两大主题几乎独立，但有的时候我们也会透过把 Randomized Algorithms 按照每一步的 期望值高低作为选择转为一个 deterministic algorithm 去得到一个问题的 approxima- tion guarantee。 我自己主观感受掌握课程内容的难易 (痛苦) 程度「前半学期：後半学期＝３.５：１」 先苦 (真的很苦) 後甘，理论上期末考卷面 (调分前) 分数应该要比期中考高出一些 ( 或很多，期末考有人满分)，我自己则是例外。 η 上课用书(影印讲义或是指定教科书) 老师有说课程内容主要是按照课程网上提供的三本教科书综合编排， 1. Approximation Algorithms, Vazirani 2. Design of Approximation Algorithms, Williamson and Shmoys 3. Randomized Algorithms, Motwani and Raghavan 这三本都能在网路上找得到「友善数位版」。 上课有遇到不懂的地方，除了询问老师助教跟同学之外，也可以直接去翻课文，作业题目 有一部份也会从课本出 (但不保证找得到解答)，前半学期主要依赖第 1 本，後半学期主 要依赖第 3 本，第 2 本印象中不怎麽用到，只有期中考的某一题勉强算有点相关而已。 然後我笔电的资料夹内，不知为何还多出了一本 Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal，忘记是老师上课时额外推荐，还是我自己找到的，好像是为了复习机率相关 的定理 (Chernoff bounds) 才特别找到的一本书。 μ 上课方式(投影片、团体讨论、老师教学风格) 三节课的板书上好上满，为了讲解的流畅度，中堂下课时间不一定是学校表定的钟响时间 ，极少数时候中间只有一堂大下课，有些时候最後一节会超过 10 到 15 分钟左右 (也就 是大约 12:20) 才下课。每周上课除了期中期末考之外都有同步录影，上完课的当天晚上 就会上传到 NTU COOL，不得不说助教的效率真的非常令人满意！某一周的第一节大约 有半小时因故没有录到，老师还特地找时间重新录制这部分的内容，不得不说老师真的是 把「宽以待人，严以律己」的精神实践地非常彻底，如果是我的话可能会直接改传手写笔 记上去吧。 老师的授课风格很简单，就是每周都按照预先准备好的几张 A4 手写笔记，先在黑板上写 好超大字的板书，再依序以麦克风有条理地讲解，讲解过程中偶尔会有一两次大停顿点， 问大家有没有问题，鼓励大家举手发言与讨论。 每次小节下课如果有比较多同学问到相同的问题，老师下一节上课就会把该问题再重新讲 解一遍。当周最後一节下课之後可以到讲台前问问题问到饱，所以要选这门课的话建议把 中午的时段也空下来。因为每次都有很多人想问问题问到饱，如果赶时间的话可能要尽量 坐前面一点才有机会抢先，不然要等很久。当周结束之後老师则会根据当周的状况再次调 整下周上课的进度。 如果还想要更深入了解「授课风格」的话，蛮强烈推荐大家先去看老师之前的采访 (有两 篇，第一篇比较以前的主要是在讲带研究生方面，第二篇比较最近的才是讲授课方面)， 1. https://www.dlc.ntu.edu.tw/wp-content/uploads/1019%E9%99%B3%E5%92%8C%E9%BA% 9F%E8%80%81%E5%B8%AB.pdf 2. https://issuu.com/muladna/docs/_16-issuu (第 198-207 页) 在第一篇采访里面：「我企图展现的是，你在这领域要待一辈子时，真实会遇到的状况是 什麽。我希望的是学生能像我一样，对这领域有兴趣、预先知道在这领域做研究是什麽情 况！」这门课的评量方式有一样的效果，让我知道自己并不适合从事理论研究。 在第二篇采访里面：「善用板书、频繁互动。写板书是老师推动思考的过程」、「老师上 课几乎没有任何 『痾』、『嗯』之类的语助词。所有停顿都像是精心设计，每一句话都 像是排练过！」。 还有一个采访没提到、但我上完课有深刻体会到的，就是善用精确而生动的中文词汇描述 隐藏在问题中的道理与背後解决问题的思想，举例来说： 1. 为什麽一个问题的 string encoding 要采用二进位 (binary string) 而非一进位 (unary string)？因为二进位的表示法比一进位在长度上更「经济」。 2. Bin Packing 演算法的 approximation guarantee 在上课只有比较粗浅的分析，如果 还要得到更好的 ratio，就要再对原演算法更「细致」的讨论，老师说网路上有其他参考 资料但是就课程范围来说没必要去 cover 它。 3. 作业的某一题要求想出一个 f(k)-approximation, f(k) < c 的演算法，但上课教的 演算法是在某个环节比较没有限制的话，就能达到 c-approximation guarantee，所以在 那个环节上就有一个「操作的空间」。 4. 还有一个我有点记不太清楚的是，在讲 LRU (least recently used) 一节好像有出现 某个 slot「被针对」的字眼，细节留待好心人补充。 上述几个授课风格的最终目的都只有一个，就是为了要能在每周三个小时的课程当中把复 杂的演算法清楚地呈现给大家。 ρ 考题型式、作业方式 ＊作业： 这学期有四次作业，每次都是五题，都是演算法的设计题以及证明题，有些题目课本中有 出现，有些可以从 2000 年以前的经典论文中找到解答，有些答案则是网路上不管怎麽找 都找不到。如果有援引参考资料或者是从其他人的协助求得答案，都要在每一题的题号旁 标上 collaborator，否则该题不计分，即使独立完成也要标上 no collaborator, 否则 不计分。不接受迟交，因为上课时间会讲解答案。整学期都是缴交日的第一堂下课前在 NTU COOL 上缴交电子档。有点忘记是不是打字书写都行。 难度就跟传说中的一样，题目叙述跟上课教过的有八成七像，但自己无论怎麽想破头就是 想不出来，此时这门课最有趣的地方就是老师希望大家 office hours 都可以去找助教要 hints，但是如果你生性害羞内向 (如我) 想 DIY，却 DIY 不出来的话，那把所有出现过 的思考脉络全部记载上去，也能获得该题一半以上的分数。给分可说是非常大方。 有一次跟助教吃饭的时候 (非开课期间)，助教说因为批改大量的作业实在是很耗费心神, 所以我经常在书写作业的过程中有意无意地点缀一些自己的研究领域让他看得非常开心。 ＊考试： 这学期有一次期中考跟一次期末考，可以带一张 A4 双面大抄入场考试，大抄内容、制作 方式不限，不会延长考试时间，考试期间可以自由进出教室，不会有人监考，个人觉得这 样比较自由、作答的时候比较不会有压力。 这学期的考试每次都是五题，难度固定都是三题从作业小幅度修改而来的超基本题，加上 两题新的你完全料想不到的超创意题 (刚好都跟图论有关)。之所以要强调是超基本题， 是因为考前一次上课老师会解答作业跟提示考试内容，如果你很幸运地往作业原题的方向 去思考，就会很容易想出来，如果不往原题的方向思考，随着时间一分一秒过去，心态会 愈来愈慌。那超创意题要嘛本来就想不出来，要嘛是拿课程中很 widely used 的 proto- type 下去改，不需要去理解那些很 large-scale 的演算法。简言之，超基本题和超创意 题两类区分的很开，考试的时候如果能先一眼看出便事半功倍。强烈建议把老师提示的出 题范围也记在大抄上，因为考试的当下你可能会很慌，看到题目叙述却无法联想到对应的 范围而想不出解答。也把你觉得可能被修改而来的作业过程写在大抄上，这样在改的时候 就不用自己重新再想一遍，会快很多。改得动的演算法 (上课＋作业) 最好 200% 弄懂， 不然像我以为自己懂了结果改不动而丢了 7 分 (理论上应该要扣更多)。改不动的通常可 以不要看 (你全部忘光也没有关系)，因为考题的证明手法通常不会跟上课某个特定或 large-scale 演算法的证明手法一样或相关。也不需要预先把其他论文印下来，当下你不 会有时间看的。如果要额外准备的话建议 survey 跟图论有关的 small-scale algo。 考试的给分标准和作业有很大不同，听说是只按正确性给分，但即便如此我还是觉得作答 的时候要尽量写比较好，我自己则没有做到这个部分，不习惯瞎掰错误的东西在考卷上。 有时候一个大题会附很多小题，如果前一个小题不会，後面的小题仍然能先把前面的小题 当成已知结果继续作答，我常忘记这件事而丢了不少分数。 虽然老师会附考古题，但帮助不大。 ＊期中检讨： 期中考後到下周上课老师讲解答案之前，可以补交考卷的检讨当成一次作业 (following the homework policy)，如果这次作业写得还不错，那期末结算总成绩时如果是在及格线 下 5 分以内，会改以最低及格等第通过本课程，否则这份补交不影响学期成绩。我自己 是有交检讨，在里面顺便把一些上课可能有遗漏掉的证明补齐，结果下周上课老师讲解答 案的时候，听着听着便觉得「欸乾怎麽都跟我的补交一模一样ＸＤ」，这是我在这门课最 有成就感的时候。在检讨那题有 30 分配分的 MFLP 的时候，我一直躺在床上 emo 心里 想着自己没有能力作理论研究，後来边参考第 2 本书，硬是把解法兜出来之後，上课去 问老师，老师才说那题是某篇论文里面的 algorithm 拆成的小题再改编而成，而且我还 厘清了那题只需要考虑 x=1 的小细节。反而是期末考 consistent hashing 那题我迟迟 都想不到解法，网路上也找不太到。 老师还有一个坚持，那就是这门课的修课同学不能流传任何作业考试部分或完整的书写 过程给其他人，必须用口语的方式进行讨论，因为讨论才能刺激思考。 σ 评分方式(给分甜吗？是紮实分？) 紮实，甜？ 作业 40%＋期中考 30%＋期末考 30% (是说 112-2 学期公告的好像不太一样，我猜是因为期中考范围比较难所以比重调高) (如果改成：作业 4x15%＋期中考 20%＋期末考 20% 然後不调分，似乎也是一种可能) 有四次作业，总分是 100+100+80+100=380，除以 3.8 当作作业成绩，简单来说不同次作 业每一分的权重是相同的，这个部分原则上不调分。 期中考全班原始平均 51.4，标准差 16，调分方式：原始分数 * 0.8 + 32 期末考全班原始平均 55.8，标准差 20，调分方式：原始分数 * 0.7 + 35 调分机制不明，有兴趣的同学应该可以直接问老师？ 最後就是直接按原始公告比例换成等第成绩，公告信上写说换算的时候还会再微调，但我 自己是没被调到。 就我印象中的个人成绩来说 (COOL 网页关掉了没办法查成绩QQ)，前三次作业都有一题写 不出来、最後一次满分，期中、期末都只有基本题分数 (原始 60 分上下)，这样的学期 成绩会是 A- (82)，但其实期中、期末各有一题进阶题如果思路对的话应该要想得出来， 只有一题想出会升级为 A，再一题想出则会有 A+. 由此可见，认真读书但脑袋不太灵光 的同学如我可以保底 A-，但要再升级的话很吃考试的状态、运气跟智商。 (这边智商的定义乃能利用尽量少的资讯与时间与足够有效率的思考路径得到想要的结论) 下面放一张从可爱巧虎岛撷取出来的梗图给大家笑一笑，这样的同学只能拿到 A-。 https://imgur.com/ZZkwijC (https://www.youtube.com/watch?v=GbHkKw8dqEk&t=215s ) (https://www.youtube.com/watch?v=qfskq-iaBG8&t=215s ) 另外根据 epo 上面的数据显示： 比您成绩低的比例 43.66% 与您成绩 (A-) 相同的比例 23.94% 比您成绩高的比例 32.39%，这些人属於比较会活用知识的同学，比例并不低，所以给分 甜不甜老实说见仁见智。但可以肯定的是如果探索学分能用在这门课的话一定会有很多人 跑去申请。 ω 其它(是否注重出席率？如果为外系选修，需先有什麽基础较好吗？老师个性？ 加签习惯？严禁迟到等…) 最後是比较多我个人的修课感想，原本去年修完课就要发的，结果忘记被什麽事情拖到， 现在才草草赶出一个版本 (因为要开学了 哈哈)，听说很多学术工作者经常被各种庶务 耽误到许多稿件都拖个五年十年才发出去，有点担心自己以後会不会也变成那样的人。 这门课还有许多细节跟稍微 private 的心路历程写出来就不有趣了，那部分便留待大家 自行体会。 这篇文章最主要的目的是提供给这学期要修这门课的同学，应该要以怎麽样的心态下去 参与，才能有最一度赞的学习效果。 首先会选这门课的同学，想当然尔都是对演算法相当有兴趣，而且看到老师的名字也顺势 自认为对作业考试难度都 hold 得住，但其实这门课之所以被称为「高等」演算法，正是 因为它和系上开设的不论是大学部还是研究所课号的演算法课程有极大的不同，那不同在 哪里呢？ 1. 解决问题的层次不一样。传统演算法课程希望解出的问题大部分都是属於 P class， 也就是存在一个以问题大小为自变数的多项式时间演算法去 (deterministically) 解出 该问题，然而这门课希望解决的问题通常都不属於 P class，都是属於 NP-hard class， 所以才会衍伸出容许误差ε倍的演算法分类像 PTAS、FPTAS、RFPAS 等等，这门课大部分 的时间都在跟它们打交道。 2. 演算法的规模不一样。传统演算法课程顶多像 Dijkstra, Prim 那边就很了不起了， 但这门课前半学期会教到像 primal-dual 这类比较复杂的 framework，一题可能会写到 两面 A4 大小，跟解 KKT condition 一样耗时，这类的题目也不怎麽适合多练习，因为 写完一题可能就没力气做其他事了。 3. 用到的数学工具不一样。传统演算法课程只需要离散数学跟数学归纳法，但是这门课 恰恰相反，跟传统演算法重叠的只有一开始的背包问题出现 dynamic programming (DP) 而已，其他时候反而都是使用到像机率 (Chernoff bounds 上课会复习) 或者是线性规划 还有微积分跟求极限等数学系本科比较熟悉的工具。这门课的「传统演算法」味道会随着 学期的过去而愈来愈淡。 所以当你说自己对演算法有兴趣，是什麽样子的演算法呢？你以为的演算法跟现实世界中 真实存在的演算法真的是一样的吗？你以为对喜欢的人早已了解透彻，但彼人的真实面貌 真的是如你所想的那般吗？ 基於上述几个理由，有些同学可能会发现课程内容不符合自己的预期便纷纷退选。 接下来是上课风格。老师的时间掌控其实非常精准，在我看来每次上课都好像在打仗，是 指战战兢兢的意思，语速虽慢，但证明关键常以精炼词句带过，知识密度 (含金量) 其实 颇高。基础的部分上课带得非常体贴，但困难、延伸、(跳tone?) 的作业便只能独立思考 推敲，完全无法从上课内容获得一些什麽，极大的反差可能也是让一部份人退选的主因。 我自己很喜欢基础的部分很仔细地讲，但有些高层次的定理没在课程中解释出来也很难让 我信服，我後来都是自己想办法解决，举例来说像 c(i,j) = h(i,j) + h(j,i) 的期望值 算法看似直觉，但其实有个小细节是这个 c(i,j) 所考虑到的路径中可能会经过很多次 j 那怎麽能保证用 h(i,j) + h(j,i) 的算法能让一条路径刚好只会被算一次？我後来是用 两个随机变数的总和去解释，以遇到第一个 j 的路径长为切割点。在讲解 large-scale algo 的时候通常是局部局部的带，蛮多同学当下有能力举手提出问题或指出漏洞，但我 没有这个能力，我必须打完逐字稿先知道全貌才好理解吸收，这导致了我期中考那题 30 分的 MFLP 只写了第一小题的 5 分，因为我没意识到那题是从考前一周的内容修改而来, 那周的内容因为有某个不等式的推导过於复杂而略过，我就以为是观光周，一整个就偷懒 疏忽掉了。只要一段资讯有某个环节无法理解，便无法理解整段资讯的全局，是我的致命 伤。而课程末尾的 online, streaming algo 因为不考，我也就没特别花心力读进去了。 这门课由於有课程录影的关系，好像有蛮多人认为自己看影片吸收会比较好，像这位同学 https://webptt.com/cn.aspx?n=bbs/NTUcourse/M.1626858295.A.3C5.html 所说的「我自己就是大 多时候远距上课，主要是因为自己控速度的话好像吸收得更好。」，导致有某几周来的人 特别少，但老师的课是需要透过提问来控制讲课速度、推进课程内容的，课程录影和老师 期待的上课方式似乎背道而驰。 回到前述第 2 点，这门课的演算法规模之大，造成以下两个现象： 1. 有些演算法真的可以当成观光周，因为改不动的演算法都不考也不会是作业题，例如 　 * k-median 的 5-approx. local search algorithm 和 * MFLP 的 3-approx. local search algorithm 这些演算法记不进金鱼脑里面，也无法萃取出设计精神出来，真的就是纯欣赏。这也导致 了考试范围只集中在改得动的演算法，并没有平均分散在各周，如果是像我会特地把论文 翻出来就只为了弄懂这些改不动的演算法，这些 efforts 就无法反映在学期成绩上面， 心理上会备感吃亏。我曾跟已经修不到这门课的同学 (也是老师以前的学生) 小小抱怨过 这件事，那他就反问我说你修课到底是为了要学东西还是要 get good grades？如果是你 会怎麽回答呢？ 2. 有的时候演算法规模大到让人要把问题说清楚给老师听都需要费些许功夫，像我这种 超级大懒人一枚，只要中午因为要赶着搭交通车而问不到老师之後就会自己找课本或论文 解决，但说实在的，这门课最正确的学习方式其实是： (O) 找教授助教同学讨论厘清问题的关键 (X) 自己翻课本论文找到正确的解释方式 理由是透过反例才可以找到问题真正的关键，如果你是自己找 explanation 的话就有点 像是直接请人家帮你修家具或水电的感觉，修好了你还是不知道原本问题出在哪啊～ >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 来一个具体的例子：第四周老师有介绍过一个 2-phase 的 6-approx. MFLP 演算法，这 演算法我自己觉得超级有趣，只是一直对 2nd phase 决定最後要打开哪些 facility 的 程序有些疑虑，我当时并没有真的找到反例，只是有一个比较直观会让老师上课给的版本 fail 的理由，现在我忘记那个理由到底是什麽了，也许那个理由根本就不会发生。 ＊老师上课的版本：先把 clients 按照 1st phase 得到的各自 connection cost cj 由 小到大排序，接着依序检查这些 client，每个 client j 都已对应到一个集合 Nj 代表 正在服务它的 facilities，从 Nj 之中挑一个 opening cost 最小的 i 去正式地打开它 并把范围内的其他 facilities 强迫关闭，同时受影响的 clients 全部也改由 i 服务。 (这个程序之中我忘记会不会有 clients 和 facilities 的状态被修改两次以上，如果有 的话不太确定是要维持不动还是照常修改，也不太确定会不会有某几条不等式被 apply 两次以上的问题。)＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ ＊我自己想的版本：一样是先对 clients 按照 cj 由小到大排序，接着依序检查「当下」 的 client j 是否已经被指定到一个我们认可的 facility 服务，如果是则直接往下一个 client 看，如果不是则强迫此 j 只被 Nj 内任一个我们已经认可的 facility k 服务， 如果 k 不存在，则随意认可 Nj 内的某个 facility 为完整的 yi := 1 并令为 k，然後 强迫关闭 Nj 内所有我们还没认可的 facility (即 yi := 0), 接着一样让所有受到影响 的 clients 也全部都改只给 k 服务。这个作法可以确保每个不等式只会被 apply 恰好 一次。＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ 原本这个分歧点是要在某一周上完课之後找老师讨论的，只是因为人太多後来赶时间就不 了了之了。 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< 剩下的就是一些没办法自成一个段落的小小碎片： 1. NTU COOL 本身有支援讨论区功能，只是因为这门课的防弊措施，大家因为怕把自己的 过多解法公开出来，不太敢在讨论区上讨论作业，能交流想法的空间就少了很多。但课程 影片底下是可以留言的，我自己偶尔也会留自己的想法或找到的参考资料在上面，老师都 会回覆，只是 NTU COOL 会自动把留言寄信给所有的修课同学，可能有点尴尬。 2. 由於这门课是研究所科号，修课同学跟助教基本上都是硕士班算是同届，就比较没有 上下关系。而且敢接演算法类科的助教我觉得都超猛，打从心底非常崇拜，我不敢接演算 法类科的助教有一个原因正是因为批改作业速度太慢，写文章给大家看 CP 值比较高。 3. 老师上课给的 primal-dual 例子超赞令人一目了然，让我不需要再背公式规则，直接 从例子推广到其他问题上还能加深印象。 4. 准备这门课的其中一个技巧，就是要弄懂怎麽去调整那些改得动的演算法的参数。举 例来说，如果要把背包问题的每个物品价值无条件进位成某个实数 b 的整数倍，那这个 b 在其他等价问题中的角色是什麽？再考虑另一个稍加限制的装箱问题：「全部的物品只 有 k 种大小，而且每个物品的体积都≧ε/2 (每种大小的物品个数并没有任何限制)」， 那 k 和ε在其他等价问题中的角色是什麽？ 5. 整学期下来，我还深刻体会到其他人 (老师或同学) 做得到，自己却无法望其项背的 能力，那就是自行悟出一个问题背後比较 high-level 的想法或算法。举例来说，期末考 有一题要证明某个随机变数的期望值 < 100，我第一时间就是机械地算，但老师所期望的 算法可以很方便地就得到一个常数 c < 100 的上界。这边也呼应到一个现实生活中经常 出现的场景：有时候那个捷径其实很难找到，人们可能不小心为了找那个捷径而耗费过多 时间，还不如直接选一般的路走比较省时。另一个例子是 The Power of Two Choices， 因为它的证明本身非常复杂 (所以作业考试也不出)，老师下一堂课 recap 的时候马上就 用一个更简洁的想法再重述一遍，而这个想法是我自己想不到的。 6. 我修课的时候还意外发现 The Power of Two Choices 的由来其实蛮有趣的，Sci-Hub 可以协助你方便找到相关论文。 7. 别小看 union bound，它在估计 error event 发生机率上界的时候很好用！ 8. 这门课让我知道自己不适合从事理论研究，举例来说当你意外设计出一个如期中考 30 分 MFLP 演算法的时候，如果你还不知道它的 approximation guarantee，你有没有毅力 坚持下去找到一个 3-approx. 的证明 (又该坚持多久？)，还是先摆一边跑去做其他待办 事项？在前面小题的 hints 都还没出现之前，你根本无从下手。我考完在检讨这一题的 时候是翻找了第 2 本课本＋在床上 emo 了一个小时多才想到的，虽然想出来真的很爽但 还没想出来之前的心态其实颇焦虑，因为只有一周的时间，如果真的把理论研究作为自己 的职业恐怕会严重影响到自己的身心健康。 9. 我最喜欢的作业题目是有关於 Weighted Set Cover 的 H(n)-approx. algo，最喜欢 的章节是 derandomization，这个章节把随机演算法和近似演算法两大看似独立的主题很 巧妙地串接起来！ 10. 老师在最後一堂课作总结的时候说，你可能过了几年之後就会忘记这门课所教过大部 分演算法的各式细节，但这门课的宗旨就是希望带给修课同学见识到世界上还有各式各样 你所意想不到能解决 P class 以外问题的演算法。(老师是说几年以後，但我一个学期就 忘得差不多了哈哈。) 有人常开玩笑说「好课值得一修再修」，我不会在这门课讲同样的 话，因为要理解 large-scale algo 其实蛮耗费心力的，如果要修就要一次把课修好。这 门课的大魔王 MFLP 会以不同的姿态出现在不同的周次上，如果不是在该领域打滚多年， 只在网路上查查资料的话，根本不可能洞见这样的连结，足见老师在领域内的专业。 11. 我自己修这门课除了单纯想多了解传统演算法 (P class) 以外的世界还有什麽花样 可以玩、可以发展到什麽程度，还有个更重要的原因就是，去年是这门课从 105-2 之後 暌违多年第一次开课，老师与我同届的学生只有我修得到课，其他人也很好奇这门课修起 来究竟感觉如何。 　　　Ω 私心推荐指数(以五分计) ★★★★★ ＊这门课适合： 单纯瞻仰老师风采如我 ★★★★★★★★★★★★★★★★★★★★★★★★★★★★ 通灵能力十足，资奥、数奥大电神 ★★★★★★★★★★★★★★★★★★★★★★★ 想见识传统演算法以外的世界 ★★★★★★★★★★★★★★★★★★★★★★★★★ ＊这门课不适合： 愿意花大量时间写作业且能拿高分，但无法在短时间的考试内正常发挥实力的同学 ☆ 有根深蒂固的观念认为只要够努力够认真就一定能拿 A+ 的同学 ☆ 准备考试的心力 (兴奋程度) 跟结果分数如果不成正相关会很 emo 的同学 ☆ 　　　α 建议预修课程 这段是我自己加的，除了老师在课程网上注明的演算法、机率、离散数学、资料结构以外 其实微积分 (基础函数操作与极限的计算)、基础复杂度理论也很需要，因为学期前半段 常 reduction 来 reduction 去的，学期後半段的 counting 章节就和 #P class 有关， 要 amplify 一个 randomized algorithm 到一定的成功机率也跟 PTM (probabilistic Turing machine) 息息相关。而 MAX-3SAT 的 (7/8)-approx. 证明会用到 PCP theorem, 但这个上课只有提结果而已，没带证明。我当学期有同时修资工系陈伟松老师的复杂度理 论专题，在这块帮助不小，可惜老师已经换学校了。另外在一般理论课俗称的 math matu rity，这门课会需要一点，但又没像资工系李老师的课这麽吃重。 　　　Ψ 总结 这门课旨在介绍传统演算法以外的花花世界，不应该带有传统演算法的刻板印象来参与这 门课，large-scale 最大可以到传统的好几倍。复习时建议只 focus 在改得动的 algo 就好，其他改不动的 algo 原则上不用太放在心上。老师非常和善又强大 (到容易让人忘 记感谢，经常不小心视为理所当然) 而且很认真准备，助教也比我厉害好几倍，全心投入 一定能收获不少。建议抱团修不然遇到想讨论的时候等不到老师又只能自言自语很尴尬， 彷佛你自己搭捷运的时候只能用手机滑着批踢踢八卦板然後科科笑 (颗颗笑)。惟选课前 要注意一下成绩考核是否符合自己的期望。It's not an easy course, but good luck and have fun! 最後再强调一次： (虽然同意转发，但目的是希望有选到这门课的同学不要走错棚，请不要对文章内与上述 目的无关的文字妄自评论。) 112-2: https://course.ntu.edu.tw/courses/b23c853a-53a7-4922-8c0c-959afd832910 111-2: https://course.ntu.edu.tw/courses/29013e18-7f09-4671-953a-af773b2da113 105-2: https://webptt.com/cn.aspx?n=bbs/NTUcourse/M.1499070488.A.82E.html (在 111-2 学期以前唯一的心得文) 另外我修课时每周有打下逐字稿 (不然复习的时候还要去拉影片的时间轴颇费时)，如果 有人需要的话我可以每周更新在推文。祝看到这里的你开学愉快～ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.218.58 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTUcourse/M.1708257984.A.1A2.html 以下是去年的周更笔记，我会注意尽量不透漏作业或考试内容，另外笔记内容乃自己消化 过後之第二手资料，未必保证正确或跟上课内容相同，请斟酌使用～ Week 1: https://drive.google.com/file/d/1UuyFmhL6wbn8SFBFFpKTDQ-ES90qyVF8/view Week 2: https://drive.google.com/file/d/1GAk4v5xc8knIvi3h0hrsujaciAWe45xF/view Week 3: https://drive.google.com/file/d/1dqHeryK9MMuOBxP966N6yQ3EadYvF9kU/view Week 4: https://drive.google.com/file/d/13jMUdGHwMfVKw5PlRdKen4AdR6rKo3lg/view Week 5: https://drive.google.com/file/d/1Q0YF2MzOr7omtRdqUuttAYJh-jGuR-pT/view Week 6: https://drive.google.com/file/d/1Q3xaVs86Q9nFcY6L6IRrxJjKubty-Xb0/view Week 7: https://drive.google.com/file/d/1pNTu3XO5UAT4_j2z1WB-0_h232GE1OFz/view Week 8: (Midterm) Week 9: https://drive.google.com/file/d/1s1aU8slulBDaH-Ymx81THoM5Fg_kgfq0/view Week10: https://drive.google.com/file/d/1JzkggeQnJpglL74srqnehTFdNrktlf9M/view Week11: https://drive.google.com/file/d/1jW5ZS6xSG2oTZ6vbku1TSJkSavBVSf8s/view Week12: https://drive.google.com/file/d/1wjtl6g7n82tq2e59aLfh54k-9jicX8gC/view Week13: https://drive.google.com/file/d/1_Asu2nLQJfJxs3pATxe9roYmht5zvJS_/view Week14: https://drive.google.com/file/d/1EaHQLcusg6xGBBJaNBpeBM0LLI-fz5MG/view ============================================================================== While taking this course, consider the following online optimization problem. 1. During this semester, you are participating in a 3-hour lecture each week (except the midterm and final). The given lectures are always accompanied with some induced love. Without considering the next problem beforehand, how would you characterize such love in your own opinion? Provide your characterization and the corresponding reason. Usually, formulation is required, and you may also want to do a little bit of quantization if necessary. 2. Based on your characterization in (1), how would you optimize, in each week, such accumulated love received so far in the sense that your understanding of the algorithms given in the lectures would be faster and deeper? Give your optimization algorithm. Also specify the reference if your algorithm is from the existing literature. 3. Is the algorithm efficiently implementable? If yes, derive the algorithm's time complexity and explain your derivation; otherwise, explain why. 4. Based on the same characterization, in what sense would your optimization procedure be the easiest to design and efficiently implementable? We wish that this sense is also applicable to your study in this course. 5. Do you think that your characterization in (1) is already suitable for answering (2) and (3)? For instance, the optimization algorithm is efficiently implementable. If not, could you provide another characterization and answer (2) and (3) again? ============================================================================== 以上问题借镜自资工系李彦寰老师 112-2 开的《预测、学习、与赛局 (CSIE5002)》课程 里面的 HW0 和 HW1. ※ 编辑: alan23273850 (140.112.218.58 台湾), 05/24/2024 22:14:53