Algorithmics (演算法) 2013

Lecturer: 江振瑞
Teacher Assistant: 葉政峰黃郁誠廖基豪黃信文陳思源陳冠佑
Blackborad System: http://bb.ncu.edu.tw (演算法B)
Time: Tuesday 15:00~17:50
Place: E6 - A2O7
TA Class: ~
Downloads:

JDK: http://java.sun.com/javase/downloads/index.jsp
MinGW C++ Compiler (G++): (http://prdownloads.sf.net/mingw/MinGW-3.0.0-1.exe?download)
Editor for Java/C/C++/C#: Jeep4 (Jeep4Setup.exe)
( data )

TextBook:

Introduction to the Design and Analysis of Algorithms -- A Strategic Approach (2/e), R.C.T. Lee et. al., McGraw Hill, 2005.

Reference Books:

Introduction to Algorithms (2/e), Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, MIT Press, 2001.
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. 認識演算法: (Alg.ppt)(Al-Khwarizmi)(MyBookCh1)(JavaScript 簡介) (9/17)
1.1 演算法名稱的由來
1.2 什麼是演算法?
1.3 演算法的例子
1.4 如何表示演算法?
1.5 如何實作演算法?
1.6 演算法的正確性與效能
Homework1: (你必須至少完成二個題目，若完成二個以上的題目則可以取得額外加分)
(A) 使用流程圖(flow chart)表示歐幾里德GCD演算法 (Use the flow chart to describe the Euclid GCD algorithm.)
(B) 使用虛擬瑪(pseudo code)寫一個演算法，以輸入一個整數n並輸出小於n的最大質數(prime) (Write an algorithm using the pseudo code to input an integer n and output the largest prime less than n.
(C) 使用虛擬瑪(pseudo code)寫一個演算法，以輸入一個整數n並輸出所有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.)
(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的所有完美數(perfect number) (Write an algorithm to input an integer n and output all perfect numbers less than n.
2. 演算法分析: (AnalyzingAlgorithms.ppt)(SortAna.ppt)(AnalyzingAlgorithms(CH).ppt)(SortAna(CH).ppt) (9/24)
2.1 演算法時間複雜度(time complexity)
2.2 大O記號(Big-O Notation)
2.3 量級的比較
2.4 多項式 vs. 指數演算法
2.5 氣泡排序演算法分析
2.6 插入排序演算法分析
2.7 快速排序演算法分析
2.8 合併排序演算法分析
Homework2: (你必須至少完成二個題目，若完成二個以上的題目則可以取得額外加分)
(A) 寫出二元搜尋演算法(binary search algorithm)並分析其最佳、平均與最差狀況時間複雜度(the time complextity in the best case, worst case and average case)
(B) 說明改良的氣泡排序演算法 (improved bubble sort algorithm)的平均狀況時間複雜度為O(n^2)
(C) 說明合併排序演算法(merge sort algorithm)的最佳裝況時間複雜度為O(n log n)
(D) 說明合併排序演算法 (merge sort algorithm)的平均狀況時間複雜度為O(n log n)
(E) 說明合併排序演算法 (merge sort algorithm)的最差狀況時間複雜度為O(n log n)
3. 分割-征服或分而治之(divide-and-conquer)演算法 I: (Divide-Conquer-A.zip) (10/1)

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

3.1 分而治之演算法範例: 解決缺陷棋盤填滿(Tiling a Defective Chessboard)問題
3.2 分而治之二維求秩(2D rank finding)演算法
3.3 分而治之二維求最大點(2D maxima finding)演算法
3.4 分而治之最近二維點對(closest pair of 2D points)演算法
3.5 最長相同連續元素子序列(the longest identical consecutive element subsequence) 問題
3.6 最長單調遞增連續元素子序列(the longest monotonically increasing consecutive element subsequence) 問題
Homework3: (你必須至少完成二個題目，若完成二個以上的題目則可以取得額外加分)
(A) 請展示細節(資料結構及程序)來說明如何利用 presorting改善分而治之二維求秩(2D rank finding)演算法
(B) 寫一個分而治之演算法來解決一個給定的數值集合的求秩(rank finding)問題
(C) 寫一個演算法來找出一群在X軸上的點中的最近點對(closest pair of points on X-axis)
(D) 寫出一個分而治之演算法來解決最長相同連續元素子序列(the longest identical consecutive element subsequence) 問題，並分析演算法的時間複雜度
(E) 寫出一個分而治之演算法來解決最長單調遞增連續元素子序列(the longest monotonically increasing consecutive element subsequence) 問題，並分析演算法的時間複雜度
(Bonus Programming Homework)
(P1) 寫一程式來實作改良式分而治之二維求秩演算法
(P2) 寫一程式來實作分而治之二維求最大點(2D maxima finding)演算法
(P3) 寫一程式來實作分而治之最近二維點對(closest pair of 2D points)演算法

證明歐基里德最小含括樹問題有著下界為Ω(n log n)。

4. 貪婪演算法(greedy algorithm): (Greedy.zip) (10/8)
貪婪演算法(greedy algorithm)一步步地建構出一個問題的完整解答。其每一步都藉由貪婪原則(greed rule)增加一部份的解答到完整解答中。所謂貪婪原則的精神為: 每一次都選擇當下最好的部份解答加入完整解答。
4.1 Kruskal's最小含括樹(minimum spanning tree, MST)演算法
4.2 Prim's最小含括樹(minimum spanning tree, MST)演算法
4.3 霍夫曼編碼(Huffman Code)
4.4 背包問題(Knapsack Problem) (帶出0/1背包問題後可以在第五週講授NP-hard問題)
4.5 Dijkstra最短路徑演算法(Shortest Path Algorithms)
4.6 Bellman-Ford最短路徑演算法(Shortest Path Algorithms) (可視為動態規劃演算法)
4.7 Floyd-Warshall最短路徑演算法(Shortest Path Algorithms) (可視為動態規劃演算法)
Homework4: (你必須至少完成二個題目，若完成二個以上的題目則可以取得額外加分)

A. 寫一個貪婪演算法將一個給定的百元以下金額，以最少的硬幣(50元、10元、5元、1元)來支付。
B. 分別利用Kruskal's演算法與Prim's演算法求出以下圖(graph)的最小生成樹 (minimum spanning tree, MST)

C. 提出一個Dijkstra演算法無法正確執行的圖(graph)。
D. 分別利用Dijkstra演算法及Bellman-Ford演算法求以下圖(graph)頂點1到各頂點的最短路徑(shortest path)距離(成本)

E. 利用Floyd-Warshall演算法求出以上圖(graph)所有頂點對最短路徑(all-pair shortest path)距離(成本)
5. 刪除-搜尋(prune-and-search)演算法: (PruneAndSearch.zip)(10/15)
刪除-搜尋(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，我們可以得到當n趨近於無窮大時，T(n)=O(n^k)。

5.1 二元搜尋(Binary search)演算法
5.2 選取問題(selection problem)與中位數(median)尋找演算法
5.3 一般化的刪除-搜尋演算法時間複雜度
5.4 線性規劃(linear programming)
5.5 一圓心問題(1-center problem)
Homework5: (你必須至少完成二個題目，若完成二個以上的題目則可以取得額外加分)
A. 在解決選取問題的刪除-搜尋演算法中，若每個分割子集改為3個元素，則其最壞狀況時間複雜度是否依然為O(n)。
B. 在解決選取問題的刪除-搜尋演算法中，將每個分割子集改為6個元素後重新分析其時間複雜度。
C. 以刪除-搜尋演算法解決以下限制範圍一圓心問題(constrained 1-center problem): (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(2,0)，圓心在y=0上。(可以精確繪圖說明即可)
D. 以刪除-搜尋演算法解決以下限制範圍一圓心問題(constrained 1-center problem): (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(4,0)，圓心在y=3上。(可以精確繪圖說明即可)
E. 以刪除-搜尋演算法解決以下簡化的雙變量線性規劃問題 (simplified 2-variable linear programming problem): 最大化y，限制條件為y>=x+4, y>=3x+6, y>=2x+8, y>=4x+10, y>=-x+6, y>=-2x+2, y>=-3x+9, y>=-4x+12。(可以精確繪圖說明即可)
6. 動態規劃(dynamic programming)演算法 I: (DynamicP.zip)(10/22)
動態規劃(dynamic programming)演算法籍由將原問題分解成一系列子問題 (subproblems)，並依序解決子問題來解決原問題。為避免一再地解重複的子問題，一旦解出子問題的解答(solution)，即會將其存在表格(或陣列)中。當需要用到某一子問題的解答時，與其重新計算其解答，演算法會取而代之地從表格中直接取出其解答以節省計算時間，是一個「以空間換取時間」的演算法。一個動態規劃演算法會先從最簡單的子問題先解起，並以一定的程序持續運行直至求出原問題解答為止。

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

6.1 基本概念: 最佳解原則(principle of optimality)

6.2 動態規劃 v.s.貪婪演算法

6.3 最長共同子序列(longest common subsequence, LCS or LCSS)問題
6.4 多階圖最小成本路徑(multi-stage graph minimum-cost path)問題

6.5 矩陣鏈乘積(matrix-chain product)問題

Homework6:

(你必須至少完成二個題目，若完成二個以上的題目則可以取得額外加分)

A. 將

動態規劃最長共同子序列(LCS)

演算法改為遞迴呼叫版

演算法

。

B. 寫一個演算法，輸入一個有n個元素的集合S，可以輸出所有S的子集合。
C. 寫一個演算法，輸入二個序列(或陣列)A與B，檢查序列B是否為序列A的子序列，並分析及時間複雜度。
D. 寫一動態規劃演算法來解最長單調遞增子序列問題(the longest monotonically increasing subsequence problem)，並分析演算法的時間複雜度。
E. 藉由動態規劃演算法來替一矩陣鏈(其維度序列為 <5, 20, 8, 60, 10, 12> )加上括號來最佳化矩陣相乘次數。
F. (編輯成本問題)令兩字串為 A=a1a2...am 與 B=b1b2...bn，我們可以藉由以下三種編輯指令來將A字串轉換成B字串:
1.從A字串中刪除一個字元
2.從A字串中插入一個字元
3.將A字串中的其中一個字元替換成另一個字元
假設上述指令分別花費成本3、2和1，編寫一個

動態規劃演算法求出將字串A轉換為字串B的最小成本。另外，根據這個演算法，寫出

最小成本

指令過程將字串GTXYT轉換成字串TXGYCT。
(加分程式設計作業)
(P1)

實作動態規劃最長共同子序列(LCS)演算法，執行之並記錄其執行時間。

(P2)

將

動態規劃最長共同子序列(LCS)

演算法改為遞迴呼叫版，

實作之、執行之並記錄其執行時間。比較

動態規劃版與

遞迴呼叫版

二者執行時間的長短。

(P3) 實作動態規劃演算法解決矩陣鏈乘積(matrix- chain product)問題。

7. 樹搜尋(tree search)與回溯(backtracking)演算法: (TreeSearch&Backtracking.zip) (10/29)
*許多問題的尋找解答過程可以使用樹 (tree)來表達，這類問題也都可以建構出解答空間樹(solution space tree)。因此要找到這些問題的解答，不管是可行解(feasible solution)或是最佳解(optimal solution)，就轉變成一個樹搜尋(tree search)問題。
*有許多方法可以拜訪(visit)與拓展(expand)一個解答空間樹，包括深度優先搜尋法(depth-first search)、廣度優先搜尋法(breadth-first search)、登山搜尋法(hill climbing)以及最佳優先搜尋法(best-first search)等方法。
7.1 廣度優先搜尋法(breadth-first search)
7.2 深度優先搜尋法(depth-first search)
7.3 登山搜尋法(hill climbing)
7.4 最佳優先搜尋法(best-first search)
7.5 回溯演算法(backtracking)演算法
Homework7: (你必須至少完成二個題目，若完成二個以上的題目則可以取得額外加分)
A. 給定一集合S={7, 4, 1, 2, 11}以及一加總值10，利用深度優先搜尋法來解子集合加總問題。
B. 以深度優先搜尋法找出上圖的漢米爾頓迴圈(Hamiltonian circuit)

C. 以廣度優先搜尋法找出上圖的漢米爾頓迴圈(Hamiltonian circuit)
D. 選擇以下策略中的二個來解決下圖中的八拼圖(8-puzzle)問題：廣度優先搜尋法、深度優先搜尋法、登山搜尋法以及最佳優先搜尋法。其中最後兩個方法的評估函數為方塊錯置的數目，若有相同的情形，則以移動方向上左下右為其優先順序。
起始狀態:

2		3
1	8	4
7	6	5

目標狀態:

1	2	3
8		4
7	6	5

(加分程式設計作業)
(P1-P4) 撰寫程式實作上列任何作業

8. 分支定界(Branch and Bound)演算法 (Branch&Bound.zip) (11/5)
*分支定界(branch and bound)是一個拜訪與拓展解答空間樹的特殊方法，用於找出問題的最佳解。其做法相當於找出一種方法來切割出解答空間的分支(branch)，然後以上界(upper bound)與下界(lower bound)的概念來加快最佳解的搜尋。
*對於尋找最小成本(minimum cost)解答的最佳化問題而言，分支定界演算法會針對每一分支的解答預測其成本下界(lower bound)，並利用找出可行解來得到問題的成本上界(upper bound)。如果有一個解答的成本下界超過問題成本上界，則這個解不可能是最佳的，因此演算法會中止(terminate)與這個解相關聯的整個分支的搜尋。
*而對於尋找最大利益(maximum benefit)解答的最佳化問題而言，分支定界演算法會針對每一分支的解答預測其利益上界(upper bound)，並利用找出可行解來得到問題的利益下界(lower bound)。如果有一個解答的利益上界低於問題利益下界，則這個解不可能是最佳的，因此演算法會中止(terminate)與這個解相關聯的整個分支的搜尋。
8.1 基本概念
8.2 分支定界演算法(配合登山搜尋法)解決多階圖最短路徑問題
8.3 分支定界演算法(配合最佳優先搜尋法)解決旅行推銷員問題
8,4 分支定界演算法(配合最佳優先搜尋法)解決0/1背包問題
8.5 一個特殊的分支定界演算法: A*演算法
Homework8: (你必須至少完成二個題目，若完成二個以上的題目則可以取得額外加分)
A. 以分支定界演算法解決以下多階圖最短路徑問題。

B. 使用分支定界演算法解決以下旅行銷售員問題。（註: 必須畫出搜尋樹）

_i ^j	1	2	3	4	5
1	ø	5	61	34	12
2	57	ø	43	20	7
3	39	42	ø	8	21
4	6	50	42	ø	8
5	41	26	10	35	ø

ø 代表無窮大
C. 給定一0/1背包問題，其背包可載重C=10,且有三物品的重量分別為10, 3, 5，而其利潤分別為40, 20, 30，使用分支定界演算法來解此0/1背包問題（註: 必須畫出搜尋樹）
D. 使用A*演算法來解以下之多階圖最短路徑問題。（註: 必須畫出搜尋樹）
MSG2

(加分程式設計作業)
(P1-P4) 撰寫程式實作上列任何作業

9. 期中考 (11/12)
10, 11, 12. 問題下界與問題分類: P、NP、NP困難與NP完全問題 (11/19) (11/26) (12/3) (原定第五週講授)

*一個問題的下界為任何能解決此問題的演算法至少所需的時間複雜度。(

ProblemLB.zip

*NP完全問題理論: 若任何一個NP完全問題可在多項式時間被解決，則每一個NP問題皆可在多項式時間獲得解決(也就是P=NP)。

Recipe, Cook and Carp

NPC-1.zip

NPC-2.zip

NPC理論測驗及解答

Homework9: (11/19: A, D, E任選一題)

Homework10: (11/26: 任選二題: Homework9 B, C 與 Homework10 A, B, C, D)
A. 已知漢米爾頓迴圈(Hamiltonian circuit)決策問題為NPC，證明旅行推銷員(Traveling salesperson)決策問題也是NPC。
B. 設計NP演算法解決0/1背包決策問題。
C. 設計NP演算法解決集合覆蓋(set covering)決策問題。
D. 如何證明P<>NP(P不等於NP)?如何證明P=NP?(需要解釋你的答案)

Homework11: (12/3: 參加CSIT會議，任選一篇論文聽講並撰寫一頁以上之心得報告。報告內容必須包括論文題目，及其摘要) (CSIT議程)

13. 近似演算法 (Approximation algorithms) (ApproximationAlgorithm.ppt) (12/10)
由拉旅途演算法 (Eulerian Tour Algorithm) (EulerianTour.zip)
Homework 12: (12/10: 任選二題)
A. 證明最適裝箱(best-fit bin packing)演算法的近似比例界(approximation ratio bound)為2。
B. 使用2-近似演算法(2-approximation algorithm)來解決以下圖的頂點覆蓋問題(vertex cover problem)。（註: 須描述在執行演算法過程的每個中間結果。）

C. 使用尤拉旅途演算法來找出以下圖的尤拉旅途。（註: 須描述在執行演算法過程的每個中間結果。）

(加分程式設計作業)
P1. 寫一程式來實作尤拉旅途演算法。
(12/17) Part-1 Final Exam. (15%) 15:00-17:50

14. 匈牙利演算法(Hungarian Algorithm)、最大流量最小成本演算法(Maximum-Flow Minimum-Cost Algorithm) (Review.ppt) (HungarianAlgorithm.zip) (MaximumFlow.zip)、應用實例(LOM.ppt) (12/24)
Homework 13: (12/24: 任選二題)
A. 使用匈牙利演算法(Hungarian algorithm)來解以下的指派問題(assignment problem)（註: 必須寫出演算法執行過程中的每個中間結果）

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

B. 自行設計一個指派問題(assignment problem)的4x4成本矩陣，並以匈牙利演算法(Hungarian algorithm)找出最大權重完美二分匹配(Maximum-Weight Perfect Bipartite Matching)。
C. 說明如何使用匈牙利演算法(Hungarian algorithm)解決最小歐氏權重配對(Minimum Euclidean Weighted Matching)問題。
D. 畫圖舉例說明如何將最大二分匹配問題(maximum bipartite problem)變轉為最大流量問題(maximum flow probolem)。(Hint: 參考Cormen et al.'s book Ch 26)
E. 以Edmons-Karp演算法解決以下最大流量問題(圖的有向邊(directed edge)上所標示的為容量(capacity))
MaximumFlow

(加分程式設計作業)
P1. 寫一程式來實作匈牙利演算法(Hungarian Algorithm)以解決問題A。
P2. 寫一程式來實作Edmons-Karp演算法(Hungarian Algorithm)以解決問題E。

15. 分而治之演算法 II (The divide-and-conquer algorithms II): (12/31)
(ComputationGeometry.zip)(ConvexHull.zip)(Voronoi.zip)(Voronoi/Delaunay Applet)
Homework14: (12/31: 任選二題)
A. 說明如何藉由 O(n log n)的預先程序，使得歐幾里德最近鄰居搜尋問題可在 O(log n ) 時間獲得解決? (Show how to achieve Euclidean nearest neighbor searching in O(log n) time with O(n log n) preprocessing?)
B. 給定一個平面點集合(planar point set)及其范諾圖(Voronoi diagram)，寫一演算法求出此點集合的凸包(convex hull)
C. Jarvis's algorithm可以解決給定點集之凸包問題(convex hull problem)，說明為何Jarvis's algorithm是個output-sensitive演算法。說明其最佳狀況時間複雜度為何為O(n)與最差狀況時間複雜度為何為O(n²)。
D. 范諾圖問題的問題下界(the lower bound of the Voronoi diagram problem)為OMEGA(n log n)，這是因為排序問題可變轉為(reduce to)范諾圖問題。說明排序問題如何變轉為(reduce to)范諾圖問題?
E. 下圖顯示兩個凸包的下切線的求取過程，說明此二凸包上切線的求取過程。

F. 給定一個包含n個正或負整數的一維陣列A，以分而治之演算法在O(n log n)時間複雜度求出連續相鄰元素的最大總和。
(加分程式設計作業)
P1. 寫一程式求出給定點的凸包(convex hull)。
P2. 寫一程式求出給定點的范諾圖(Voronoi diagram)。
16. 動態規劃(dynamic programming)演算法 II: (2014/1/07)(DynamicP2.zip)

Homework15: (A與B共二題)

A. 給定一0/1背包問題，其中背包容量W=10，三物品重量分別為10, 3, 5，而物品利潤分別為40, 20, 30，使用動態規劃法來解此0/1背包問題。(你必須列出表格的變化細節)
B. 說明為何0/1背包問題是一個弱NPC問題(weakly NPC problem)。
C.

(加分作業) 寫一個演算法CONSTRUCT-OPTIMAL-BST(root)，可以利用OPTIMAL-BST演算法產生的root表格，輸出如下的最佳二元搜尋樹的完整結構:
k2是根
k1是k2左子
d0是k1左子
d1是k1右子
k5是k2右子
...

D. (加分作業) 子集合加總(subset sum problem)問題是一個弱NPC問題(weakly NPC problem)。寫一個動態規劃演算法解決子集合加總問題。

(加分程式設計作業)
P1. 寫一程式實作動態規劃演算法解決求0/1背包問題(0/1 knapsack problem)。
P2. 寫一程式實作動態規劃演算法解決求子集合加總問題(subset sum problem)。
P3. 寫一程式實作動態規劃演算法解決最佳二元搜尋樹問題(optimal binary search tree problem)。