演算法

Algorithms

學期

112-2

學分

3 學分

當期課號

535363

永久課號

EECM30065

開課單位

電信工程研究所

授課教師

溫宏斌

校區

光復

類別

選修

上課時間表

節	週一
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) 請注意: 這門課程寒假會給出預備程式專題(即第一次程式專題作業) 作業的問題描述與測試資料可在TeraBox雲端下載,連結如下(需先下載TeraBox桌面版應用程式並註冊一個帳戶才能進行下載) https://terabox.com/s/11JhJXSC9i0-G3Ghrmkxuiw 請想選修這門課的同學務必準時繳交(已經選到課的同學請在E3繳交,尚未選到課的同學請將繳交檔案寄給助教pintang.ee10@nycu.edu.tw) 繳交期限為開學上課前一天的週日(2024/02/18)晚上11:59 !!! 如未繳交上課前會被退選!!! 請註冊選課同學務必審慎考量。

教學方式

1. NYCU E3 course website 2. The enrolled student will be asked to participate 2024 ICCAD/CAD contest (pass beta test). 謝謝各位同學註冊本門課程,以下為修課須知: 本學期由於修課人數較多擬採用翻轉教學法實施方式為同學們分組代表教學每周前半堂為老師帶領複習後半堂為各組推派代表講解現場其餘他組同學將會給予互評同時,這學期也與過去幾年開設時相同設計了其他3次程式專題(至少500-1000行)、10次手寫作業與期中/期末考(筆試+口試) 還包含一定要參加2024的國際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 2024. (https://iccad-contest.org/). 考試部份: 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: 20% 2. hand-writing homework assignments: 10% 3. 2024 ICCAD/CAD contest participation (pass beta test): 30% 4. 1 team presentation: 30% (including individual video(10%), external (10%) and internal (10%) evaluations) 5. 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 週	Sorting (2/3): Recurrence Solving, Heap Sort & Quick Sort
第 4 週	Sorting (3/3): Linear-time Sort & Order Statistics
第 5 週	Dynamic Programming (1/2): Longest Common Sequence (陳弘洋、陳柏文)
第 6 週	Dynamic Programming (2/2): Matrix-Chain Multiplication, Optimal Polygon Triangulation & Shortest Path (吳紹宇、湯睿廷)
第 7 週	Greedy Method (1/2): Knapsack Problem & Maximum Sum (戴宸洋、張量象)
第 8 週	Greedy Method (2/2): Huffman Encoding, Task Scheduling & Set Cover (呂宗霖、蔡伯俋)
第 9 週	Hashing (1/1): Hash Table, Hash Functions & Amortized Analysis (陳薔)
第 10 週	老師出國,停課一次
第 11 週	Graph Algorithms (1/2): Minimum Spanning Tree & Shortest Path Problem (吳欣宇、康學民)
第 12 週	Graph Algorithms (2/2): All-Pair Shortest Path & Network Flow (龔家雋、林境觀)
第 13 週	NP-Completeness (1/2): Informal Discussion & Turing Machine
第 14 週	NP-Completeness (2/2): Cook's Theorem, Reduction & Circuit-SAT
第 15 週	Meta-Heuristics
第 16 週	6/3(一) : Final Examination #1 (Oral Test) 6/4(二) : 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. (開發圖書代理)

Office Hours

地點: ED-700
時間: Wednesdays 1:30-3:30PM
聯絡方式: E-mail: opwen@nycu.edu.tw Phone: ext 31273