演算法概論
Introduction to Algorithms
學期
109-1
學分
3
學分
當期課號
1184
永久課號
DCP3573
開課單位
資訊學院共同課程
授課教師
蔡錫鈞
校區
光復
類別
必修
上課時間表
| 節 | 週二 | 週四 |
|---|---|---|
3 10:10–11:00 | 演算法概論 EC022 2 節連堂 | |
4 11:10–12:00 | ||
7 15:30–16:20 | 演算法概論 EC022 |
* 根據陽明交大上課時間表所列
概述
The aim of this course is to have a study of efficient algorithms and data structures for computational problems.
先修科目
程式設計 資料結構
評分方式
手寫作業及隨堂考,程式作業 (預計每週1-2兩題程式題目) 20% 期中考 25% 期末考 25% 上機考 30% C/C++
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | Growth of functions and recurrences, Divide-and-Conquer, FFT |
| 第 2 週 | Heapsort, sorting in linear time, Medians |
| 第 3 週 | Randomized Quicksort |
| 第 4 週 | Universal Hash functions, bloom filter |
| 第 5 週 | Dynamic Programming |
| 第 6 週 | Dynamic programming |
| 第 7 週 | Greedy Algorithms |
| 第 8 週 | Amortized Analysis |
| 第 9 週 | B-Trees, Red-Black Tree |
| 第 10 週 | Fibonacci Heaps, Data Structure for Disjoint Sets |
| 第 11 週 | Elementary Graph Algorithms, Minimum Spanning Trees |
| 第 12 週 | Minimum Spanning Trees |
| 第 13 週 | Single-Source Shortest Paths, All-Pairs Shortest Paths |
| 第 14 週 | Maximum Flow |
| 第 15 週 | Maximum flow, Linear Programming (if time permits) |
| 第 16 週 | Algorithms for numbers |
| 第 17 週 | NP-Complete and Approximation algorithms |
教科書
Cormen, Leiserson, Rivest and Stein, ``Introduction to Algorithms'', 3rd ed, 2009, MIT press.
Office Hours
- 地點
- 工三 623
- 時間
- By appointment
- 聯絡方式
- Email: sctsai@cs.nctu.edu.tw