課程資訊

Design Strategies for Computer Algorithms

107-1

CSIE7130

922 U1810

3.0

Ceiba 課程網頁
http://ceiba.ntu.edu.tw/1071CSIE7130_

這門課的目的在於學習演算法設計的六個基本策略，如下所示。

Greedy Method
Dynamic Programming (DP)
Prune-and-Search (P&S)
Branch-and-Bound (B&B)
Divide-and-Conquer (D&C)
Plane Sweep

這門課有二次程式考試。第一次考試要求修課同學設計能解決
the longest common subsequence problem 的 DP 程式與能解決
two-dimensional linear programming problem 的 P&S 程式。
第二次考試要求修課同學設計能解決 the 0/1 knapsack problem
的 B&B 程式與能解決 two-dimensional closest pair problem 的
D&C 程式。每次考試都有一次補考的機會，補考後成績之計算

修課同學必須閱讀以下四篇論文 (DP、P&S、B&B、D&C 各一篇)，
並繳交書面閱讀報告。

(DP) Wagner, "The string-to-string correction problem," Journal of the ACM,
vol. 21, no. 1, 1974, pp. 168-173.
(P&S) Megiddo, "Linear-time algorithms for linear programming in R3 and
related problems," SIAM Journal on Computing, vol. 12, no. 4, 1983, pp.
759-776 (only Section 3 is required).
(B&B) A personal assignment problem solved by the branch-and-bound
strategy (Section 5-6 of Introduction to the Design and Analysis of Algorithms
by Lee, Tseng, Chang and Tsai)
(D&C) Imai, Iri, and Murota, "Voronoi diagram in the Laguerre geometry and
its applications," SIAM Journal on Computing, vol. 14, no. 1, 1985, pp. 93-105.

問題定義
解法敘述 (勿列出詳細程式碼)
讀後心得

問題定義與解法敘述必須用例子與圖表輔助說明。閱讀報告請以中文書寫 (可夾雜

態度 (是否用心書寫？)
能力 (是否看懂論文且掌握重點？是否敘述清楚且精簡扼要？
是否使用合適的例子與圖表輔助說明？)

修課同學將分成八組負責研讀以下八篇論文(DP 三篇、P&S 一篇、B&B 與
D&C 各二篇)，並在課堂上作報告(presentation)。

(DP) Knuth, "Optimal binary search trees," Acta Informatica, vol.1, 1971, pp.14-25.
(DP) Hsu and Du, "New algorithms for the LCS problem," Journal of Computer and
System Sciences, vol.29, 1984, pp.133-152.
(DP) Wang, Chen, and Park, "On the set LCS and set-set LCS problems," Journal of
Algorithms, vol.14, no.3, 1993, pp.466-477 (ignore Section 3: The Set LCS Problem).
some intersection radius problems," Computing, vol.52, no.3, 1994, pp.269-279
(ignore Section 2: Intersection Radius Problem for Hyperplanes).
(B&B) Wang and Lee, "An efficient channel routing algorithm to yield an optimal
solution," IEEE Transactions on Computers, vol.39, no.7, 1990, pp.957-962.
(B&B) "A Job Scheduling Problem", Section 5-9 of Introduction to the Design
and Analysis of Algorithms by Lee, Tseng, Chang and Tsai.
(D&C) Guting, "Optimal divide-and-conquer to compute measure and contour for a
set of iso-rectangles," Acta Informatica, vol.21, 1984, pp.271-291.
(D&C) Lee, "An optimal time and minimal space algorithm for rectangle intersection
problems," International Journal of Computer and Information Sciences, vol.15, no.1,
1984, pp.23-32.

熟悉上述六種設計演算法的基本策略
增進 problem solving 與程式設計的能力
增進科技論文閱讀的能力
增進科技論文報告的能力與技巧

修習過資料結構課程
熟悉至少一種程式語言並具備寫程式的能力

Office Hours

(僅供參考)

 No. 項目 百分比 說明 1. 第一次考試 20% 2. 第二次考試 20% 3. 論文報告 20% 4. 閱讀報告 40%

 課程進度
 週次 日期 單元主題 第1週 9/10 課程介紹、Greedy Method 第2週 9/17 DP 第3週 9/24 中秋節放假 第4週 10/01 DP 第5週 10/08 P&S 第6週 10/15 P&S 第7週 10/22 P&S、B&B (10/22 的課程改在 10/27 10:20 上課) 第8週 10/29 B&B 第9週 11/05 第一次考試 第10週 11/12 B&B、D&C 第11週 11/19 D&C 第12週 11/26 D&C、Plane Sweep 第13週 12/03 論文報告: 第 1 組、第 2 組 第14週 12/10 論文報告: 第 3 組、第 4 組 第15週 12/17 第二次考試、第一次考試補考 第16週 12/24 論文報告: 第 5 組、第 6 組 第17週 12/31 調整放假 第18週 1/7 論文報告: 第 7 組、第 8 組、第二次考試補考