演算法
Algorithms
| 節 | 週二 |
|---|---|
A 18:30–19:20 | 演算法 ED103 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網站 繳交死線時間為開學上課前一天的周日(2023/02/12)晚上11:59 !!!如未繳交上課前會被退選!!! 若開學後才選到課同學也須在一禮拜內完成!!! 請註冊選課同學務必審慎考量。另外本門課不開放旁聽。
1. NYCU e3 course website 2. The enrolled student will be asked to participate 2023 ICCAD/CAD contest (pass beta test). 謝謝各位同學註冊本門課程提醒大家修課須知 由於這門課屬於電機所碩博班核心必修課程 為顧及修課品質不開放旁聽也不接受超額加簽 本學期由於修課人數較多擬採用翻轉教學法 實施方式為同學們分組代表教學 每周前半堂為老師帶領複習 後半堂為各組推派代表講解 現場其餘他組同學將會給予互評 同時,這學期也與過去幾年開設時相同 設計了其他3次程式專題(至少500-1000行)、10次手寫作業 與期中/期末考(筆試+口試) 還包含一定要參加2023的國際ICCAD/CAD程式設計競賽 課程實作負載量很重(期末專題約2000-3000行程式規模) 尤其對於C/C++程式設計實作能力上 請自行考量
作業部份: Complete 3 homework assignments: (1) 1 pre-requisite programming assignment, (2) 10 hand-writing homework assignments and (3) 2 mini programming assignments. The enrolled students are also required to participate in the ICCAD/CAD contest in 2023. (http://iccad-contest.org/2023/). 考試部份: There is only 1 examination for this school year: the final exam is oral based (by default). 評量部份:Total 110% 1. 1 pre-requisite programming assignment: 15% 2. 10 hand-writing assignments: 15% 3. 2 programming mini-projects: 20% (10%+10%) 4. 2023 ICCAD/CAD contest participation (pass beta test): 20% 5. 1 team presenation: 20% (including individual video(5%), external (10%) and internal (5%) evaluations) 6. 1 final (oral/paper) exam: 20%
- Fundamentals and Background
- Recurrences and Sorting
- Dynamic Programming
- Greedy Algorithms
- Amortized analysis and Splay Trees
- Graph Algorithms
- NP-Completeness Theory
- Metaheuristics
| 週次 | 主題 |
|---|---|
| 第 1 週 | Syllabus, Administration, Course Overview & Prerequsite Test |
| 第 2 週 | Sorting (1/3): Insertion Sort, Merge Sort & Asymptotic Notations |
| 第 3 週 | National Holiday |
| 第 4 週 | Sorting (2/3): Recurrence Solving, Heap Sort & Quick Sort (Team #1 林子昊、黃順平) |
| 第 5 週 | Sorting (3/3): Linear-time Sort & Order Statistics (Team #2 楊堃彧、呂瑋宸) |
| 第 6 週 | Dynamic Programming (1/2): Longest Common Sequence (Team #3 曹智榮、蘇柏瑋) |
| 第 7 週 | Dynamic Programming (2/2): Matrix-Chain Multiplication, Optimal Polygon Triangulation & Shortest Path (Team #4 賴宥齊、陳昱揚) |
| 第 8 週 | Ching Ming Festival (No class) |
| 第 9 週 | Greedy Method (1/2): Knapsack Problem & Maximum Sum (Team #5 翁鉑翔、曾德翰) |
| 第 10 週 | Greedy Method (2/2): Huffman Encoding, Task Scheduling & Set Cover (Team #6 吳孟宸、陳彥潔) |
| 第 11 週 | Hashing (1/1): Hash Table, Hash Functions & Amortized Analysis (Team #7 陳韋年、游翔竣) |
| 第 12 週 | Graph Algorithms (1/2): Minimum Spanning Tree & Shortest Path Problem (Team #8 鄭文洋、李元中) |
| 第 13 週 | Graph Algorithms (2/): All-Pair Shortest Path & Network Flow (Team #9 鄭有志、饒秉宸) |
| 第 14 週 | NP-Completeness (1/2): Informal Discussion & Turing Machine |
| 第 15 週 | NP-Completeness (2/2): Cook's Theorem, Reduction & Circuit-SAT |
| 第 16 週 | Meta-Heuristics |
| 第 17 週 | Final Examination #1 (Oral Test) |
| 第 18 週 | Final Examination #2 (Oral Test) |
1. Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 4th Ed., McGraw Hill/The MIT Press, 2022. ISBN: 026204630X. (開發圖書代理) 2. Dasgupta, Papadimitriou, Vazirani, "Algorithms", 1st Ed., McGraw Hill, 2006, ISBN: 0073523402. (開發圖書代理)
- 地點
- ED-700
- 時間
- Wednesdays 1:30-3:30PM
- 聯絡方式
- E-mail: opwen@nycu.edu.tw Phone: ext 31273