版上有關106交大的文章蠻少的@@ 所以直接po上來跪求指教
http://i.imgur.com/3z5eu4h.jpg
http://i.imgur.com/WAvH7QW.jpg
http://i.imgur.com/bDgqZqI.jpg
http://i.imgur.com/TYegNa1.jpg
http://i.imgur.com/srd34BN.jpg
http://i.imgur.com/9pREQuJ.jpg
http://i.imgur.com/x4OG9cT.jpg
http://i.imgur.com/LO7lcCj.jpg
http://i.imgur.com/DSPXwXH.jpg
http://i.imgur.com/ysnD99S.jpg
比較有疑惑的是第1、3、11、15題
1.一開始我是用課本定義的pi去做再轉換為p，做完後看了題目的定義跟印象中的不太相同，爬文後發現定義有改，但用題目的定義去操作還是怪怪的
3.看完程式碼，我的想法是第一輪q=n1開始往後比較，n1的value=8可以被2整除且後面的value皆小於8，所以一直swap直到8跑到n4;第二輪q從n2比較，最後得到3 2 7 8 ，這樣的想法正確嗎？
10.這題我自認在考場時也不會寫，所以直接放棄...
11.第一眼看到"greedy"和"2-way tree"，腦海中浮現的想法是Huffman algo，但看到optimal merge tree就不懂要的是怎樣子的tree
15.看到spanning tree就想到Krustal's algo和Prim algo，之後決定採用Krustal，接著令red edge weight=0,blue edge weight =1的想法下去做，請問這樣子可行嗎？
希望大家不吝指教@@

1應該就很平常的KMP吧？10 應該是randomized algorithm 我也還沒看QQ11應該是output整顆Tree15用greedy應該沒問題

1. 條件式還有一個Pi+1=/=Pj+1，應該只剩f(6)=3，其他為-19. 是不是只有extract-min是logn ，其他都是1？

那不是本來就是定義嗎 囧

第十題我看了是哭笑不得乾...我沒有被很熟那段不過這題真的是送分題你沒有把洪逸的講義看熟喔雖然多希望考這種因為我不用擔心我選擇題寫不完而且這個分數一定拿得到不少還有第九題你寫錯了那個筆記有

15題應該可以在 O(|E|)時間內解

其實應該是看熟才知道不能用他筆記上的證吧XD

15不需要sort，一個個檢查顏色正不正確就好了

回agg大:我是後來對答案時發現有討論這題，對於f(i)=the largest i<j 這段的意思有點難以理解請問第11題你會怎麼寫呢，有點摸不著頭緒該如何下筆第15這樣分析還ok囉?a大:請問對於f(i)=the largest i<j...這段的你是如何解讀的?http://i.imgur.com/hswayIs.jpghttp://i.imgur.com/TRRGsxi.jpg剛剛發現union寫錯了,extract-min我要再找找，謝謝你的提點h大:這題我只有看個印象，沒有認真去背它@@剛剛找了一下，應該是這個推導http://i.imgur.com/J4PStP6.jpghttp://i.imgur.com/PBWQtXT.jpg那時候看完覺得實在沒把握在時間緊迫的情況下寫出來，所以就投注心力在其他基本題上了xDF大 w大:謝謝你們，我再思考看看如何表達

你說failure function嗎 我就用KMP下去做而已然後你貼的筆記 Hmm 我覺得出題教授應該是看了這個出了這題 XD

想了一下15好像還是要sort

1. 我覺得應該是f(j)才對

quick sort avg. prove跟你一樣..看到覺得不會 翻筆記看到一樣的東西 覺得自己考試時應該還是寫不出來XD

15 就算要排序 因為只有兩種類型 counting sort 就可以了

1我也覺得定義應該是f(j)，i都是input了找什麼largest啦XD11，將m個sorted list建成m個只有一顆node的tree，定義node weight為element個數挑兩個weight最小的tree（令為T1、T2）；再新增一個一顆node的tree （令為T），將T1、T2接在T的左右子樹T的root weight為T1跟T2的weight sum，重複到剩下一棵tree就是輸出

agg大:如果因為這樣多拿了點分數，那真是賺到了xDy大:我覺得還是穩穩地把握其他基本分比較實在，這題就給高手得分吧QQw大、F大:演算法設計的部分我比較不熟要再多思考，先謝謝指教謝謝s大的第11題，我了解node該怎麼定義了! 這是Huffman的應用吧？

15題就先排序 把set依序由小排到大在 兩兩做merge11題打錯15題 我是把red edge設0 blue edge設1做dijkstra不對kruskal打錯一直打錯XDD