Reading List

之前的 reading list 我和投影片一起公佈在
http://solomon.ipv6.club.tw/Course/Algorithm/,
若是自己有找到更合適的 paper 也行，請直接 reply
告訴我篇名、作者、出處。

最好是把 PDF 檔下載後放在自己的個人目錄，然後把
URL 也附上來。這樣我可以幫你們一起讀一下那篇 paper。

Quincy Wu
Apr. 19

4/26 調課

原本 4/26 09:00-10:00 的那堂課，調到 4/28 09:00-10:00.

4/28 期中考

期中考試

時間：4/28 (Thursday) 09:00-12:00
地點：科三207（同上課地點）
方式：Closed Book
難易度：不會太難。要把基本的定義和演算法，以及複雜度分析弄懂。

Homework 5

Write a program which runs the PTAS of 0/1 Knapsack Problem. (Due: April 19th)

•Input format:

•

8

100

0.75

90 33

61 30

50 25

33 17

29 15

23 12

15 10

13 9

• The first row means the number of items.
• The second row means the capacity.
• The third row is the error ratio.
• The first element of the fourth row means the profit and the second element means the weight of first item, and so on.

4/12 及 4/14 停課

吳坤熹老師接獲國防部的召集令，下星期要去台東接受為期一週的教育召集，故停課一週。
請大家利用這個星期寫作業。

Homework 4

•Use the example given in P.493,

1. –Run the PTAS with e=0.75.
2. –What is the solution you obtain?
3. –What is the error ratio?

•Due: April 14th