資訊處理 92 年演算法考古題

已知甲電腦在input size 為1000 時，執行A、B、C 三個演算法都需要1 分鐘， A、B、C 三個演算法的Time Complexity 分別為a n、b n2、c 10n（a、b、c 為常 數，n 為input size）。假設乙電腦的執行速度比甲電腦快10000 倍，請問對於A、 B、C 三個演算法，乙電腦在1 分鐘內可以解的input size 最大是多少？（24 分）

請證明利用Greedy Approach 來解Fractional Knapsack Problem 可以得到最佳解。 （15 分） 請設計一個Dynamic Programming 的演算法來解0-1。Knapsack Problem（須加上 適當的說明來解釋你的設計），並分析該演算法的Time Complexity。（15 分）

請簡述NP 與NP-Complete 的定義。（6 分） 請簡述Cook’s Theorem 的內容（不須證明），並說明其對研究NP-Complete 重要 性。（10 分） 要如何才能證明P=NP 或P≠NP？請分別說明。（10 分） 請問Sorting Problem 是不是NP？請說明原因。 （10 分）

請簡述何謂Pseudo-Polynomial-Time Algorithm？（10 分）