Lecturer: 江振瑞
Teacher Assistants (TAs): 黃郁誠 廖基豪 黃信文 陳思源 郭正屏 陳昱明 姚克翰 陳彥仲 潘邦睿
LMS System: (演算法B)
Time: (中大資工: 週二 15:00~16:50 週四 10:00-12:00) (福師大資工:  週四 14:00-15:50 週五下午14:00-15:50)
Place: (中大資工: 週二 E6-A2O7 週四 E6-A208) (福師大資工: 資策會教室)
TA Class: 週四 10:00-12:00 (福師大資工:  週五下午14:00-15:50)
TA Page:  http://acan.csie.ncu.edu.tw/alg2014/
Scoring：

• 期中考(分析與設計概念)(20%)
  
• 期末考(分析與設計概念)(25%)
• 報告、課程參與度與每週之程式設計競賽成績(55%)
  

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:  

• 0a. Google開放edX平台磨課師課程: (Course on Google edX MOOCs platform): https://courses.openedx.tw/courses/NCUx/MO0001/201409/about# (online: December 1, 2014)
• 0b. 實習課助教網頁:  http://acan.csie.ncu.edu.tw/alg2014/
  
• 0c. 安裝課程相關軟體: Jeep5 (建議直接使用本網站區域下載軟體)
0.1 安裝Java Development Kit (JDK): http://java.sun.com/javase/downloads/index.jsp (區 域下載: jdk-8u11-windows-x64.exe)
0.2 安裝MinGW C++ Compiler (G++): http://prdownloads.sf.net/mingw/MinGW-3.0.0-1.exe?download (區域下載: mingw-3.0.0-1.exe)
0.3 安裝最新Python 2 Interpreter: https://www.python.org/downloads/ (區域下載: python-2.7.8.msi)
0.4 安裝Jeep5(Java editor for Chinese programmers v5.0) (區域下載: SetupJeep5.exe)
0.5 設定路徑參數: 注意，這會因為你安裝上列不同軟體的不同版本而不同，也會因為你安裝的作業系統版本不同而不同。以下為針對Win7 64位元作業系統，安裝由本網站區域下載軟體的設定:

選擇 [控制台][系統及安全性][系統][進階系統設定][環境變數]，找出[path]變數並按下[編輯]，以在其變數值末端加入:
;C:\Program Files\Java\jdk1.8.0_11\bin;C:\MinGW\bin;C:\Python27;C:\Jeep5
(也就是加入 ;JDK安裝目錄\bin;MinGW安裝目錄\bin;Python2安裝目錄;Jeep5安裝目錄)
0.6 下載範例程式(Sample.c)(Sample.cpp)(Sample.java)(Sample.py)儲存於C:\Jeep5目錄中，按下桌面Jeep5按鈕執行Jeep5軟體，並使用 [開舊檔]選項載入範例程式進行[編譯][執行]。


• 0d. ACM國際大學生程式設計競賽 (ACM International Collegiate Programming Contest, ACM-ICPC) (ACM-ICPC(Org).ppt)

• The Universidad de Valladolid (UVa) judge: http://online-judge.uva.es
  Example: http://online-judge.uva.es/p/v100/10041.html (Vito's Family) (Vito.java) (Vito1.java) (Vito.cpp)
  Exercise: http://online-judge.uva.es/p/v102/10258.html (Contest Scoreboard)
  Exercise: http://online-judge.uva.es/p/v5/531.html (Compromise)

• 1. 認識演算法 -- 從食譜到高階程式語言: (Alg1(Org).ppt)(Alg1(Org).pdf)(book1-2.3+AB.pdf)
1.1 演算法名稱的由來
1.2 什麼是演算法?
1.3 演算法的例子
1.4 如何表示演算法?
1.5 如何實作演算法? (EuclidGCD.c)(EuclidGCD.cpp)(EucidCGDClass1.java)(EucidCGDClass.java)(EuclidGCD.py)
1.6 演算法的正確性與效能
1.7 演算法的時間複雜度
1.8 大 O 趨近記號
1.9 降低演算法時間複雜度量級
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. 演算法複雜度分析範例(以排序演算法為例)
  2.1 氣泡排序(bubble sort)演算法 (Alg2 (Org).ppt)(Alg2 (Org).pdf)
  2.2 插入排序(insertion sort)演算法
  2.3 合併排序(merge sort)演算法 (屬分治演算法)
  2.4 快速排序(quick sort)演算法 (屬分治演算法)
  Homework2: (任選二題)
  (A) 使用虛擬碼描述堆積排序(heap sort)演算法
  (B) 分析堆積排序演算法時間空間複雜度
  (C) 使用虛擬碼描述基數(radix sort)演算法
  (D) 分析基數排序演算法時間空間複雜度
  
  
