課程名稱 (中文) 高等計算機演算法 (英文) Advance Computer Algorithms 開課單位 資訊工程研究所 課程代碼 I5400A 授課教師 張薰文 學分數 3.0 必/選修 選修 開課年級 研究所 先修科目或先備能力：Algorithm 課程概述與目標：課程概述與目標：This course introduces a number of advanced algorithmic techniques and concepts. This will on the one hand broaden your algorithmic knowledge because you will see a number of new concepts, and on the other hand deepen your understanding because of the more advanced nature of the topics. The course consists of following topics: 1. greedy method 2. dynamic programming 3. divide-and-conquer method 4. tree-search strategies 5. graph algorithms 6. network flow and matching 7. NP-completeness 教科書 Introduction to Algorithms, 3rd ed., Cormen, Leiserson, Rivest, & Stein, MIT, 2009. 參考教材 Introduction to the Design & Analysis of Algorithms, A. Levitin, 3rd ed. Pearson, 2012.
 課程大綱 學生學習目標 單元學習活動 學習成效評量 備註 週 單元主題 內容綱要 1 Algorithm and time complexity 1. Review algorithm 2. Time complexity and notation Learn the basic concepts of algorithms and time complexity 討論講授 2 Heapsort & Quicksort 1. Heapsort algorithm 2. Quicksort algorithm Heapsort algorithm Quicksort algorithm 討論講授 3 Sorting in Linear Time 1. Radix sort 2. Bucket sort 1. Radix sort 2. Bucket sort 討論講授閱讀討論 報告 4 Dynamic Programming 1. Elements of Dynamic Programming 2. Longest Common Subsequence Learn the principles of dynamic programming. 討論實作講授閱讀討論 5 String Matching 1. Naive String-matching algorithm 2. Other String-matching algorithm Learn the principles of String-matching algorithm. 討論實作講授閱讀討論 作業 6 Graph Traversal 1. Representations of graphs 2. Breadth-First Search 3. Depth-First Search Learn graph traversal algorithms. 討論講授閱讀討論 7 Strongly Connected Components of Graphs 1. Strongly Connected Components 2. Algorithms for Finding Strongly Connected Components 3. Topological Sort Learn strongly connected components of graphs and algorithms for finding strongly connected components. 討論講授閱讀討論 作業 8 Minimum Spanning Tree 1. Prim's Algorithm 2. Kruskal's Algorithm Learn minimum spanning trees of a graph, and Prim's algorithm and Kruskal's algorithm for finding a minimum spanning tree. 實作講授閱讀討論 9 Review Review algorithms Evaluation 期中考 10 Single-Source Shortest Path Algorithms 1. Bellman-Ford Algorithm 2. Single-Source Shortest Path Algorithms in directed acyclic graphs Learn single-source shortest path algorithms 討論講授閱讀討論 11 Single-Source Shortest Path Algorithms 1. Dijkstra's Algorithm 2. Difference constraints Single-Source Shortest Path Algorithms Learn single-source shortest path algorithms 討論講授閱讀討論 報告 12 All-Pair Shortest Path Algorithms 1. All-Pair Shortest Path Algorithms 2. Shortest Paths & Matrix multiplication Learn all-pair shortest path algorithms. 討論實作講授閱讀討論 13 All-Pair Shortest Path Algorithms 1. Floyd-Warshall Algorithms 2. Johnson's Algorithm for Sparse Graphs Learn all-pair shortest path algorithms. 討論講授閱讀討論 作業 14 Network Flow and Bipartite Matching 1. Maximum Flow Algorithms 2. Ford-Fulkerson Method Learn network flow algorithms 討論講授閱讀討論 15 Network Flow and Bipartite Matching 1. Matching in a graph 2. Maximum Bipartite Matching Learn maximum bipartite matching. 討論講授閱讀討論 報告 16 NP-Completeness 1. P and NP 2. NP-Completeness 3. Some NP-Complete Problems Learn NP-completeness and some NP-complete Problems 實作講授閱讀討論 17 Approximation Algorithms 1. Vertex-Cover Problem 2. Traveling-Salesman Problem 3. Set-Covering Problem Learn some approximation algorithms. 討論實作講授 18 Review Review Evaluation 期末考
 教學要點概述： 教材編選： □ 自編教材 ■ 教科書作者提供 評量方法： 期末考：25%   期中考：25%   報告：20%   作業：30%   教學資源： □ 教材電子檔 □ 課程網站 扣考規定：http://eboard.ttu.edu.tw/ttuwebpost/showcontent-news.php?id=504

 核心能力 期末考 期中考 報告 作業 核心能力一 具備運用數學、科學及資訊工程相關知識的能力。 3/10 3 3 3 3 核心能力二 具備解決問題之分析、規劃、設計與執行的能力。 3/10 3 3 3 3 核心能力三 具備資訊系統整合與工程實作流程規劃的能力。 2/10 2 2 2 2 核心能力四 具備計畫管理、協調與溝通整合的能力。 1/10 1 1 1 1 核心能力五 具備持續自主學習以因應資訊產業發展趨勢的能力。 1/10 1 1 1 1