Design Strategies for Computer Algorithms

請修課同學於學期間務必隨時查看課程網頁,以免錯失重要訊息。
  • 2014-01-08:
    期末考的考試時間為1/15(四)10:20~12:00AM。學號為單號的同學請至R105教室,雙號的同學請至R107教室進行測驗。期末考補考將於1/23(五)11:00AM舉行。
  • 2014-01-08:
    期末考的測試範例中,"for reference only"的意思是同學們輸出的答案可以不用和範例給的資料相同,因為標準答案可能不唯一。
  • 2014-12-22:
    第六篇與第七篇論文的報告日期為12/25;第五篇與第八篇論文的報告日期為01/08。
  • 2014-12-07:
    期末考的考試時間為01/15上午10:20~12:00。程式的測資範例皆已上傳,考試當天請攜帶自己的筆電至教室,沒有筆電的同學請事先與助教聯絡。
  • 2014-12-07:
    第四次作業已公佈,請同學至作業區查看。
  • 2014-11-19:
    第三次作業已公佈,請同學至作業區查看。
  • 2014-11-18:
    期中考補考將於12/4 09:30AM(上課前)舉行。若同學在期中考時有資料未能通過測試,請把握此次的補考機會,於補考時間攜帶自己的筆電至教室作測試。
  • 2014-11-09:
    下次上課時間為11/20 10:20AM。
  • 2014-11-08:
    期中考的考試時間為11/13上午10:20~12:00。學號為單號的同學請至R105教室,雙號的同學請至R107教室進行測驗。
  • 2014-10-23:
    第二次作業已公佈,請同學至作業區查看。
  • 2014-10-23:
    期中考將於11/13舉行。程式的測資範例皆已上傳,考試當天請攜帶自己的筆電至教室,沒有筆電的同學請事先與助教聯絡。
  • 2014-10-02:
    第一次作業已公佈,請同學至作業區查看。
  1. Reference:

    Introduction to the Design and Analysis of Algorithms, R. C. T. Lee, S. S. Tseng, R. C. Chang and Y. T. Tsai, McGraw-Hill

  2. 課程大綱:

  1. 本學期共有四個Paper reading的作業。內容須包含問題定義、解法說明、以及時間複雜度分析,請儘量以例子闡述。解法說明部份,請儘量步驟化說明,勿列出詳細的程式碼。若有任何其它的讀後心得,皆可在報告中說明。
  2. 作業請繳交至R.432
  3. 請一律以紙本繳交,若是電子檔請自行印出後繳交。

  1. Exercise 1
    Deadline: 2014-11-21 (17:00pm)
    • The String-to-String Correction Problem (by Wagner & Fischer)
      論文下載:(PDF)

  2. Exercise 2
    Deadline: 2014-11-28 (17:00pm)
    • Linear-Time Algorithms for Linear Programming in R^3 and Related Problems (by Megiddo)
      僅需閱讀Section 3。
      論文下載:(PDF)

  3. Exercise 3
    Deadline: 2014-12-19 (17:00pm)
    • A Personnel Assignment Problem Solved by the Branch-and-Bound Strategy
      請閱讀參考書上第5-6節(p. 171~176),或參考以下連結。
      文獻下載:(PDF)

  4. Exercise 4
    Deadline: 2015-01-23 (17:00pm)
    • Voronoi Diagram in the Laguerre Geometry and Its Applications (by Imai, Iri, and Murota)
      論文下載:(PDF)

期中考日期訂於2014-11-13。 請同學事先完成以下程式(可使用C/C++或Python),並於考試時間攜帶自己的筆電至教室作測試。
  1. Program 1: Longest Common Subsequence (Dynamic Programming)
    範例下載:(PDF)
  2. Program 2: 2-Dimensional Linear Programming Problem (Prune-and-Search)
    範例下載:(PDF)
期末考日期訂於2015-01-15。 請同學事先完成以下程式(可使用C/C++或Python),並於考試時間攜帶自己的筆電至教室作測試。
  1. Program 3: 0/1 Knapsack Problem (Branch-and-Bound)
    範例下載:(PDF)
  2. Program 4: 2-Dimensional Closest Pair Problem (Divide-and-Conquer)
    範例下載:(PDF)
  1. Program tests (60%)
  2. Paper reading (40%)
  3. Paper presentation (-5%~+10%)
林蔚茵 Office: R432
E-mail: r97079@csie.ntu.edu.tw
TA hour:
週二 16:00 ~ 17:00
週三 16:00 ~ 17:00