教學大綱表 (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)
扣考規定:https://curri.ttu.edu.tw/p/412-1033-1254.php