→ aggress5566: 1應該就很平常的KMP吧？ 01/17 18:03
→ aggress5566: 10 應該是randomized algorithm 我也還沒看QQ 01/17 18:03
→ aggress5566: 11應該是output整顆Tree 01/17 18:03
→ aggress5566: 15用greedy應該沒問題 01/17 18:03
推 a1596482: 1. 條件式還有一個Pi+1=/=Pj+1，應該只剩f(6)=3，其他 01/17 18:50
→ a1596482: 為-1 01/17 18:50
推 a1596482: 9. 是不是只有extract-min是logn ，其他都是1？ 01/17 18:52
→ aggress5566: 那不是本來就是定義嗎 囧 01/17 19:03
推 howard31622: 第十題我看了是哭笑不得 01/17 19:53
→ howard31622: 乾...我沒有被很熟那段 01/17 19:53
→ howard31622: 不過這題真的是送分題 01/17 19:53
→ howard31622: 你沒有把洪逸的講義看熟喔 01/17 19:53
→ howard31622: 雖然多希望考這種 01/17 19:53
→ howard31622: 因為我不用擔心我選擇題寫不完 01/17 19:53
→ howard31622: 而且這個分數一定拿得到不少 01/17 19:53
→ howard31622: 還有第九題你寫錯了 01/17 19:54
→ howard31622: 那個筆記有 01/17 19:54
推 FRAXIS: 15題應該可以在 O(|E|)時間內解 01/17 20:52
→ aggress5566: 其實應該是看熟才知道不能用他筆記上的證吧XD 01/17 21:17
推 winiel559: 15不需要sort，一個個檢查顏色正不正確就好了 01/17 21:37
→ painechaos: 回agg大:我是後來對答案時發現有討論這題，對於f(i)=t 01/18 00:02
→ painechaos: he largest i<j 這段的意思有點難以理解 01/18 00:02
→ painechaos: 請問第11題你會怎麼寫呢，有點摸不著頭緒該如何下筆 01/18 00:02
→ painechaos: 第15這樣分析還ok囉? 01/18 00:02
→ painechaos: a大:請問對於f(i)=the largest i<j...這段的你是如何 01/18 00:12
→ painechaos: 解讀的? 01/18 00:12
→ painechaos: 剛剛發現union寫錯了,extract-min我要再找找，謝謝你 01/18 00:12
→ painechaos: 的提點 01/18 00:12
→ painechaos: h大:這題我只有看個印象，沒有認真去背它@@ 01/18 00:21
→ painechaos: 剛剛找了一下，應該是這個推導 01/18 00:21
→ painechaos: 那時候看完覺得實在沒把握在時間緊迫的情況下寫出來， 01/18 00:21
→ painechaos: 所以就投注心力在其他基本題上了xD 01/18 00:21
→ painechaos: F大 w大:謝謝你們，我再思考看看如何表達 01/18 00:24
→ aggress5566: 你說failure function嗎 我就用KMP下去做而已 01/18 00:33
→ aggress5566: 然後你貼的筆記 Hmm 我覺得出題教授應該是看了這個 01/18 00:34
→ aggress5566: 出了這題 XD 01/18 00:34
推 winiel559: 想了一下15好像還是要sort 01/18 08:47
→ a1596482: 1. 我覺得應該是f(j)才對 01/18 08:58
推 yaya517: quick sort avg. prove跟你一樣..看到覺得不會 翻筆記看 01/18 09:12
→ yaya517: 到一樣的東西 覺得自己考試時應該還是寫不出來XD 01/18 09:12
推 FRAXIS: 15 就算要排序 因為只有兩種類型 counting sort 就可以了 01/18 11:26
推 sarsman: 1我也覺得定義應該是f(j)，i都是input了找什麼largest啦X 01/18 14:58
→ sarsman: D 01/18 14:58
推 sarsman: 11，將m個sorted list建成m個只有一顆node的tree，定義no 01/18 16:00
→ sarsman: de weight為element個數 01/18 16:00
推 sarsman: 挑兩個weight最小的tree（令為T1、T2）；再新增一個一顆n 01/18 16:05
→ sarsman: ode的tree （令為T），將T1、T2接在T的左右子樹 01/18 16:05
→ sarsman: T的root weight為T1跟T2的weight sum，重複到剩下一棵tre 01/18 16:07
→ sarsman: e就是輸出 01/18 16:08
→ painechaos: agg大:如果因為這樣多拿了點分數，那真是賺到了xD 01/18 17:54
→ painechaos: y大:我覺得還是穩穩地把握其他基本分比較實在，這題就 01/18 17:54
→ painechaos: 給高手得分吧QQ 01/18 17:54
→ painechaos: w大、F大:演算法設計的部分我比較不熟要再多思考，先 01/18 17:56
→ painechaos: 謝謝指教 01/18 17:56
→ painechaos: 謝謝s大的第11題，我了解node該怎麼定義了! 這是Huffm 01/18 18:00
→ painechaos: an的應用吧？ 01/18 18:00
推 leoone: 15題就先排序 把set依序由小排到大在 兩兩做merge 01/19 20:49
→ leoone: 11題打錯 01/19 20:49
→ leoone: 15題 我是把red edge設0 blue edge設1做dijkstra 01/19 20:50
→ leoone: 不對kruskal打錯 01/19 20:51
→ leoone: 一直打錯XDD 01/19 20:52
推 tinhanho: 1很奇怪 但f(8)應該是0吧?? 12/16 00:12
→ tinhanho: 直接用KMP的failure func. 看的話 12/16 00:13