I5400B 教學大綱表

教學大綱表 (103學年度第2學期)

請遵守智慧財產權，勿使用非法影印教科書，避免觸法。

課程名稱 Course Title	(中文) 高等計算機演算法 (英文) Advance Computer Algorithms			開課單位 Departments	資訊工程研究所
				課程代碼 Course No.	I5400B
授課教師 Instructor	張薰文
學分數 Credit	3.0	必/選修 core required/optional	選修	開課年級 Level	研究所
先修科目或先備能力(Course Pre-requisites)：進階程式技術
課程概述與目標(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. text algorithms 8. NP-completeness
教科書(Textbook)	Cormen, Leiserson, and Rivest, Introduction to Algorithms
參考教材(Reference)

課程大綱 Syllabus			學生學習目標 Learning Objectives	單元學習活動 Learning Activities	學習成效評量 Evaluation	備註 Notes
序 No.	單元主題 Unit topic	內容綱要 Content summary	學生學習目標 Learning Objectives	單元學習活動 Learning Activities	學習成效評量 Evaluation	備註 Notes
1	Algorithm and time complexity	1. What is algorithm? 2. Time complexity and big O notation	Learn the basic concepts of algorithms and time complexity	講授
2	Insertion Sort and Merge Sort	1. Insertion sort 2. Merge sort	Learn insertion sort and merge sort algorithms	講授閱讀討論
3	Priority Queues and Heaps	1. Priority Queues 2. Heaps	Learn the data structures of priority queues and heaps.	講授實作閱讀討論	作業
4	Heap Sort and Quick Sort	1. Heap Sort 2. Quick Sort	Learn heap sort and quick sort algorithms	講授閱讀討論
5	The Lower Bound of Sorting Algorithms and Finding the Kth Minimum	1. The Lower Bound of Sorting Algorithms 2. Finding the Kth Minimum	Learn the lower bound of sorting algorithms and an algorithm for finding the Kth minimum	講授閱讀討論
6	Binary Search and Hash Table	1. Binary Search 2. Hash Table	Learn binary search and hash table algorithms	講授實作閱讀討論	作業
7	Divide-and-Conquer Strategies and Recursion	1. Divide-and-Conquer Strategies 2. Recursion	Learn the divide-and-conquer strategies and recursion algorithms	講授實作閱讀討論
8	Greedy Algorithms	1. Greedy Algorithms 2. Some scheduling algorithms using the greedy strategy	Learn some greedy algorithms and scheduling algorithms.	講授實作閱讀討論
9	Dynamic Programming	1. Dynamic Programming 2. Dynamic Programming versus Divide-and-Conquer	Learn the principles of dynamic programming versus divide-and-conquer	講授實作閱讀討論	報告
10	Matrix-Chain Product and Longest Common Subsequence	1. Matrix-Chain Product Algorithms 2. Longest Common Subsequence Algorithms	Learn matrix-chain product and longest common subsequence algorithms.	講授實作閱讀討論
11	Graph Traversal	1. Depth-First Search 2. Breadth-First Search	Learn graph traversal algorithms.	講授實作閱讀討論
12	Strongly Connected Components of Graphs	1. Strongly Connected Components of Graphs 2. Algorithms for Finding Strongly Connected Components	Learn strongly connected components of graphs and algorithms for finding strongly connected components.	講授實作閱讀討論	作業
13	Shortest Path Algorithms	1. Positive-Edge Shortest Path Algorithms 2. Shortest Path Algorithms with Negative Edges	Learn single-node shortest path algorithms	講授實作閱讀討論
14	All-Pair Shortest Path Algorithms	1. All-Pair Shortest Path Algorithms 2. Detecting Negative Cycles	Learn all-pair shortest path algorithms and algorithms for detecting negative cycles.	講授實作閱讀討論
15	Acyclic Graphs	1. Detecting Acyclic Graphs 2. Topological Sort of an Acyclic Graph	Learn algorithms for detecting acyclic graphs and for topological sort of an acyclic graph.	講授實作閱讀討論	作業
16	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.	講授實作閱讀討論
17	Network Flow and Bipartite Matching	1. Network Flow Algorithms 2. Maximum Bipartite Matching Algorithms	Learn network flow algorithms and maximum bipartite matching algorithms	講授實作閱讀討論
18	NP-Completeness	1. P and NP 2. NP-Completeness 3. Some NP-Complete Problems	Learn NP-completeness and some NP-complete Problems	講授實作閱讀討論	期末考

教學要點概述：
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：期末考：50% 報告：10% 作業：40%

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