演算法
Algorithms
| 節 | 週三 |
|---|---|
A 18:30–19:20 | 演算法 ED219（光復） 3 節連堂 |
B 19:30–20:20 | |
C 20:30–21:20 |
* 根據陽明交大上課時間表所列
This course is designed with two objectives: 1) To provide a background in techniques for analyzing the correctness and computational cost of algorithms and 2) To discuss specific algorithms from a variety of fields in Computer Science. Mathematical foundations will be reviewed, including asymptotic notation, summation techniques, and recurrences. Several algorithm design techniques, including greedy algorithms and dynamic programming will be discussed. Specific examples from graph theory, network flow, approximation algorithms and NP-completeness theory will also be covered in this course.
1. Data Structure (ECM2303 or equivalent) 2. Discrete Mathematics (DEE1533 or equivalent) 這門課程寒假會給出預備程式專題(即第一次程式專題作業) 屆時問題描述與測試資料會上傳至交大課程e3網站 繳交死線時間為開學前一周的周日(2/16)晚上11:55 !!!如未繳交上課前會被退選!!! 若開學後才選到課同學也須在一禮拜內完成!!! 請註冊同學務必審慎考量
無備註
1. NCTU e3 course website 2. The enrolled student will be asked to participate 2020 Intercollegiate CAD contest. 謝謝各位同學註冊本門課程提醒大家修課須知 由於這門課屬於電機所碩博班核心必修課程 為顧及修課品質不開放旁聽也不接受超額加簽 同時,這學期也與過去幾年開設時相同 設計了其他兩次程式專題(至少1000行)、四次手寫作業 與期中/期末考(筆試+口試) 還包含一定要參加2020的國際CAD程式設計競賽 課程實作負載量很重(期末專題約3000-5000行程式規模) 尤其對於C/C++程式設計實作能力上 請自行考量
作業部份: Homeworks will be divided into (1) 4 handwriting assignments and (2) 2 mini programming projects + 1 final term project. Registered students are also required to participate 2020 intercollegiate IC/CAD contest (http://iccad-contest.org/2020/). 考試部份: There are 2 examinations for this school year: one is midterm and the other is final. Midterm exam is paper-based and final exam is oral+paper (by default). 評量部份: 1. 4 hand-writing homework assignments: 10% 2. 1 midterm (paper) exam: 20% 3. 1 final (oral/paper) exam: 20% (10%+10%) 4. 2 programming mini-projects: 30% (15%+15%) 5. 2020 CAD Contest Participation: 30%
Fundamentals and Background
Course Syllabus, Mathematical reviews
- 講授：
- 3
- 示範：
- 0
- 實作：
- 0
- 其他：
- 0
Recurrences and Sorting
Insertion sort, merge sort and asymptotic notations, Recurrence solving; Heap sort and quick sort, Linear time sort; Order statistics
- 講授：
- 9
- 示範：
- 0
- 實作：
- 2
- 其他：
- 0
Dynamic Programming
Longest Common Sequence, Matrix-Chain Multiplication, Optimal Polygon Triangulation, Shortest Path and Knapsack Problem.
- 講授：
- 7
- 示範：
- 0
- 實作：
- 2
- 其他：
- 0
Greedy Algorithms
Maximum Sum, Huffman Encoding, Tasking Scheduling, and Set Cover.
- 講授：
- 5
- 示範：
- 0
- 實作：
- 2
- 其他：
- 0
Amortized analysis and Splay Trees
Hashing, hash table and hash functions; Dynamic tables; Amortized analysis
- 講授：
- 3
- 示範：
- 0
- 實作：
- 2
- 其他：
- 0
Graph Algorithms
Minimum Spanning Tree, Single-Source Shortest Path, All-Pair Shortest Path and Network Flow
- 講授：
- 9
- 示範：
- 0
- 實作：
- 2
- 其他：
- 0
NP-Completeness Theory
Turing Machine, Cook's Theorem, Reduction, Circuit SAT, Branch-and-Bound and Local Search.
- 講授：
- 9
- 示範：
- 0
- 實作：
- 2
- 其他：
- 0
| 週次 | 主題 |
|---|---|
| 第 1 週 | Syllabus, Administration, Course Overview & Prerequsite Test 3/4 |
| 第 2 週 | Sorting (1/3): Insertion Sort, Merge Sort & Asymptotic Notations 3/11 |
| 第 3 週 | Sorting (2/3): Recurrence Solving, Heap Sort & Quick Sort 3/18 |
| 第 4 週 | Sorting (3/3): Linear-time Sort & Order Statistics 3/25 |
| 第 5 週 | Dynamic Programming (1/2): Longest Common Sequence 4/1 |
| 第 6 週 | Dynamic Programming (2/2): Matrix-Chain Multiplication, Optimal Polygon Triangulation & Shortest Path 4/8 |
| 第 7 週 | Greedy Method (1/2): Knapsack Problem & Maximum Sum 4/15 |
| 第 8 週 | Greedy Method (2/2): Huffman Encoding, Task Scheduling & Set Cover 4/22 |
| 第 9 週 | Midterm Examination (Paper Test) 4/29 |
| 第 10 週 | Graph Algorithms (1/3): Minimum Spanning Tree & Shortest Path Problem 5/6 |
| 第 11 週 | Graph Algorithms (2/3): All-Pair Shortest Path 5/13 |
| 第 12 週 | Graph Algorithms (3/3): Network Flow 5/20 |
| 第 13 週 | NP-Completeness (1/2): Informal Discussion & Turing Machine 5/27 |
| 第 14 週 | NP-Completeness (2/2): Cook's Theorem, Reduction & Circuit-SAT 6/17 |
| 第 15 週 | Meta-Heuristics 6/10 |
| 第 16 週 | Final Review (No Class) 6/17 |
| 第 17 週 | Final Examination (Oral Test) 6/24 |
1. Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3rd Ed., McGraw Hill/The MIT Press, 2009. ISBN: 0-262-03384-4. (開發圖書代理) 2. Dasgupta, Papadimitriou, Vazirani, "Algorithms", 1st Ed., McGraw Hill, 2006, ISBN: 0073523402. (開發圖書代理)
- 地點
- ED-700
- 時間
- Wednesdays 1:30-3:30PM
- 聯絡方式
- E-mail: opwen@g2.nctu.edu.tw Phone: ext 31273