演算法 Term Project 實施要點

每個同學尋覓一個題目，將該問題的一個或多個演算法撰寫程式，加以測試分析。若能改良演算法，則更佳。最後需撰寫一份完整的分析報告

題目來源有二：

1. 課本的Voronoi diagram 演算法

2. 自行尋覓適合做為演算法課程程式設計的題目。

Term Project 實施時程如下：

  1. 起算日為93年11月9日
  2. 第一、二週找尋題目、研讀資料、確立演算法等。並將題目以及其簡易說明張貼於本課程BBS版 (bbs3.nsysu.edu.tw, cse-algo版)，以供他人參考(請於 93年11月23日前完成）。題目經核定後，才能進行下一個階段。格式如下：

             姓名：
             系級：
             學號：
             題目：
             說明：（100字至200字，請以中文書寫，內可含英文專有名詞）
                           (若為Voronoi diagram 則無須說明）      

  1. 第三、四週撰寫程式、進行初步測試。(於 93年12月7日查驗初步成果，請於該日攜帶作品前來上課，課後demo)
  2. 第五、六週完成最後實驗數據、撰寫報告(於 93年12月21日查驗最後成果，請於該日攜帶作品前來上課，課後demo)。
  3. 繳交報告期限為93年12月21日。

注意事項：

  1. 題目為Voronoi diagram者，演算法須為課本之divide-and-conquer 方法，其操作介面須為視窗介面。此題目之資料結構較複雜，需花心思好好設計，亦可參考下列書籍 

Atsuyuki Okabe,    Barry Boots,    Kokichi Sugihara,   Sung Nok Chiu 
 Spatial Tessellations : Concepts and Applications of Voronoi Diagrams
索書號   QA278.2 O36 1992
Sec. 4.2 Data Structure for Representing a Voronoi Diagram, pp.215~pp.223

  1. 撰寫程式時，不限使用何種程式語言。 
  2. 撰寫程式，不得抄襲他人或放置於網路上的程式。若經發現，本學期本課程以不及格論。
  3. 程式需有「版權宣告」的功能，形式不拘，但宣告內容需包含學號及姓名。

  4. 報告以 htm 檔案為主，製作成一個網頁。並請注意，網頁連結不要使用絕對位址（除非必要）。繳交報告時，請將所有檔案（程式原始碼、執行檔、報告）壓縮成一個 zip 檔案，並e-mail 至下址：

    homework@par.cse.nsysu.edu.tw

報告內容應含以下項目：

題目、系級、姓名、學號

簡介：含問題簡述、可能有哪些演算法可以使用、程式測試結論等

問題敘述：詳細說明問題（若知道問題的起源，亦請加以說明）、最好以範例解釋問題。

演算法：詳細描述解題的演算法，演算法須以條列式列出（如同課本演算法格式）。最好以範例解釋演算法。如果有改良之處，亦在此描述。

程式設計：將演算法於程式設計中，需要使用的資料結構，需注意的細節或特別的技巧，在此部分講述。

實驗結果：首先說明測試的環境，包含使用的電腦硬體系統（CPU型號、記憶體容量等）、作業系統、編譯器名稱及版本。然後列出測試數據，並與演算法的時間複雜度( time complexity)進行比較分析。實驗數據應包含執行所需時間、測試資料量、答案品質等。實驗結果可用表格列出數據，亦可以圖表列出結果，或兩者並用。對於實驗數據，應做簡單說明。若數據呈現某些料想不到的結果，請找出理由加以說明。

結論與心得：說明所得結論、可能可以改良之處、心得等。

參考文獻：列出所用到的書籍或論文。

附錄：程式碼

註：1. 題目為Voronoi diagram者，報告內容可以不含：簡介、問題敘述、演算法、參考文獻。
        2. 本要點若有未盡事宜，將在本課程網頁上修改之。