課程名稱Course Title (中文) 高等計算機演算法 (英文) Advance Computer Algorithms 開課單位Departments 資訊工程研究所 課程代碼Course No. I5400 授課教師Instructor 張薰文 學分數Credit 3.0 必/選修core required/optional 選修 開課年級Level 研究所 先修科目或先備能力(Course Pre-requisites)：Algorithm 課程概述與目標(Course Overview and Goals)：課程概述與目標：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 教科書(Textbook) Introduction to Algorithms, 3rd ed., Cormen, Leiserson, Rivest, & Stein, MIT, 2009. 參考教材(Reference) Introduction to the Design & Analysis of Algorithms, A. Levitin, 3rd ed. Pearson, 2012.
 課程大綱 Syllabus 學生學習目標Learning Objectives 單元學習活動Learning Activities 學習成效評量Evaluation 備註Notes 序No. 單元主題Unit topic 內容綱要Content summary 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 Strongly Connected Components of Graphs 1. Representations of graphs 2. Strongly Connected Components 3. Algorithms for Finding Strongly Connected Components 4. Topological Sort Learn strongly connected components of graphs and algorithms for finding strongly connected components. 7 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. 8 Review Review algorithms Evaluation 期中考 9 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 10 Single-Source Shortest Path Algorithms 1. Dijkstra's Algorithm 2. Difference constraints Single-Source Shortest Path Algorithms Learn single-source shortest path algorithms 11 All-Pair Shortest Path Algorithms 1. All-Pair Shortest Path Algorithms 2. Shortest Paths & Matrix multiplication Learn all-pair shortest path algorithms. 12 All-Pair Shortest Path Algorithms 1. Floyd-Warshall Algorithms 2. Johnson's Algorithm for Sparse Graphs Learn all-pair shortest path algorithms. 13 Network Flow and Bipartite Matching 1. Maximum Flow Algorithms 2. Ford-Fulkerson Method Learn network flow algorithms 14 Network Flow and Bipartite Matching 1. Matching in a graph 2. Maximum Bipartite Matching Learn maximum bipartite matching. 15 NP-Completeness 1. P and NP 2. NP-Completeness 3. Some NP-Complete Problems Learn NP-completeness and some NP-complete Problems 16 Approximation Algorithms 1. Vertex-Cover Problem 2. Traveling-Salesman Problem 3. Set-Covering Problem Learn some approximation algorithms. 17 Review Review Evaluation

 序No. 實施期間Period 實施方式Content 教學說明Teaching instructions 彈性教學評量方式Evaluation 備註Notes 1 起:2024-03-11 迄:2024-03-31 2.非同步線上課程 Asynchronous online course 學習以下單元： Complexity of Divide-and-Conquer Algorithms (Master Theorem) 測驗 2 起:2024-05-06 迄:2024-05-27 2.非同步線上課程 Asynchronous online course 學習以下內容： Minimum Spanning Trees

 教學要點概述： 1.自編教材 Handout by Instructor： ■ 1-1.簡報 Slids □ 1-2.影音教材 Videos □ 1-3.教具 Teaching Aids □ 1-4.教科書 Textbook □ 1-5.其他 Other □ 2.自編評量工具/量表 Educational Assessment □ 3.教科書作者提供 Textbook 成績考核 Performance Evaluation： 期末考：30%   期中考：30%   彈性教學：10%   平時考：20%   作業：10%   教學資源(Teaching Resources)： ■ 教材電子檔(Soft Copy of the Handout or the Textbook) □ 課程網站(Website) 扣考規定：https://curri.ttu.edu.tw/p/412-1033-1254.php