Teaching Assistants (TAs): 陳思翰 朱俊瑋 林彥廷 陳祐麟
Time: 週二 14:00~16:50
Place: 週二 教研大樓 TR A203
TA Class: 週二 13:00~13:50 (教研大樓 TR A203)
Video List: Link
請大家先觀看去年的課程介紹影片: https://youtu.be/pLTIKYN2DUg
*加選請慎思，因為每週手寫作業6-10題，任選二題作答；每週線 上程式作業3題，至少完成一題；每週助教課程分組報告一小時，需上傳作業解題投影片。
*建議可以採用先看習題，然後再到影片中學會解決問題技術的方式學習，效果較佳!
Scope:
- Many Classical Algorithms
- Several Machine Learning/Deep Learning Algorithms
- Few Quantum Algorithms (2021新增)
- 期中考(分析與設計概念)(25%)
- 期末考(分析與設計概念)(30%)
- 程式設計作業、報告、課程參與度及程式設計競賽成績(45%)
- 6/15-6/22
Final Examination
(時間: 6/15 20:00-6/22 12:00)
選擇5個演算法中至少2個進行實作上傳至Online Judge(佔總分14%)，其中1個演算法需要撰寫報告，詳細說明演算法每個步驟的實作過程，書面報告以docx或pdf檔案格式繳交(佔總分 8%)。實作的演算法於6/15晚上20:00公告，程式上傳與報告繳交截止期限皆為6/22中午12:00。 - My Book's Manuscript -- New Quantum Algorithm Chapter: AlgBook-2021-0617.zip (updated 2021/06/17)(06/17考量勘誤項目；06/15新增 Quantum Algorithm內容)(此新章節內容 勘誤加分持續中...， 列舉勘誤請列本版本日期及頁碼並請先查清是否已有他人列舉過。:)
- Term Report (佔總分 8%): Due Day: 06/29
20:00:
請看完上列教科書中有關量子演算法的新章節，針對以下主題之一(選A或B，多寫不加分)撰寫3-5頁的期末報告，若 有引述要標註並註明出處，以免被認定為報告抄襲 :
A. 量子程式語言(選擇以下語言之一，如QVM、QCL、Q#、Q|SI>、Q language、qGCL、QMASM、Scaffold、Silq、LIQUi|>、Quipper、funQ或其他語言)
B. 量子計算於不同領域之應用(選擇以下應用之一，如網路安全、藥物開發、金融建模、交通最佳化、天氣預報、氣候變遷、量子機器學習或其他應用)
- Term Project Due Day: 06/29 20:00
- My Book's Manuscript: AlgBook-2021-0426.zip (updated 2021/04/26)(第8章之後還在編修中，請先不要進行勘誤)(04/26 主要新增第8章結語與修正第8章部份錯誤)(04/20 主要包含所有勘誤修正以及修改活動選擇演算法及其時間複雜度分析)(04/15 主要修正第k小元素(中位數)selection alg.錯誤， 修改heap sort alg.說明及Huffman coding alg.與Dijkstra alg.有關使用heap-based priority queue的說明；04/13修改書名，增加第0章，共有0~14章含3附錄， 章名加 註**代表尚在編輯中)(教科書勘誤加分持續中...， 列舉勘誤請列版本日期及頁碼並請先查清是否已有他人列舉過。:)
- R.C.T. Lee et. al., Introduction to the Design and Analysis of Algorithms -- A Strategic Approach (2/e), McGraw Hill, 2005.
- Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, Introduction to Algorithms (3/e), MIT Press, 2009.
- 張元翔, 量子電腦與量子計算, 碁峰, 2020.
- 陳建宏(譯), 量子計算實戰, 碁峰, 2020.
- 林大貴, TensorFlow + Keras 深度學習人工智慧實務應用, 博碩文化, 2017.
- 齊藤康毅, Deep Learning -- 用Python進行深度學習的基礎理論實作, O'REILLY, (吳嘉芳
譯, 碁峰資訊出版), 2017.
- 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.
2 安裝MinGW C++ Compiler (G++): http://prdownloads.sf.net/mingw/MinGW-3.0.0-1.exe?download
3 安裝最新Python 3 Interpreter: https://www.anaconda.com/
4 安裝Jeep7(Java editor for every programmers v7.0) (下載: Jeep7Setup&SourceCode.exe) (防毒軟體會誤判為不安全軟體，但保證安全，請安心使用。)
5 設定路徑參數: 注意，這會因為你安裝上列不同軟體的不同版本而不同，也會因為你安裝的作業系統版本不同而不同。以下為針對Windows作業系統的設定:
選擇 [控制台][系統及安全性][系統][進階系統設定][環境變數]，找出[path]變數並按下[編輯]，並在其變數值末端加入以下內容:
;JDK安裝目 錄\bin;MinGW安裝目錄\ bin;Python安裝目錄;Jeep7安裝目錄
(例如: ;C:\Program Files\Java\jdk-9.0.4\bin;C:\MinGW\bin;C:\Users\yourname\Anaconda3;C:\Jeep7)
6 下載範例程式(Sample.c)(Sample.cpp)(Sample.java)(Sample.py)儲 存於C:\Jeep7目錄中，按下桌面Jeep7圖示執行Jeep7軟體，並使用 [開舊檔]選項載入範例程式進行[編譯][執行]。
- 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. 認識演算法 -- 從食譜到高階程式語言: (AlgSmallTalk.pptx) (Alg-Intro.pptx) (CPSforIndustry4.0.zip) (ACM-ICPC&EPC.ppt)(CPSProject.zip)(3/2) 1. 演算法名稱的由來
2. 什麼是演算法?
3. 演算法的例子
4. 如何表示演算法?
5. 如何實作演算法? (EuclidGCD.c)(EuclidGCD.cpp)(EucidCGDClass1.java)(EucidCGDClass.java)(EuclidGCD.py)
6. 演算法的正確性
Homework1: (for 3/2; Due day: before next class or TA's class)
(A)使用虛擬瑪(pseudo code)寫一個演算法，輸入一個整數n(n>2)並並判斷n是否為質數(prime)(Write an algorithm using the pseudo code to input an integer n and output (decide) if n is a prime.)
(B) 使用虛擬 瑪(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.)
(C) 使用虛擬 瑪(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.)
(D) 使用虛擬瑪(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.)
(E) 使用虛擬瑪(pseudo code)寫一個演算法，輸入一個整數n(n>2)並判斷n是否為完美數(perfect number)。一個完美數是一個正整數，它所有的真因數(即除了自身以外的因數)的和，恰好等於它本身。 (Write an algorithm using the pseudo code to input an integer n and output (decide) if n is a perfect number. Note that a perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself.)
(F) 使用虛擬瑪(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 → 22+82= 68 → 62+82=100 → 12+02+02=1，因此28是快樂數
- 2. 演算法複雜度分析範例(以排序演算法為例)(Alg-Analysis.pptx)(3/9)
.1 演算法的效能
.2 演算法的時間複雜度
.3 大O漸進記號
.4 降低演算法時間複雜度量級
.5 漸進記號(asymptotical notation): Big O, Big Omega, Theta
.6 多項式時間、指數時間及偽多項式時間演算法
.7 氣泡排序(bubble sort)演算法
.8 插入排序(insertion sort)演算法
Homework 2: (for 3/9; Due day: before next class or TA's class)
(A) 在氣泡排序(bubble sort)演算法中，若在某回合中完全沒有任何資料對調，則可推論資料已經排序完成而立即結束演算法執行，這稱為改良氣泡排序(improved bubble sort)演算法。請以虛擬碼描述「改 良氣泡排序演算法」。(請注意:在有些文獻中，所謂 「氣泡排序演算法」其實指的是「改良氣泡排序演算 法」)
(B) 分析改良氣泡排序演算法最佳、最差與平均時間複雜度
(C) 使用虛擬瑪(pseudo code)寫一個時間複雜度為O(sqrt(n))的演算法，輸入一個整數n(n>2)並輸出所有n除了本身以外的正因數 (factor)總和，你必須分析演算法的時間複雜度。
(D) 使用虛擬瑪(pseudo code)寫一個時間複雜度為O(sqrt(n))的演算法，輸入整數n及m(n>m>2)，輸出所有比n小並大於 m的n的因數 (factor)總和，若無此因數則輸出0，分析演算法的時 間與空間複雜度。
(E) 使用虛擬瑪(pseudo code)寫一個時間複雜度為O(sqrt(n))的演算法，輸入一個整數(n>2)並判斷n是否為完美數 (perfect number)，你必須分析演算法的最差及最佳時間複雜度。
(F) 使用虛擬瑪(pseudo code)寫一個演算法，以輸入一個具有n個元素的集合S並輸出S的幂集(pwoer set)，你必須分析演算法的時間複雜度。 (Write an algorithm to input a set S of n elements and output the power set of S. You must analyze the time complexity of your algorithm.)
(G) 分析費伯納西數列演算法與遞迴費伯納西數列演算法之空間 複雜度
**(H) 使 用虛擬碼寫出堆積排序(heap sort)演算法，分析其時間與空間複雜度 (heap sort不列入考試範圍， 但是以下列入考試範圍: 以binary heap實作的priority queue的operations，包括 insert(p): Inserts a new element with priority p; extractMax(): Extracts an element with maximum priority; remove(i): Removes an element pointed by an iterator i; changePriority(i, p): Changes the priority of an element pointed by i to p; 都具有O(log n)的time complexity；而getMax(): Returns an element with maximum priority; 則具有O(1) time complexity。)
(I) 畫出n log n、n log2 n、n2及n3圖 形(for n=2, 4, 8, ..., 128)並比較之。(新增)
(J) 若一演算法A的時間複雜度為6 x 2n=O(2n)可以在n=10的時候耗費一小時解決問題 X，而另一個解決問題X的演算法B的時間複雜度為5 x n3 = O(n3)， 則請問當n=10時演 算法B要耗費多少時間完成?(新增)
(H) 若一演算法A的時間複雜 度為6 x 2n=O(2n)可 以在n=10的時候耗費一小時解決問題X，而另一個解決問 題X的演算法B的時間 複雜度為5 x n3 =O(n3)，則請問當n為 何值時演算法B要耗費一小時才可以完 成?(新增)
- 3.
分治(divide-and-conquer)演算法: (Alg-Divide&Conquer.pptx)(3/16)
若是問題 規模(problem size)夠小， 就直接解決之；反之，若問題規模較大，就將其分割(divide)成兩個或多個子問題(分割階段)，然後將每個子問題遞迴地 (recursively)征 服(conquer)解決之(征服階段)。之後再將每個子 問題的解答合併(merge)，使其成為原問題的解答(合併階段)。.5 最大連續子序列和(Maximum Contiguous Subsequence Sum, MCSS)演算法
.1 分治演算法簡介
.2 分治缺陷棋盤填滿(tiling a defective chessboard)演算法
.3 合併排序(merge sort)演算法 (屬分治演算法)
.4 快速排序(quick sort)演算法 (屬分治演算法)
Homework 3: (本週的3A-3F任選一題，加上上週的2A,2B, 2I,2J, 2H任選一題)
A. 分析合併排序演算法中將兩個元素依序由小而大排列的子陣列L與R合併為元素依序由小而大排列的陣列A的時間 複雜度為O(n)，其中|L|=|R|=n/2, |A|=n。
B. 分析快速排序演算法最佳狀況空間複雜度(best case space complexity)。
C. 分析快速排序演算法最差狀況空間複雜度(worst case space complexity)。
D. 舉出兩個方法讓快速 排序(quick sort)演算法避免產生最壞狀況。
E. 給定一個序列S=(-2, 1, -3, 4, -1, 2, 1, -5, 4)，仿照merge sort的執行過程畫圖 說明使用分治最大非空連續 子序列和演算法求出最大非空連 續子序列和的過程。
F. 給定一個序列S=(-2, -1, -3, -4, -1, -2, -1, -5)，仿照merge sort的執行過程畫 圖說明使用分治最 大可空連續子序列和演算法求出最大可 空連 續子序列和的過程。
- 4. 分治演算法(2): (Alg-Divide&Conquer.pptx後
半段)(FFT.zip)
(3/23)
.1 分治快速傅立葉變換(fast Fourier transform, FFT)演算法
.2 分治二維求 秩(2D rank finding)演算法
.3 分治二維極大點(2D maxima finding)演算法
.4 分治二 維最近點對(2D closest pair of points)演算法
Homework 4: (每位學生都要撰寫2題: A題為必選題，B, C, D, E, F或G中 則任選一題)
A. 舉例說明一個快速傅立葉變換的應用。
B. 寫一個分治演算法來解決一個給定數值集合 的求秩(rank finding)問題，並進行複雜度分析。
C. 寫一個分治演算法來找出一群在X軸上的點中的最近點對(closest pair of points on X-axis)，並進行複雜度 分析。
D. 給定8個二維平面點: (1, 4), (2, 2), (3, 5), (4, 8), (5, 6), (6, 3), (7, 9), (8, 7)，畫圖說明使用分治二維極大點演算法求出所有極大點(maxima)的過程。
E. 給定8個二維平面點: (1, 4), (2, 2), (3, 5), (4, 8), (5, 6), (6, 3), (7, 9), (8, 7)，畫圖說明使用分治二維求秩演算法求出每個點的秩(rank)的過程。
F. 給定8個二維平面點: (1, 4), (2, 2), (3, 5), (4, 8), (5, 6), (6, 3), (7, 9), (8, 7)，畫圖說明使用分治二維最近點對演算法求出最近點對距離的過程。
G. 說明如何使用預先排序(pre-sorting)於分治最近二維點對 (closest pair of 2D points)演算法。
4.5 凸包(Convex Hull)演算法: (ConvexHull.zip) (3/30)
5. 刪尋(prune-and-search)演算法: (Alg-Prune&Search.pptx) (3/30)
刪尋(prune-and-search)演算法包含多次迭代 (iteration)，在每一次的迭代中，均刪除(prune)輸入資料的一部分(假設為f部份, 0<f<1)，而後再遞迴地(recursively)以相同的演算法在剩餘的資料中搜尋(search)出解答。 在經過一定次數的迭代後， 輸入資料的規模將會變得相當小，而能在常數時間內直接找出解答。
假設一個刪除-搜尋演算法的時間複雜度為T(n)，並且每次迭 代所需的時間 為O(nk)(k為大於0的常數)，則T(n)=T((1-f)n)+O(nk)。由於 1-f<1，我們可得T(n)=O(nk)。
.1 刪尋(prune-and-search)演算法概念介紹
.2 二元搜尋(binary search)演算法
.3 選取(selection)與中位數(median)演算法
.4 限制的一圓心 (constrained 1-center)演算法
Homework 5:
(A) 舉一個8個元素的陣列為例說明二元搜尋演算法執行情形，分別說明最佳狀況時間複雜度找到目 標元素、最壞狀況時間複雜度找到目標元素及最壞狀況時間複雜度找不到目標元素。
(B) 在選取刪尋演算法中，若每個分割子集改為3個元素，則其最壞狀況時間複雜度是否依然為 O(n)，為什麼?
(C) 在選取刪尋演算法中，將每個分割子集改為6個元素後重新分析其時間複雜度。
(D) 有一個刪尋演算法其時間複雜度為 T(n)=T((7/8)n)+cn2， 詳細分析其時間複雜度並以大O記號表示。
(E) 以刪尋演算法解決以下限制的一圓心問題: (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(2,0)，圓心在y=0上。(可 以精確繪圖說明即可)
(F) 以刪尋演算法解決以下限制的一圓心問題: (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(4,0)，圓心在y=3上。(可 以精確繪圖說明即可)
-
韓非 (約西元前 281
生，西元前 233 年卒) 是戰國末期的
思想家，是中國古代法家思想的代表人物。戰國時期，齊、楚、燕、韓、趙、魏、秦七雄並立。蘇秦曾提出南北合縱六國以抗秦的戰略思
想，使秦國
十五年無法向西出兵攻擊位於其東邊且南北合縱的六國。但是後來張儀以東西連橫的外交策略，遊說各國由合縱抗秦轉變為連橫親秦，而 讓秦國得以遠交近攻，逐漸併吞六國。
韓非在《韓非子·存韓》篇中提到:「諸侯可蠶食而盡」，意思是說秦國可化整為零，也就是將一個整體合縱抗秦的六國化分成許 多零散部份，然後像蠶吃桑葉那樣，一點一點的逐步侵佔滅亡六國，而達成一統
天下的目的。
本單元所介紹的演算法，包括二元搜尋演算法、選取與中位數演算法及限制的一圓心演算法，都採用刪尋解題策略解決問題。這個策略就 是類似「化整為零，蠶食而盡」的概念。刪尋演算法包含許多的迭代，
每次迭代都嘗試刪除固定比例的輸入資料，而後再遞迴地從剩餘資料中搜尋出解答，若仍然無法找出解答則再刪除固定比例的輸入資料。 這樣經過幾次迭代後，輸入資料的規模將會小到足以讓問題在常數時間內
直接解決，因而得到問題的解答。一般而言，整個刪尋演算法的時間複雜度與每個迭代的時間複雜度具有相同的量級，因此刪尋演算是一 個有效率的演算法。
- Term Project 說明與教學 (3/30)
(請同學務必把握時間觀看由助教錄製的Term
Project教學影片，儘早完成機器學習/深度學習環境安裝，並開始撰寫程式以完成Term Project)
題目: 深度學習中文手寫數字辨識
輸入: 中文手寫數字資料集(dataset)
輸出: 中文手寫數字辨識準確率(accuracy)
佔分: 總成績20%
目的: 讓學生練習使用深度學習(deep learning)模型解決中文手寫數字辨識問題。深度學習(deep learning)模型可為深度神經網路(deep neural network, DNN)、捲積神經網路(convolutional neural network, CNN)、長短期記憶(long short-term memory, LSTM)神經網路或閘控遞迴單元(gated recurrent unit, GRU)神經網路。
資料集說明: (資料集下載連結)
資料集檔案handwrite_detect.zip為中文手寫數字資料集，包含了訓練資料集(training dataset)與測試資料集(test dataset)
訓練資料共有2450筆
測試資料共有1700筆
評分項目與規範:
Source code(.py)
A short report (.pdf) (含有)
中文手寫辨識準確率(accuracy)，以截圖方式呈現
Source code之逐行解釋
繳交方式: 請將所有檔案壓縮成 .zip 後，再上傳至 e-class 作業繳交區
(上傳檔名:Term_Project_學號_姓名.zip)
繳交時間: 期末考周之下一周二 20:00前截止
備註 : 切勿互相抄襲，若發現抄襲，則以0分計算
投影片: https://drive.google.com/drive/folders/1OiRiTyf5xMbHxlUEg2LUbXT9Z9GqgLZu?usp=sharing
教學影片:
演算法課程_機 器學習環境安裝之教學影片 - 6. 貪婪演算法(greedy algorithm):
(Alg-Greedy.pptx) (4/13)
貪婪演算法(greedy algorithm)一步步地建構出一個問題的完整解答。其每一步都藉由貪婪解題策略(greed strategy)增加一部份的解答到完整解答中。所謂貪婪解題策略為: 每一次都選擇當下最好的部份解答加入完整解答中。
.1 背包演算法(knapsack algorithm) (帶出0/1背包問題後可以在之後講授NP-hard問題)
.2 活動選擇(activity selection)演算法
.3 Huffman編碼(Huffman coding)演算法
.4 Kruskal最小生成樹(minimum spanning tree, MST)演算法
.5 Prim最小生成樹(minimum spanning tree, MST)演算法
.6 Dijkstra演算法
Homework 6:
(A) 一個背包容量為 10，現在有5個物品， 重量分別為4、3、6、2、5，價格分別為10、9、 12、4、8，求背包能夠裝入零碎(fractional)物品的最大價值為何?
(B) 給定 5 個活動，其活動區間分別為 [0,18), [3, 5), [4, 16), [2, 9), [10, 15)，請描述如何以活動選擇演算法找出最多的相容活動總數m(必須寫出m的數值)。
(C) 利用Huffman 編 碼演算法替以下字元編碼A(46%)、 B(7%)、C (28%)、D (19%)。(備註:括號中為字元出現頻率)
(D) 利用Kruskal演算法求出以下的圖(graph)的最小生成樹 (minimum spanning tree, MST)
(E) 利用Prim演算法求出以上的圖(graph)的最小生成樹 (minimum spanning tree, MST)
(F). 利用Dijkstra演算法求以下圖(graph)頂點4到各頂點的最短路徑(shortest path)及其距離(成本)。註: 需要寫出每次迭代每個節點之最 短路徑更新的過程。
(G). 承上題，利用Dijkstra演算法求頂點1到各頂點的最短路徑(shortest path)及其距離(成本)。註: 需要寫出每次迭代每個節點之最 短路徑更新的過程。
- 期中考: (時 間: 4/20 下 午2:00-3:50)(範圍: 已授課的部份:教科書第0章到第7章，加第9章Dijkstra alg.)(地點: 請TA另行公佈按照座位表入座，應試請戴口罩)(投影片更新較慢，因此標準答案以此版教科書為準: AlgBook-2021-0415.zip ) (教科書勘誤加分持續中...)
- 公告:
5/12(星期三)14:00-15:50 量子演算法簡介演講 (地點: 工五館 A207)
6/1(星期二) 14:00-17:00 量子電腦程式設計課程 (地點: 電算中心)(因為疫情取消)
7. 動態規劃(dynamic programming)演算法: (Alg-DP.pptx) (4/27)
演算法課程_0427 maximum contiguous subsequence sum, MCSS Dynamic Programming algorithm_6
動態規劃(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)演算法
*最小編輯成本 (Minimum Edit Cost, MEC)演算法
*0/1背包動態規劃演算法(0/1 knapsack dynamic programming algorithm)
*子集合加總(subset sum)動態規劃演算法
*(複習)多項式及偽多項式時間演算法
*最大連續子序列和(maximum contiguous subsequence sum, MCSS)動態規劃演算法
Homework 7:
A. 說明X=ABCBA與Y=BDCA兩個字串藉由動態規劃演
算法求出最長共同子序列的過程。
B. 設計一個演算法，可以產生一個給定集合S的所有可能子集合。
C. 設計一個演算法，可以輸入長度為m的序列X及長 度為n的序列Y，輸出true或是false，分別 代表X是或不是Y的子序列。
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. 修改子集合加總動態規劃演算法使其傳回加總值為c的子集合若此子集合存在；否則傳回空集合。
G. 令S = (-2, 1, -3, 4, -1, 2, 1, -5, 4), 使用動態規劃演算法求出最大連續非空子 序列和。
H. 設計最大連續可空子序列和動態規劃演算法。
B. 設計一個演算法，可以產生一個給定集合S的所有可能子集合。
C. 設計一個演算法，可以輸入長度為m的序列X及長 度為n的序列Y，輸出true或是false，分別 代表X是或不是Y的子序列。
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. 修改子集合加總動態規劃演算法使其傳回加總值為c的子集合若此子集合存在；否則傳回空集合。
G. 令S = (-2, 1, -3, 4, -1, 2, 1, -5, 4), 使用動態規劃演算法求出最大連續非空子 序列和。
H. 設計最大連續可空子序列和動態規劃演算法。
- 8.
(5/4)樹搜尋(tree
search)與回溯(backtracking)演算法: (TreeSearch.pptx)
(5/4)
Slides and Videos: (Alg4-1203(NoMark).pptx) (更正: 投影片第36和37頁 樹第三層右邊的三個節點由左而右依序為"2' "4' "5") 5/4課程影片==>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)等演算法。
* 廣度優先搜尋(breadth-first search, BFS)演算法
* 深度優先搜尋(depth-first search, DFS)演算法
* 登山搜尋法(hill climbing search, HCS)演算法
* 最佳優先搜尋法(best-first search)演算法
* 回溯(backtracking)演算法
Homework 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
3184765
E. 以空單 格的移動方向為上下左右的次序，以深度優先搜 尋演 算法解決D題中 的八拼圖(8- puzzle)問題。1238
47
65
F. 以空單格的移動方向為上下左右的次序，以登山搜尋演算法解決D題中的八拼圖(8-puzzle)問題。而評估函數為 方塊錯置的數目，若有相同的 情形，則以空單格移動方向上下左右為其優先順序。
G. 以空單格的移動方向為上下左右的次序，以最佳優先搜 尋演算法解決D題中的八拼圖 (8-puzzle)問題。而評估函數為方塊錯置的數目，若有相同的情形，則以空單格移動方 向上下左右為其優先順序。 - 9. (5/11)
分支定界(Branch and
Bound)演算法 (Branch&Bound.zip)
(Youtube video Part1: https://youtu.be/KUlDxRV6fsU)(Youtube video Part2: https://youtu.be/R91wC81n6Yk)
(5/11)
*分支定界(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*演算法
Homework 9:
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的最段路徑問題。 - 10.
(5/18)使用貪婪(greedy)演算法以
及動態規劃(dynamic programming)演算法解決最短路徑問題: (Alg-SP.pptx) (5/18)
由加權有向圖(weighted digraph)中的某個頂點或節點 (vertex or node)v到圖中的另一節點u，若v到u之間存在一條路徑(path)，則路徑中所經過的邊(edge)的權值(weight)總合稱為路徑的成本 (cost)或距離(distance)，而所有路徑中具有最小成本或距離的路徑則稱為最短路徑(shortest path)。
著名的最短路徑演算法包括：
(0) 本次課程概要說明(含貪婪演算法及動態規劃演算法之比較說明)(影片網址:https://youtu.be/YYg8iLf1ej4)
(1) 多階圖最短路徑演算法(使用動態規劃解題策略)(影片網址:https://youtu.be/GQ4xKH4MpYI)
(2) Dijkstra演算法(使用貪婪解題策略)(期中考前已解說，因此不包含在此次課程影片中)
(3) Bellman-Ford演算法(使用動態規劃解題策略)(影片網址:https://youtu.be/jc-NLpcV6vY)
(4) Floyd-Warshall演算法(使用動態規劃解題策略)(影片網址:https://youtu.be/UdTjmFy7J_E)
Homework 10:
A. 使用動態規劃演算法求以下多階圖的最短路徑。
B. 利用Dijkstra演算法求以下圖(graph)頂點4到各頂點的最短路徑(shortest path)及其距離(成本)。
C. 承上題，利用Dijkstra演算法求頂點1到各頂點的最短路徑(shortest path)及其距離(成本)。
D. 畫圖說明利用利用Floyd-Warshall演算法求以下圖(graph)全對最短路徑(all-pair shortest path)距離(成本)(此圖的啟始距離矩陣如下，以經過的中間節點為s, a, b, c, d的順序寫出距離矩陣的改變過程。)
(d->b的加權在圖形與表格中誤植為不一致的值，同學可以將之改為5或6讓圖形與表格一致後解題都算答對。)
E. 求出以下給定圖(graph)的Floyd-Warshall演算法的啟始前節點矩陣(陣列)，並求出最後的前節點矩陣(陣 列)。
G. 針對以下的給定圖，列出Bellman-Ford最短路徑演算 法執行過程， 說明Bellman -Ford最短路徑演算法如何檢查出一給定圖具有負循環(negative-weight cycle)。
- (圖
形相關 演算法複雜度比較) (Optional)
- Introduction to Software Defined Networking (SDN) Multicast (SDN-Multicast.pptx) (Optional)
- 11. (5/25)(6/1)問
題下界與問題分類: P、NP、NP困難與NP完全問題 (5/25)(6/1)
*一個問題 的下界為任何能解決此問題的演算法至少所需的時間複雜度。(The lower bound of a problem is the least time complexity required for any algorithm which can be used to solve this problem.)
*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). (ProblemLB.zip)(Recipe, Cook and Carp)(NPC.zip)
*(NPC理論測驗及解答)
原6/1(星期二) 14:00-17:00 台大量子電腦程式設計課程因為疫情取消，改回由老師線上上課。
(5/25的課程請觀看下列的影片，作 業為A-F)
演算法課程_0525_1(13:00'為其他班級相關內容，請 由13:00'之後觀看)
演算法課程_0525_2(01:01' 為其他班級相關內容，請由01:01'之後觀看)
演算法課程_0525_3(05:41'為其他班級相關內容，請由 05:41'之後觀看)
(6/1 的課程請觀看下列的影片，作業為G-S，除了S題之外，繳交 作業時須先說明每個問題的定義，然後再寫證明)
Homework 11:
A. 以下的敘述是對還是錯，並解釋對或錯的原因:
若我們能證明任何一個 NPC問題的最壞狀況問題下界(worst case problem lower bound)是指數函數量級，則我們已經證明 NP不等於P。
B. 以下的敘述是對還是錯，並解釋對或錯的原因:
若我們能證明任何一個 NPC問題的最壞狀況問題下界(worst case problem lower bound)是多項式函數量級，則我們已經證明 NP等於P。
C. 以下的敘述是對還是錯，並解釋對或錯的原因:
若我們能直找到一個確定性演算法，在最差狀況下以多項式時間複雜度解決一個NPC問題，則我們已經證明NP等於P。
D. 以下的敘述是對還是錯，並解釋對或錯的原因:
人們已經證明: 沒有任何確定演算法(deterministic algorithm)可以在最差狀況(worst case)下，以多項式時間複雜度解決NPC問題。
E. 以下的敘述是對還是錯，並解釋對或錯的原因:
人們已經證明: 沒有任何確定演算法(deterministic algorithm)可以在最差狀況(worst case)下，以多項式時間複雜度解決NP-hard問題。
F. 以下的敘述是對還是錯，並解釋對或錯的原因:
任何NPC問題可以polynomially reduces to另一個NPC問題。
G. 證明支配集問題(dominating set problem)為NP問題。證明支配集問題(dominating set problem)為NP問題。
H. 證明點覆蓋問題(vertex cover problem)為NP問題。
I. 證明集團問題(clique problem)為NP問題。
J. 證明著色問題(chromatic coloring problem)為NP問題。
K. 證明0/1 背包問題(0/1 knapsack problem)為NP問題。
L. 證明3-滿足問題(3-SAT problem)為NP問題。
M. 證明最大割問題(Max cut problem)為NP問題。
N. 證明史坦惹樹問題(Steiner tree problem)為NP問題。
O. 證明劃分問題(partition problem)為NP問題。
P. 證明擊中集合問題(hitting set problem)為NP問題。
Q. 證明三維匹配問題(3-dimensional matching problem)為NP問題。
R. 證明Convex Hull問題的問題下界為Omega(n log n)
S. 畫出merge sort演算法的三個元素(1,2,3)的decision tree
- 12.
匈牙利演算法(Hungarian Algorithm)(HungarianAlg.zip)(6/8)
演算法課程 _0608(匈牙利演算法)影片
Homework 12: 本週只有兩題，因此每個學生都要做這兩題作業，但本週不需繳交影片與簡報。
A. 使用匈牙利演算法(Hungarian algorithm)來解以下的最小成本指派問題(assignment problem)（註: 必須寫出演算法執行過程中的每個中間結果）
B. 說明如何使用匈牙利演算法(Hungarian algorithm)解決最小歐氏平面權重配對(Minimum Euclidean Weighted Matching)問題。所謂最小歐氏平面權重 配對問題描述如下: 給定n個點(n為偶數)，如何將此n個點匹配形成n/2個點對，讓每個點對形成一條線段，而此n/2條線段具有最小的長度總和。
Task A
Task B
Task C
Tim
$1
$2
$3
Bob
$2
$3
$2
Alex
$2
$2
$3
