教學大綱表 (110學年度 第2學期)
請遵守智慧財產權，勿使用非法影印教科書，避免觸法。
課程名稱
Course Title		 (中文) 高等計算機演算法
(英文) Advance Computer Algorithms 		開課單位
Departments		 資訊工程研究所
課程代碼
Course No.		 I5400A
授課教師
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 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  


教學要點概述：
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： 期末考：25%   期中考：25%   報告：20%   作業：30%  

教學資源(Teaching Resources)：
□ 教材電子檔(Soft Copy of the Handout or the Textbook)
□ 課程網站(Website)
扣考規定：http://eboard.ttu.edu.tw/ttuwebpost/showcontent-news.php?id=504