課程資訊

Design Strategies for Computer Algorithms

110-1

CSIE7130

922 U1810

3.0

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

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

common subsequence problem 的 DP 程式與一個能解決 2-d linear
programming problem 的 P&S 程式。第二次考試要求同學設計一個能解決
the 0/1 knapsack problem 的 B&B 程式與一個能解決 2-d closest pair
problem 的 D&C 程式。以上四個 problems 與其相對應的演算法在課堂上將

"原始成績+(補考成績-原始成績)x90%" 作為最終成績。

(DP) Wagner, "The string-to-string correction problem," Journal of the
ACM, vol.21, no.1, 1974, 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, 759-776 (only Section 3 is required).
(B&B) A personal assignment problem solved by the branch-and-
bound strategy (in Section 5-6 of Lee, Tseng, Chang and Tsai's
book: Introduction to the Design and Analysis of Algorithms).
(D&C) Imai, Iri, and Murota, "Voronoi diagram in the Laguerre
geometry and its applications," SIAM Journal on Computing,
vol.14, no.1, 1985, 93-105.

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

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

(DP) Knuth, "Optimal binary search trees," Acta Informatica, vol.1, 1971,
14-25.
(DP) Hsu and Du, "New algorithms for the LCS problem," Journal of
Computer and System Sciences, vol.29, 1984, 133-152.
(DP) Wang, Chen, and Park, "On the set LCS and set-set LCS problems,"
Journal of Algorithms, vol.14, no.3, 1993, 466-477. (ignore Section 3:
The Set LCS Problem)
algorithms for some intersection radius problems," Computing, vol.52,
no.3, 1994, 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, 957-962.
(B&B) Section 5-9 of Lee, Tseng, Chang and Tsai's book: Introduction to
the Design and Analysis of Algorithms.
(D&C) Guting, "Optimal divide-and-conquer to compute measure and
contour for a set of iso-rectangles," Acta Informatica, vol.21, 1984,
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, 23-32.

(若有需要)，相信對同學日後職場生涯有所助益。

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

修習過資料結構課程
具備撰寫程式的能力

Office Hours

(僅供參考)

 No. 項目 百分比 說明 1. 期中考 20% 2. 期末考 20% 3. 作業 40% 4. 分組報告 20%

 課程進度
 週次 日期 單元主題 第2週 9/27 課程介紹、Greedy Method 第3週 10/04 Greedy Method、DP 第4週 10/11 補假 第5週 10/18 DP 第6週 10/25 DP、P&S 第7週 11/01 P&S 第8週 11/08 P&S、B&B 第9週 11/15 校慶日停課 第10週 11/22 第一次考試 第11週 11/29 B&B 第12週 12/06 B&B、D&C 第13週 12/13 D&C 第14週 12/20 D&C、Plane Sweep 第15週 12/27 論文報告 (第 1 組、第 2 組、第 3 組) 第16週 1/03 第二次考試 第17週 1/10 論文報告 (第 4 組、第 5 組、第 6 組) 第18週 1/13 論文報告 (第 7 組、第 8 組) (1/17: 補考)