Algorithmics (演算法) 2017 (for 福師大)

Lecturer: 江振瑞
Teaching Assistants (TAs): 林育勳鍾偉勝林廷諭
Time: 週二 14:00~16:50
Place: E6-A203
TA Class: 週四 16:00~16:50 (資策會204)
Scoring：

期中考(分析與設計概念)(20%)
期末考(分析與設計概念)(25%)
程式設計作業、報告、課程參與度及程式設計競賽成績(55%) (作業報告連結)

TextBook:

My Book's Manuscript (book1-8.zip)
Introduction to the Design and Analysis of Algorithms -- A Strategic Approach (2/e), R.C.T. Lee et. al., McGraw Hill, 2005.
Introduction to Algorithms (3/e), Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, MIT Press, 2009.

Reference Books:

Algorithm Design: Foundations, Analysis, and Internet Examples, Michael T. Goodrich, Roberto Tamassia, Wiley, 2002. (有中譯本)
Computer Algorithms, Ellis Horowitz et. al., Silicon Press, 2008.
中文Java程式設計 (第三版) SIM-908A , 江振瑞著, 儒林出版社, 2006.
物件導向資料結構 — 使用Java語言, 江振瑞著, 松崗圖書公司, 2005.
Algorithms, S. Dasgupta, C. Papadimitriou and U. Vazirani, McGraw Hill, 2008.
Programming Challenges, Steven S. Skiena and Miguel Revilla, Elsevier, 2003.
The Algorithm Design Manual, Steven S. Skiena, Elsevier.

Syllabus:

1. (2/14)認識演算法 -- 從食譜到高階程式語言: (Alg-Intro.pptx)

.1 演算法名稱的由來
.2 什麼是演算法?
.3 演算法的例子
.4 如何表示演算法?
.5 如何實作演算法? (EuclidGCD.c)(EuclidGCD.cpp)(EucidCGDClass1.java)

(EucidCGDClass.java)

(EuclidGCD.py)
.6 演算法的正確性

