教學大綱表
請遵守智慧財產權,勿使用非法影印教科書,避免觸法。
課程名稱 (中文) 高等計算機演算法
(英文) Advance Computer Algorithms
開課單位 資訊工程研究所
課程代碼 I5400A
授課教師 張薰文
學分數 3.0 必/選修 選修 開課年級 研究所
先修科目或先備能力:Algorithm
課程概述與目標:課程概述與目標: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
教科書 Introduction to Algorithms, 3rd ed., Cormen, Leiserson, Rivest, & Stein, MIT, 2009.
參考教材 Introduction to the Design & Analysis of Algorithms, A. Levitin, 3rd ed. Pearson, 2012.
課程大綱 學生學習目標 單元學習活動 學習成效評量 備註
單元主題 內容綱要
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
  • 期末考
  •  

    教學要點概述:
    教材編選: □ 自編教材 ■ 教科書作者提供
    評量方法: 期末考:25%   期中考:25%   報告:20%   作業:30%  
    教學資源: □ 教材電子檔 □ 課程網站
    扣考規定:http://eboard.ttu.edu.tw/ttuwebpost/showcontent-news.php?id=504

    研究所
    核心能力 期末考 期中考 報告 作業
    核心能力一 具備運用數學、科學及資訊工程相關知識的能力。 3/10 3 3 3 3
    核心能力二 具備解決問題之分析、規劃、設計與執行的能力。 3/10 3 3 3 3
    核心能力三 具備資訊系統整合與工程實作流程規劃的能力。 2/10 2 2 2 2
    核心能力四 具備計畫管理、協調與溝通整合的能力。 1/10 1 1 1 1
    核心能力五 具備持續自主學習以因應資訊產業發展趨勢的能力。 1/10 1 1 1 1