• 3. 分治(divide-and-conquer)演算法: (Alg2 (Org).ppt)(Alg2 (Org).pdf)
  
  若是問題 規模(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)演算法
  Homework3: (任選二題)
  (A) 寫一個分治演算法來解決一 個給定的數值集合的求秩(rank finding)問題，並進行複雜度分析。
  (B) 寫一個分治演算法來找出一群在X軸上的點中的最近點對(closest pair of points on X-axis)，並進行複雜度分析。
  (C) 寫出一個分治演算法來解決最長單調遞增 連續元素 子序列(the longest monotonically increasing consecutive element subsequence) 問題，並分析演算法的時間複雜度，並進行複雜度分析。
  (D) 給定一 個包含n個正或負整數的一維陣列A，以分治演算法在O(n log n)時間複雜度求出連續相鄰元素的最大總和。你必須進行複雜度分析以驗證你的結果。

• 4. 刪尋(prune-and-search)演算法: (Alg2 (Org).ppt)(Alg2 (Org).pdf)
  刪尋(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)演算法
  4.4 簡化的二變數線性規劃(simplified 2-variable linear programming)演算法
   
  Homework4: (任選二題)
  (A) 在選取刪尋演算法中，若每個分割子集改為3個元素，則其最壞狀況時間複雜度是否依然為O(n)，為什麼?
  (B) 在選取刪尋演算法中，將每個分割子集改為6個元素後重新分析其時間複雜度。
  (C) 以刪尋演算法解決以下限制的一圓心問題: (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(2,0)，圓心在y=0上。(可以精確繪圖說明即可)
  (D) 以刪尋演算法解決以下限制的一圓心問題: (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(4,0)，圓心在y=3上。(可以精確繪圖說明即可)
  (E) 以刪尋演算法解決以下簡化的雙變量線性規劃問題: 最大化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。(可以精確繪圖說明即可)
  

• 5. 貪婪演算法(greedy algorithm): (Alg3 (Org).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最短路徑演算法
  Homework5: (任選二題)
  
  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(7%)、C (18%)、D (33%)。(備註:括號中為字元出現頻率)
  D. 利用Dijkstra演算法求以下圖(graph)頂點4到各頂點的最短路徑(shortest path)距離(成本)
  
  
• 6. 動態規劃(dynamic programming)演算法: (Alg3 (Org).pptx)
  動態規劃(dynamic programming)演算法籍由將原問題分解成一系列子問題 (subproblems)，並依序解決子問題來解決原問題。為避免一再地解重複的子問 題，一旦解出子問題的解答(solution)，即會將其存在表格(或陣列)中。當需要用到某一子問題的解答時，與其重新計算其解答，演算法會取而代之地 從表格中直接取出其解答以節省計算時間，是一個「以空間換取時間」的演算法。一個動態規劃演算法會先從最簡單的子問題先解起，並以一定的程序持續運行直至 求出原問題解答為止。
最佳解原則(Principle of optimality): 假設為了解決一個問題，我們必須作出一系列的決策 D1, D2, …, Dn。若這一系列的決策是最佳解，則針對於前n-k個(或最後n-k個)決策所產生的狀態(子問題)而言，最後的k個(或前k個)決策(1<= k<=n)必定也是最佳的。
6.1 Bellman-Ford最短路徑演算法
6.2 Floyd-Warshall最短路徑演算法
6.3 多階圖最小成本路徑(multi-stage graph minimum-cost path)演算法
6.4 最長共同子序列(longest common subsequence, LCS or LCSS)演算法
6.5 矩陣鏈乘積(matrix-chain product)演算法
Homework6: (任選二題)
A. 利用Floyd-Warshall演算法求以下圖(graph)全對最短路徑(all-pair shortest path)距離(成本)(此圖的啟始距離矩陣如下，以經過的中間節點為s, a, b, c, d的順序寫出距離矩陣的改變過程。)

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

C. 以下是Floyd-Warshall演算法針對具有五個節點(記為1、2、3、4、5)的圖產生的前節點矩陣(陣列)，說明如何藉以找出節點1到節點3的 最短路徑，及節點5到節點2的最短路徑。

• 演講: Software Defined Networking and Dijkstra's Algorithm (SDN&Dijkstra2014-1105.pptx)
  Title: This talk introduces the SDN (Software Defined Networking) concept and its development and applications. The talk also includes the topic of extending Dijkstra’s shortest path algorithm to achieve the optimal routing for SDN by considering not only edge weights but also node weights. How to implement the extended Dijkstra’s algorithm with Pyretic, a Python-based language for developing SDN applications, is also elaborated. Finally, simulation results of the algorithm using the Mininet and the Iperf tools on the Abilene topology are described.
  
• 期中考: (時間: 2014/11/11 下午3:00-4:50) (地點: 工程五館 資工系 A207 教室) (範圍: 0-6項目中已授課的部份，含演講的內容)(交卷時分不同班別分開交) (Alg3(NoMark)2014-1106.pptx)
  
• 6-1. 動態規劃演算法(以MOOCs的方式學習)(程式設計比賽正常舉行) (11/22-11/28) (Alg3(NoMark)2014-1106.pptx) (11/27與11/28舉行程式設計比賽)
  6.1a Bellman-Ford最短路徑演算法
  6.2b Floyd-Warshall最短路徑演算法
  6.3c 0/1背包動態規劃演算法
  Homework6: (任選二題尚未做過的題目)
  
• 7. 樹搜尋(tree search)與回溯(backtracking)演算法: (Alg4-1203(NoMark).pptx)(更正: 投影片第36和37頁 樹第三層右邊的三個節點由左而右依序為"2' "4' "5")(11/18, 11/20上課)(11/20與11/21無程式設計比賽)
  *許多問題的尋找解答過程可以使用樹 (tree)來表達，這類問題也都可以建構 出解答空間樹(solution space tree)。因此要找到這些問題的解答，不管是可行解(feasible solution)或是最佳解(optimal solution)，就轉變成一個樹搜尋(tree search)問題。
  *有許多方法可以拜訪(visit)與拓展(expand)一個解答 空間樹，包括深度優先搜尋(depth-first search)、廣度優先搜尋(width-first search)、登山搜尋(hill climbing search)以及最佳優先搜尋(best-first search)等演算法。
  7.1 廣度優先搜尋(width-first search)演算法
  7.2 深度優先搜尋(depth-first search)演算法
  7.3 登山搜尋法(hill climbing search)演算法
  7.4 最佳優先搜尋法(best-first search)演算法
  7.5 回溯(backtracking)演算法
  Homework7: (任選二題)
  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)問題。而評估函數為方塊錯置的數目，若有相同的情形，則以空單格移動方向上下左右為其優先順序。
  
• 8. 分支定界(Branch and Bound)演算法 (Branch&Bound.zip)
  *分支定界(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*演算法來解以下之多階圖最短路徑問題。（註: 必須畫出搜尋樹）
  
  
  
• 英文演講
  時間: 12/15(星期一)10:00-12:00
  地點: A207
  講題: 1. 5G Mobile Communication : Evolution towards Networked Society 2. MIMO and Beamforming which enable 5G Mobile Communication
  Homework9: 手寫作業(1-2頁): 因應4G、5G高速、寬頻、高覆蓋率的特殊新應用 (評分依據為創新性與可行性)
  星期四與星期五的上機比賽題目為綜合性題目，題目較簡單但是較多，涵蓋所有演算法12/12以前之課程內容
  
• 10, 11 問題下界與問題分類: 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理論測驗及解答)
Homework10: (任選二題)
A. 說明在n個數值中找出第二大的數至少需要(n-2+⌊log⁡ n⌋)的比較次數。
B. 證明二元搜尋演算法對於只考慮比較的搜尋演算法是最佳的。
C. 證明歐基里德最小含括樹( Euclidean minimal spanning tree problem)問題的問題下界為Ω(n log n)。
Homework11: (任選二題)
A. 如何證明一個問題是NP-hard?
B. 設計NP演算法解決集合覆蓋(set covering)決策問題。
C. 以下為分割問題(partition problem)的描述：給定一個正整數集合S，是否存在一種分割將S分割為S1與S2集合，且S1集合的元素加總值與S2相同？證明此分割問題為一NP 問題。
D. 已知漢米爾頓迴路(Hamiltonian circuit)決策問題為NPC，證明旅行推銷員(Traveling salesperson)決策問題也是NPC。
E. 如何可以證明P<>NP(P不等於NP)?如何可以證明P=NP?(需要解釋你的答案)
• 12. 近似演算法 (Approximation algorithms) (ApproximationAlgorithm.ppt)
  尤拉旅途演算法 (Eulerian Tour Algorithm) (EulerianTour.zip)
  Homework 12: (任選二題)
  A. 證明最適裝箱(best-fit bin packing)演算法的近似比例界(approximation ratio bound)為2。
  B. 使用2-近似演算法(2-approximation algorithm)來解決以下圖的頂點覆蓋問題(vertex cover problem)。（註: 須描述在執行演算法過程的每個中間結果。）
  
  C. 使用尤拉旅途演算法來找出以下圖的尤拉旅途。（註: 須描述在執行演算法過程的每個中間結果。）