課程大綱 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 |
|
|
|