演算法概論(英文授課)
Introduction to Algorithms
學期
108-1
學分
3
學分
當期課號
1250
永久課號
DCP1208
開課單位
資訊學院共同課程
授課教師
蔡孟宗
校區
光復
類別
必修
上課時間表
| 節 | 週二 | 週四 |
|---|---|---|
3 10:10–11:00 | 演算法概論(英文授課) EC115 2 節連堂 | |
4 11:10–12:00 | ||
7 15:30–16:20 | 演算法概論(英文授課) EC115 |
* 根據陽明交大上課時間表所列
概述
Introduction to Design and Analysis of Algorithms.
先修科目
Data Structures and Object-oriented Programming
教學方式
https://e3new.nctu.edu.tw/login/index.php
評分方式
(A) 3 written assignments + 2 quizzes, (B) 3 programming assignments + 2 programming quizzes, (C) 1 midterm exam, and (D) 1 final exam. The final grade is ≥ 0.4 Max{A, B} + 0.2 Min{A, B} + 0.2 C + 0.2 D.
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | Basics |
| 第 2 週 | Comparison-based Sorting |
| 第 3 週 | Selection, Sorting in Linear Time |
| 第 4 週 | Selected Geometric Problems |
| 第 5 週 | Hash Tables, Dynamic Programming |
| 第 6 週 | Dynamic Programming |
| 第 7 週 | Greedy Algorithms |
| 第 8 週 | Amortized Analysis, Quake Heaps |
| 第 9 週 | Midterm Exam |
| 第 10 週 | Data Structures for Disjoint Sets, Elementary Graph Algorithms |
| 第 11 週 | Minimum Spanning Trees |
| 第 12 週 | Shortest Paths |
| 第 13 週 | Maximum Flow |
| 第 14 週 | Linear Programming, Approximation Algorithms |
| 第 15 週 | NP-hardness, APX-hardness |
| 第 16 週 | Randomized Algorithms, Probabilistic Data Structures |
| 第 17 週 | Number-Theoretic Algorithms |
| 第 18 週 | Final Exam |
教科書
Introduction to Algorithms (3rd Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press.
Office Hours
- 地點
- EC 336
- 時間
- TBA
- 聯絡方式
- mtsai@cs.nctu.edu.tw