各位學弟妹：
大家好，我是系上的研究生，吳兆麟。
本學期擔任演算法的助教，負責各位期中期末兩次考試的閱卷。
目前期中考的考卷已全部改完，我會在今天（週二）拿給老師，
所以各位應該在週四可以領回自己的考卷。
各位拿到考卷後若覺得有問題，可以來找我討論，
地點是系館地下室的智慧型機械人實驗室。
但是因為我有時候會在另外一間實驗室或必須MEETING，
所以想來找我討論的人最好先打系館分機120至實驗室確認，
或以email跟我聯絡約好時間：r89042@csie.ntu.edu.tw。
考卷上寫錯答案的地方，我大部分都有給予註解，
所以大家可以看看自己錯在什麼地方。
除了一些比較特殊的答案必須另作考量之外，
基本上是以下面的評分標準作為閱卷及給分的標準。
------------
1.滿分二十分，答對任意一題七分，任意兩題十四分。
Θ寫成Ο或Ω，扣一分。只寫答案，各得二分。
沒用Master Method的方式，分數折半計算。
2.有效的演算法，十分。Θ(n^2)演算法，十分。
寫出正確的pseudo code，額外加分。SORT，五分。LCS，五分。印出答案，五分。
3.能夠正確表示出演算法的流程，十五分。答案正確，五分。過程不完整，扣十分。
採用暴力法或觀察法時，必須寫出每一個digit的比較過程才算完整流程。
4.證明K列K行元素內容不變，二十分。
說明K列K行元素內容不變但無法證明，五分。
無法證明上述內容但寫出空間複雜度，五分。
討論方向錯誤寫成時間複雜度，零分。
5.(a)floor(n/2)*1/n ≦ 1/2。
說明median前後各n/2個數，十分。
證明方向相反，扣五分。沒有一般性，扣五分。
(b)演算法：
Step1: 使用select選出中位數Xk，O(n)。
Step2: 利用Xk計算出小於（大於）Xk之Xi之Wi總和，O(n)。
Step3: 若兩者之和均小於等於1/2，OK。
否則將和大於1/2的部分當作新數列回Step1。
寫出Step1，五分。寫出Step2，五分。寫出pseudo code，額外加五分。
注意事項：此小題不可使用partition，否則會破壞index而造成演算法失效。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.217