Design Strategies for Computer Algorithms

請修課同學於學期間務必隨時查看課程網頁,以免錯失重要訊息。
  • 2014-01-08:
    期末考補考將於2014-01-15下午15:30舉行。若同學在期末考時有資料未能通過測試,請把握補考機會,於補考時間攜帶自己的筆電至教室作測試。
  • 2013-12-13:
    期末考日期為2014-01-08,考試當天請攜帶自己的筆電至教室,沒有筆電的同學請事先與助教聯絡。
  • 2013-12-13:
    12/25上課時會播放電影美麗人生,同學們可先閱讀電影介紹:點此進入簡介
  • 2013-12-08:
    12/16~12/19助教出國,該週的TA hour暫停,同學們有問題可email與助教聯絡。作業三如同往常請繳交至R432,屆時會由其他同學代收。
  • 2013-11-29:
    公佈Program Assignment 4測資範例。
  • 2013-11-20:
    期中考補考將於12/4下課時間(18:30)舉行。若同學在期中考時有資料未能通過測試,請把握此次的補考機會,於補考時間攜帶自己的筆電至教室作測試。
  • 2013-11-18:
    公佈Program Assignment 3測資範例二組。
  • 2013-11-09:
    第三次與第四次作業繳交期限已公佈,請同學至作業區查看。
  • 2013-10-17:
    各組的論文報告題目與時程已公佈,每組報告時間為一小時,請至論文報告區查看。
  • 2013-10-14:
    本週上課(10/16)中間的下課時間將決定論文報告的題目,請各組組長留在教室抽籤,如組長缺席將由助教代抽。
  • 2013-10-14:
    期中考日期為11/13,考試當天請攜帶自己的筆電至教室,沒有筆電的同學請事先與助教聯絡。
  • 2013-10-11:
    公佈分組名單,請至論文報告區查看。名單以組別排序,每組成員為5~7人,其中備註欄若有標示"O"者為該組組長,請組長將自己的email寄給助教以便日後聯繫。
  • 2013-10-11:
    已上傳Paper reading作業二,請至作業區下載。
  • 2013-10-07:
    公佈Program Assignment 2測資範例二組。
  • 2013-10-03:
    論文報告的分組名單請在下次上課(10/9)前寄給助教,如未寄出則將由助教分配組別。
  • 2013-10-01:
    陳老師鼓勵同學們看papers時嚐試看懂papers內的proofs,但同學們的閱讀報告(Paper reading)與論文報告(Paper presentation)可忽略proofs。
  • 2013-10-01:
    第一個Paper reading的作業,同學們可從所列二篇論文中擇一閱讀。請注意,本學期的四次作業皆為個人報告,每人皆須繳交一份,唯有期末的Paper presentation部份才是以小組為單位。
  • 2013-09-27:
    已上傳Paper reading作業一的論文,請至作業區下載,閱讀報告的繳交期限為10/31。
  • 2013-09-23:
    公佈Program Assignment 1測資二組。
  • 2013-09-19:
    論文報告的分組開始進行,每組成員五人,決定好之後請各組寄一份名單給助教。若有需要協助分組可與助教聯絡。
  • 2013-09-16:
    更新課程講義"Dynamic Programming"(p.24),請同學至課程區下載。
  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. 課程大綱:

    • Dynamic Programming
    • Branch-and-Bound
    • Divide-and-Conquer
    • Prune-and-Search

    Options:
    • Greedy Method
    • Strategies for Computational Geometry
    • Strategies for Tree Searching
    • Strategies for Parallel Algorithms
    • Binary Tree Method
    • Randomized Algorithms
    • On-Line Algorithms

  3. 課程投影片於上課前公佈:

  1. 本學期共有四個Paper reading的作業,皆為個人報告。閱讀報告須包含問題定義、方法說明以及時間複雜度分析。方法的部分請舉一個例子來說明演算法的流程。若有任何其它的讀後心得,皆可在報告中說明。
  2. 作業請繳交至R.432
  3. 請一律以紙本繳交,若是電子檔請自行印出後繳交。

  1. Exercise 1
    Deadline: 2013-10-31 (17:00pm)
    • The String-to-String Correction Problem (by Wagner & Fischer)
      論文下載:(PDF)
      註:Hirschberg的論文不是用dynamic programming,因此建議尚未選取的同學們可考慮Wagner & Fischer的論文(使用dynamic programming)。

    • Algorithms for the Longest Common Subsequence Problem (by Hirschberg)
      論文下載:(PDF)
      註:Hirschberg的論文與另一篇使用dynamic programming的LCS論文(by Hsu & Du)有密切關係。Hsu & Du的論文將會在paper presentation時報告。

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

  3. Exercise 3
    Deadline: 2013-12-20 (17:00pm)
    • Voronoi Diagram in the Laguerre Geometry and Its Applications (by Imai, Iri, and Murota)
      論文下載:(PDF)

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

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