Homework1: (Just choose 1 out of 5 problems; Due day: 2/16 before TA's class)

(A)

使用虛擬瑪(pseudo code)寫一個演算法，輸入一個整數n(n>2)並輸出小於n的最大因數(factor) (Write an algorithm using the pseudo code to input an integer n and output the n's largest factor that is less than n.)

(B)

使用虛擬瑪(pseudo code)寫一個演算法，輸入一個整數n(n>2)並輸出所有n除了本身以外的正因數(factor)總和 (Write an algorithm using the pseudo code to input an integer n and output the total summation of all n's factors except n.)
(C) 使用虛擬瑪(pseudo code)寫一個演算法，輸入整數n及m(n>m>2)，輸出所有比n小並大於m的n的因數(factor)總和，若無此因數則輸出0 (Write an algorithm using the pseudo code to input integers n and m, and output all n's factors larger than m and less than n.)
(D) 使用虛擬瑪(pseudo code)寫一個演算法，輸入一個整數n並判斷n是否為完美數(perfect number) (Write an algorithm using the pseudo code to input an integer n and output (decide) if n is a perfect number.)
(E) 使用虛擬瑪(pseudo code)寫一個演算法，輸入一個整數n(n>0)並判斷n是否為快樂數(happy number) (Write an algorithm to input an integer n and output (decide) if n is a happy number.)
註: 快樂數有以下的特性：在給定的進位制下，該數字所有數位(digits)的平方和，得到的新數再次求所有數位的平方和，如此重複進行，最終結果必為1。例如，以十進位為例：
28 → 2²+8²= 68 → 6²+8²=100 → 1²+0²+0²=1，因此28是快樂數

2. (2/21)演算法複雜度分析範例(以排序演算法為例)(Alg-Analysis.pptx)
.1 演算法的效能
.2 演算法的時間複雜度
.3 大O漸進記號
.4 降低演算法時間複雜度量級
.5 漸進記號(asymptotical notation): Big O, Big Omega, Theta
.6 多項式時間、指數時間及偽多項式時間演算法

.7 氣泡排序(bubble sort)演算法

.8 插入排序(insertion sort)演算法

Homework 2: (Just choose 1 out of 5 problems; Due day: 3/2 before TA's class)
(A) 在氣泡排序(bubble sort)演算法中，若在某回合中完全沒有任何資料對調，則可推論資料已經排序完成而立即結束演算法執行，這稱為改良

氣泡排序(improved bubble sort)演算法。請

以虛擬碼描述

「改良

氣泡排序演算法」。(請注意:在有些文獻中，所謂「氣泡排序

演算法」其實指的是「

改良

氣泡排序演算法」)

(B) 分析

改良

氣泡排序演算法最佳、最差與平均

時間複雜度

(C) 分析以下兩個階乘演算法的時間複雜度

Algorithm 遞迴階乘(int n)
Input: n為正整數
Output: n!之值
if n>1 then return n*遞迴階乘(n-1) //進行遞迴呼叫
else return 1 //停止遞迴呼叫

Algorithm 非遞迴階乘(int n)
Input: n為正整數
Output: n!之值
f←1
for i←1 to n do
f←f*i
return f

(D) 河內之塔(Towers of Hanoi)問題是一個古老而有趣的問題，由法國數學家Eduard Lucas在十九世紀初所創，河內之塔的名稱來自以下的傳說：
在越南河內市的市郊有一座寺廟，這廟中有三支金子做成的柱子，其中一根柱子上疊著64個大小不同圓盤，如下圖所示：

這些圓盤可以在三根柱子中移動，但是要遵守以下之規則：

每次只能移動一個圓盤
大圓盤不可以疊在小圓盤上面

這廟裡的出家人都很認真的在研究著怎麼移動圓盤，因為傳說若能將柱子中的所有圓盤都移動到另外一支柱子上時，則世界大同之日(原Eduard Lucas之說法為世界末日)則會來臨。

以下為河內之塔演算法，請分析其時間複雜度。

Algorithm 河內之塔( n )
Input：整數n代表「圓盤總數」
Output：將所有圓盤由一支柱子移動到另外一支柱子的順序。原盤的移動必須遵守一次只能移動一個圓盤，且大圓盤不可以疊在小圓盤上面的限制。
1. 將柱A上面n-1個圓盤透過「河內之塔(n-1)」之運算藉由柱C移動到柱B
2. 將柱A中僅剩的圓盤移到柱C
3. 將柱B上的n-1個圓盤透過「河內之塔(n-1)」之運算藉由柱A移到柱C

(E) 分析以下演算法(片段)時間複雜度:
(1) for i←1 to n do
for j←i to n do
for k←j to n do
x←x+1

(2) for i←1 to n do
j←i
for k←j+1 to n do
x←x+1

(3) k←n
while k>0 do
k←k/5
x←x+1

3. (3/7) 分治(divide-and-conquer)演算法: (Alg-Divide&Conquer.pptx)

若是問題規模(problem size)夠小，就直接解決之；反之，若問題規模較大，就將其分割(divide)成兩個或多個子問題(分割階段)，然後將每個子問題遞迴地(recursively)征服(conquer)解決之(征服階段)。之後再將每個子問題的解答合併(merge)，使其成為原問題的解答(合併階段)。
3.1 合併排序(merge sort)演算法 (屬分治演算法)
3.2 快速排序(quick sort)演算法 (屬分治演算法)

3.3 分治缺陷棋盤填滿(tiling a defective chessboard)演算法
3.4 分治二維求秩(2D rank finding)演算法
3.5 分治二維最大點(2D maxima finding)演算法
3.6 分治最近二維點對(closest pair of 2D points)演算法
(3/14) 3.7 最大連續子序列和(maximum contiguous subsequence sum, MCSS)演算法 (MCSS.zip)
Problem Set 3:
(A) 舉出一個方法讓快速排序(quick sort)演算法避免產生最壞狀況。
(B) 寫一個分治演算法來解決一個給定數值集合的求秩(rank finding)問題，並進行複雜度分析。
(C) 寫一個分治演算法來找出一群在X軸上的點中的最近點對(closest pair of points on X-axis)，並進行複雜度分析。

4. (3/14) 刪尋(prune-and-search)演算法: (Alg-Prune&Search.pptx)
刪尋(prune-and-search)演算法包含多次迭代 (iteration)，在每一次的迭代中，均刪除(prune)輸入資料的一部分(假設為f部份, 0<f<1)，而後再遞迴地(recursively)以相同的演算法在剩餘的資料中搜尋(search)出解答。在經過一定次數的迭代後，輸入資料的規模將會變得相當小，而能在常數時間內直接找出解答。
假設一個刪除-搜尋演算法的時間複雜度為T(n)，並且每次迭代所需的時間為O(n^k)(k為大於0的常數)，則T(n)=T((1-f)n)+O(n^k)。由於 1-f<1，我們可得T(n)=O(n^k)。

4.1 二元搜尋(binary search)演算法
4.2 選取(selection)與中位數(median)演算法
4.3 限制的一圓心(constrained 1-center)演算法
(not taught)4.4 簡化的二變數線性規劃(simplified 2-variable linear programming)演算法
Problem Set 4:
(A) 仿照merge sort的執行過程範例說明方式，畫圖說明S=(-2, 1, -3, 4, -1, 2, 1, -5)使用最大連續非空子序列和分治演算法(MCSS演算法)」的執行過程。
(B) 仿照merge sort的執行過程範例說明方式，畫圖說明S=(-2, -1, -3, -4, -1, -2, -1, -5)使用最大連續可空子序列和分治演算法(MCSS演算法)」的執行過程。
(C) 在選取刪尋演算法中，若每個分割子集改為3個元素，則其最壞狀況時間複雜度是否依然為O(n)，為什麼?
(D) 在選取刪尋演算法中，將每個分割子集改為6個元素後重新分析其時間複雜度。
(E) 有一個刪尋演算法其時間複雜度為T(n)=T((7/8)n)+cn²，詳細分析其時間複雜度並以大O記號表示。
(F) 以刪尋演算法解決以下限制的一圓心問題: (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(2,0)，圓心在y=0上。(可以精確繪圖說明即可)
(G) 以刪尋演算法解決以下限制的一圓心問題: (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(4,0)，圓心在y=3上。(可以精確繪圖說明即可)

5. (3/21) 貪婪演算法(greedy algorithm): (Alg-Greedy.pptx)
貪婪演算法(greedy algorithm)一步步地建構出一個問題的完整解答。其每一步都藉由貪婪解題策略(greed strategy)增加一部份的解答到完整解答中。所謂貪婪解題策略為: 每一次都選擇當下最好的部份解答加入完整解答中。
5.1 背包演算法(knapsack algorithm) (帶出0/1背包問題後可以在之後講授NP-hard問題)
5.2 Huffman編碼演算法
5.3 Kruskal最小含括樹(minimum spanning tree, MST)演算法
5.4 Prim最小含括樹(minimum spanning tree, MST)演算法
5.5 Dijkstra最短路徑演算法
Problem Set 5:
(A) 一個背包容量為10，現在有5個物品，重量分別為4、3、6、2、5，價格分別為10、9、 12、4、8，求背包能夠裝入零碎(fractional)物品的最大價值為何?

(B) 分別利用Kruskal's演算法與Prim's演算法求出以下圖(graph)的最小生成樹 (minimum spanning tree, MST)

(C) 利用Huffman 編碼演算法替以下字元編碼A(42%)、B(17%)、C (28%)、D (13%)。(備註:括號中為字元出現頻率)
(D) 利用Dijkstra演算法求以下圖(graph)頂點4到各頂點的最短路徑(shortest path)距離(成本)
Introduction to Software Defined Networking (SDN) Multicast (SDN-Multicast.pptx)

6. (3/28) 動態規劃(dynamic programming)演算法: (Alg-DP.pptx)
動態規劃(dynamic programming)演算法籍由將原問題分解成一系列子問題 (subproblems)，並依序解決子問題來解決原問題。為避免一再地解重複的子問題，一旦解出子問題的解答(solution)，即會將其存在表格(或陣列)中。當需要用到某一子問題的解答時，與其重新計算其解答，演算法會取而代之地從表格中直接取出其解答以節省計算時間，是一個「以空間換取時間」的演算法。一個動態規劃演算法會先從最簡單的子問題先解起，並以一定的程序持續運行直至求出原問題解答為止。

最佳解原則(Principle of optimality): 假設為了解決一個問題，我們必須作出一系列的決策 D1, D2, …, Dn。若這一系列的決策是最佳解，則針對於前n-k個(或最後n-k個)決策所產生的狀態(子問題)而言，最後的k個(或前k個)決策(1<= k<=n)必定也是最佳的。

* 最長共同子序列(longest common subsequence, LCS or LCSS)演算法
* 最大連續子序列和(maximum contiguous subsequence sum, MCSS)動態規劃演算法
* 背包動態規劃演算法(0/1 knapsack dynamic programming algorithm)
* 多項式及偽多項式時間
* 子集合加總動態規劃演算法
* 矩陣鏈乘積(matrix-chain product)動態規劃演算法
* 最佳二元搜尋樹動態規劃演算法

Problem Set 6:

A. 說明X=ABCBA與Y=BDCA兩個字串藉由動態規劃演算法求出最長共同子序列的過程
B. 如何將「最大連續非空子序列和動態規劃演算法」修改為「最大連續可空子序列和動態規劃演算法」?
C. (編輯成本問題)令兩字串為 A=a1a2...am 與 B=b1b2...bn，我們可以藉由以下三種編輯指令來將A字串轉換成B字串:
1.從A字串中刪除一個字元
2.從A字串中插入一個字元
3.將A字串中的其中一個字元替換成另一個字元
假設上述指令分別花費成本1、2和 3，編寫一個動態規劃演算法求出將字串A轉換為字串B的最小成本。另外，根據這個演算法，寫出最小成本指令過程將字串GTXYT轉換成字串 TXGYCT。
D. 給定一個0/1背包問題如下；背包荷重 W=12，且4個物品其重量各為6、4、5、3，其價值各為20、30、40、10，說明藉由動態規劃演算法解決此0/1背包問題的過程。
E. 以子集合加總動態規劃演算法解決以下子集合加總問題: 給定整數集合S={1, 2, 4, 7}及整數c=10。
F. 藉由動態規劃演算法來替一矩陣鏈(其維度序列為 <5, 20, 10, 12> )加上括號來最佳化矩陣相乘次數。
G. 給定p1=0.2, p2=0.15, p3=0.3; q0=0.1, q1=0.08, q2=0.07, q3=0.1,以最佳二元搜尋樹動態規劃演算法建構出最佳二元搜尋樹。
H. 修改子集合加總動態規劃演算法使其傳回加總值為c的子集合若此子集合存在；否則傳回空集合。

(3/30) TA Class (for Problems A, B, C)
(4/4) No-Class
(4/6) TA Class (for Problems D, E, F, G, H)

期中考: (時間: 4/11 下午2:00-3:50)(範圍: 已授課的部份)(參考講義: book1-8.zip)
7. (4/18) 再探動態規劃演算法(dynamic programming algorithm revisited): (Alg-DP.pptx)
(4/25)
* Bellman-Ford最短路徑演算法
* Floyd-Warshall最短路徑演算法
* Industry 4.0 CPS Gets Big and Deep!?(CPSBig&Deep.zip)
Problem Set 7
A. 畫圖說明利用利用Floyd-Warshall演算法求以下圖(graph)全對最短路徑(all-pair shortest path)距離(成本)(此圖的啟始距離矩陣如下，以經過的中間節點為s, a, b, c, d的順序寫出距離矩陣的改變過程。)
(d->b的加權在圖形與表格中誤植為不一致的值，同學可以將之改為5或6讓圖形與表格一致後解題都算答對。)

B. 求出以下給定圖(graph)的Floyd-Warshall演算法的啟始前節點矩陣(陣列)，並求出最後的前節點矩陣(陣列)。

C. 針對以下的給定圖，列出Bellman-Ford最短路徑演算法執行過程，說明Bellman -Ford最短路徑演算法如何檢查出一給定圖具有負循環(negative-weight cycle)。

8. (5/2) 最小成本最大流量演算法(Minimum-Cost Maximum-Flow Alg., Min-Cost Max-Flow Alg., MCMF Alg.)(MCMF-New.zip)
應用實例 1: Paper: Yung-Liang Lai and Jehn-Ruey Jiang, "Sink-Connected Barrier Coverage Optimization for Wireless Sensor Networks," in Proc. of 2011 International Conference on Wireless and Mobile Communications (ICWMC 2011), 2011. (Slides)
應用實例 2: Paper: Yung-Liang Lai, and Jehn-Ruey Jiang, "Barrier Coverage with Optimized Quality for Wireless Sensor Networks," in Proc. of the 15th International Symposium on Wireless Personal Multimedia Communications Symposium (WPMC'12), 2012. (Slides)
應用實例 3: Jehn-Ruey Jiang, Guan-Yi Sung, and Jih-Wei Wu, "LOM: A Leader Oriented Matchmaking Algorithm for Multiplayer Online Games," in Proc. of International Conference on Internet Studies (NETs 2015), 2015. (Distinguished Paper Award)(LOM.ppt)

*匈牙利演算法(Hungarian Algorithm)(HungarianAlg.zip)(The algorithm will be taught if time is available.)
Problem Set 10:
A. 以以Edmonds-Karp演算法解決以下最大流量問題解決以下最大流量問題(圖的有向邊 (directed edge)上所標示的為容量(capacity))
MaximumFlow

B. 使用匈牙利演算法(Hungarian algorithm)來解以下的指派問題(assignment problem)（註: 必須寫出演算法執行過程中的每個中間結果）

	Task A	Task B	Task C
Tim	$1	$2	$3
Bob	$2	$3	$2
Alex	$2	$2	$3

C. 隨意畫出四個歐氏平面點(2D point)，設其距離皆為整數(以公分計算)，以匈牙利演算法(Hungarian algorithm)找出其最小歐氏平面權重配對(Minimum Euclidean Weighted Matching)。其中所謂最小歐氏平面權重配對問題描述如下: 給定n個點(n為偶數)，如何將此n個點匹配形成n/2個點對，讓每個點對形成一條線段，而此n/2條線段具有最小的長度總和。
D. 將以下最小成本指派問題(assignment problem)轉換(reduce to)為流網(flow network)，以便可以使用最大流(max-flow)演算法解決之。

	Task 1	Task 2	Task 3
Carl	$24	$28	$24
Bob	$26	$32	$28
Alex	$24	$28	$30

9. (5/9) MOOCs (演算法基礎與應用)(Youtube video: https://youtu.be/jon0-ouFtYI)
樹搜尋(tree search)與回溯(backtracking)演算法: (Alg4-1203(NoMark).pptx)(更正: 投影片第36和37頁樹第三層右邊的三個節點由左而右依序為"2' "4' "5") (Youtube video:https://youtu.be/mM93FheJEGQ)
*許多問題的尋找解答過程可以使用樹 (tree)來表達，這類問題也都可以建構出解答空間樹(solution space tree)。因此要找到這些問題的解答，不管是可行解(feasible solution)或是最佳解(optimal solution)，就轉變成一個樹搜尋(tree search)問題。
*有許多方法可以拜訪(visit)與拓展(expand)一個解答空間樹，包括深度優先搜尋(depth-first search, DFS)、廣度優先搜尋(breadth- first search, BFS)、登山搜尋(hill climbing search, HCS)以及最佳優先搜尋(best-first search)等演算法。
.1 廣度優先搜尋(breadth-first search, BFS)演算法
.2 深度優先搜尋(depth-first search, DFS)演算法
.3 登山搜尋法(hill climbing search, HCS)演算法
.4 最佳優先搜尋法(best-first search)演算法
.5 回溯(backtracking)演算法
Problem Set 8:
A. 給定一集合S={7, 4, 1, 2, 11}以及一加總值10，利用深度優先搜尋法來解子集合加總問題，你必須畫出解出問題的解答空間樹(solution space tree)。
B. 以深度優先搜尋演算法找出以下圖(graph)的漢米爾頓迴路 (Hamiltonian circuit)，你必須畫出解出問題的解答空間樹(solution space tree)。

C. 以廣度優先搜尋演算法找出上圖的漢米爾頓迴路，你必須畫出解出問題的解答空間樹(solution space tree)。
D. 以空單格的移動方向為上下左右的次序，以廣度優先搜尋演算法下解決以下的八拼圖(8- puzzle)問題。
起始狀態:

2		3
1	8	4
7	6	5

目標狀態:

1	2	3
8		4
7	6	5

E. 以空單格的移動方向為上下左右的次序，以深度優先搜尋演算法解決D題中的八拼圖(8- puzzle)問題。
F. 以空單格的移動方向為上下左右的次序，以登山搜尋演算法解決D題中的八拼圖(8-puzzle)問題。而評估函數為方塊錯置的數目，若有相同的情形，則以空單格移動方向上下左右為其優先順序。
G. 以空單格的移動方向為上下左右的次序，以最佳優先搜尋演算法解決D題中的八拼圖(8-puzzle)問題。而評估函數為方塊錯置的數目，若有相同的情形，則以空單格移動方向上下左右為其優先順序。

10. (5/16之前觀看影片，5/16小考，5/18繳交習題與實習報告) 分支定界(Branch and Bound)演算法 (Branch&Bound.zip) (Youtube video Part1: https://youtu.be/KUlDxRV6fsU)(Youtube video Part2: https://youtu.be/R91wC81n6Yk)
*分支定界(branch and bound)是一個拜訪與拓展解答空間樹的特殊方法，用於找出問題的最佳解。其做法相當於找出一種方法來切割出解答空間的分支(branch)，然後以上界(upper bound)與下界(lower bound)的概念來加快最佳解的搜尋。
*對於尋找最小成本(minimum cost)解答的最佳化問題而言，分支定界演算法會針對每一分支的解答預測其成本下界(lower bound)，並利用找出可行解來得到問題的成本上界(upper bound)。如果有一個解答的成本下界超過問題成本上界，則這個解不可能是最佳的，因此演算法會中止(terminate)與這個解相關聯的整個分支的搜尋。
*而對於尋找最大利益(maximum benefit)解答的最佳化問題而言，分支定界演算法會針對每一分支的解答預測其利益上界(upper bound)，並利用找出可行解來得到問題的利益下界(lower bound)。如果有一個解答的利益上界低於問題利益下界，則這個解不可能是最佳的，因此演算法會中止(terminate)與這個解相關聯的整個分支的搜尋。
.1 基本概念
.2 分支定界演算法(配合登山搜尋法)解決多階圖最短路徑問題
.3 分支定界演算法(配合最佳優先搜尋法)解決旅行推銷員問題
.4 分支定界演算法(配合最佳優先搜尋法)解決0/1背包問題
.5 一個特殊的分支定界演算法: A*演算法
Problem Set 9: (5/18繳交習題與實習報告)
A. 以分支定界演算法解決以下多階圖最短路徑問題。

B. 給定一0/1背包問題，其背包可載重C=10,且有三物品的重量分別為10, 3, 5，而其利潤分別為40, 20, 30，求出可以放入背包中物品利潤的負值的最小化，使用分支定界演算法來解此0/1背包問題。（註: 必須畫出搜尋樹）(此題使用負的目標函數值，因此feasible solution是求出upper bound，而且我們不斷地嘗試降低upper bound)
C. 同上題，但目標改為求出可以放入背包中物品利潤的最大化，使用分支定界演算法來解此0/1背包問題。（註: 必須畫出搜尋樹）(此題使用正的目標函數值，因此feasible solution是求出lower bound，而且我們不斷地嘗試提高lower bound)
D. 使用A*演算法來解以下之多階圖最短路徑問題。（註: 必須畫出搜尋樹）

E. 將A題的S與T對調，箭頭反向解題。
F. 將B題所有成本乘以2減3解題。
G. 將C題的物品重量改為20, 5, 6解題。
H. 將D題的V0與V8對調，箭頭反向解由V8到V0的最段路徑問題。

11. (5/23) 問題下界與問題分類: P、NP、NP困難與NP完全問題*一個問題的下界為任何能解決此問題的演算法至少所需的時間複雜度。(The lower bound of a problem is the least time complexity required for any algorithm which can be used to solve this problem.) (ProblemLB.zip)
*NP完全問題理論: 若任何一個NP完全問題可在多項式時間被解決，則每一個NP問題皆可在多項式時間獲得解決(也就是P=NP)。 If any one NP-complete problem can be solved in polynomial time, then every problem in NP can also be solved in polynomial time (i.e., P=NP). (Recipe, Cook and Carp)(NPC.zip)
*(NPC理論測驗及解答)
Problem Set 10:
A. 證明支配集問題(dominating set problem)為NP問題。
B. 證明點覆蓋問題(vertex cover problem)為NP問題。
C. 證明集團問題(clique problem)為NP問題。
D. 證明著色問題(chromatic coloring problem)為NP問題。
E. 證明0/1 背包問題(0/1 knapsack problem)為NP問題。
F. 證明3-滿足問題(3-SAT problem)為NP問題。
G. 證明Steiner tree決策問題為NP問題。
(5/30) Dragon Boat Festival (No Class)
12. (6/6)近似演算法 (Approximation algorithms) (ApproximationAlgorithm.zip)

EulerianTour.zip

From Wiki: URL: https://zh.wikipedia.org/wiki/%E4%B8%80%E7%AC%94%E7%94%BB%E9%97%AE%E9%A2%98
定理一
*連通的無向圖G有歐拉路徑的充要條件是： G中奇頂點（連接的邊數量為奇數的頂點）的數目等於0或者2。
*連通的無向圖G是歐拉環（存在歐拉迴路）的充要條件是： G中每個頂點的度都是偶數。

定理二
*一個連通的有向圖可以表示為一條從頂點 u到 v的（不閉合的）歐拉路徑的充要條件是： u的出度（從這個頂點發出的有向邊的數量）比入度（指向這個頂點的有向邊的數量）多1， v的出度比入度少1，而其它頂點的出度和入度都相等。
*一個連通的有向圖是歐拉環（存在歐拉迴路）的充要條件是：每個頂點的出度和入度都相等。

Problem Set 11: