Algorithmics (演算法) 2020
Lecturer: 江振瑞
Teaching Assistants (TAs): 陳學致 李佳霖 廖建凱 陳沿廷
Time: 週二 14:00~16:50
Place: 週二 工五館E6-A207
TA Class:  週二 13:00~13:50 (工五館E6-A207)
 Online Video: https://www.twitch.tv/acanlab
Offline Video: https://drive.google.com/folderview?id=1WsZopoti_c_7gKfFHerIk5iflLGsQc4_
Scoring：
 Textbooks:
Reference Books:
Programming:
  • 安裝課程相關軟體及原始程式碼: Jeep7 (for JAVA platform on Windows)
    • 1 安裝Java Development Kit (JDK): http://java.sun.com/javase/downloads/index.jsp
    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軟體，並使用 [開舊檔]選項載入範例程式進行[編譯][執行]。

  • ACM國際大學生 程式設計 競賽 (ACM International Collegiate Programming Contest, ACM-ICPC) (ACM-ICPC&EPC.ppt)
    • Syllabus:  
    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. 設計    最大連續可空子序列和動態規劃演算法。
    著名的最短路徑演算法包括：
    (1) 多階圖最短路徑演算法    (使用動態規劃解題策略)
    (2) Dijkstra演算法(使用貪婪解題策略)
    (3) Bellman-Ford演算法(使用動態規劃解題策略)
    (4) Floyd-Warshall演算法(使用動態規劃解題策略)
    Homework 9:
    A. 使用動態規劃演算法求以下多階圖的最短路徑。
    MSG
         B. 利用Dijkstra演算法求以下圖(graph)頂點4到各頂點的最短路徑(shortest path)及其距離(成本)。
    A graph
    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演算法的啟始前節點矩陣(陣列)，並求出最後的前節點矩陣(陣列)。
    A graph
    G. 針對以下的給定圖，列出Bellman-Ford最短路徑演算 法執行過程， 說明Bellman -Ford最短路徑演算法如何檢查出一給定圖具有負循環(negative-weight cycle)。

    Problem Set 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問題。

    Links：
    Back to My Home