課程資訊

Design Strategies for Computer Algorithms

109-1

CSIE7130

922 U1810

3.0

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

•　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)
•　(P&S) Bhattacharya, Jadhav, Mukhopadhyay, and Robert, "Optimal
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) Güting, "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%

 課程進度
 週次 日期 單元主題 第1週 9/14 課程介紹、Greedy Method 第2週 9/21 Greedy Method、DP 第3週 9/28 DP 第4週 10/05 DP、P&S 第5週 10/12 P&S 第6週 10/19 P&S、B&B 第7週 10/26 B&B 第8週 11/02 第一次考試 第9週 11/09 B&B、D&C 第10週 11/16 D&C 第11週 11/23 D&C 第12週 11/30 D&C、Plane Sweep 第13週 12/07 論文報告: 第 1 組、第 2 組 第14週 12/14 第二次考試 第15週 12/21 論文報告: 第 3 組、第 4 組 第16週 12/28 論文報告: 第 5 組、第 6 組 第17週 1/04 論文報告: 第 7 組、第 8 組 第18週 1/11 補考