※ 本文是否可提供臺大同學轉作其他非營利用途？（須保留原作者 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/m.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/m.aspx?n=bbs/NTUcourse/M.1499070488.A.82E.html (在 111-2 學期以前唯一的心得文) 另外我修課時每週有打下逐字稿 (不然複習的時候還要去拉影片的時間軸頗費時)，如果 有人需要的話我可以每週更新在推文。祝看到這裡的你開學愉快～ --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.218.58 (臺灣) ※ 文章網址: https://webptt.com/m.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