課程名稱 |
高等演算法 Advanced Algorithms |
開課學期 |
111-2 |
授課對象 |
電機資訊學院 電機工程學研究所 |
授課教師 |
陳和麟 |
課號 |
EE5182 |
課程識別碼 |
921 U2590 |
班次 |
|
學分 |
3.0 |
全/半年 |
半年 |
必/選修 |
選修 |
上課時間 |
星期四2,3,4(9:10~12:10) |
上課地點 |
明達231 |
備註 |
總人數上限:180人 |
|
|
課程簡介影片 |
|
核心能力關聯 |
本課程尚未建立核心能力關連 |
課程大綱
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
課程概述 |
This course will study various techniques for designing and analyzing algorithms. We will mainly focus on problems for which the exact algorithm is not known or not efficient enough and problems with resource constraints. Besides designing efficient algorithms, proving the performance guarantees is also a main topic of this course. Some topics that we will cover are as follows:
Approximation Algorithms: Algorithms that find near-optimal solutions with provable performance guarantees in polynomial time. This course will mainly focus on approximation algorithms for NP-hard problems.
Randomized Algorithms: Algorithms that use random numbers. We will focus on algorithms with provable success probabilities and good expected solution quality.
Streaming Algorithms: Algorithms that solve problems on massive datasets. In this type of problem, usually, the algorithm is only allowed to read the data once and use no more than a constant or poly-logarithmic amount of space.
Online Algorithm: The input to the problem is not known in advance and arrives over time. An online algorithm must decide how to process a specific input before seeing future inputs. The goal is to perform as well as an algorithm that knows all inputs beforehand.
We will cover algorithm design techniques such as hashing, sampling, and linear programming. |
課程目標 |
本課程主要針對從事演算法研究的學生,提供演算法設計的技巧與未來學習的方向。 |
課程要求 |
預修課程: 演算法、機率、離散數學、資料結構 |
預期每週課後學習時數 |
|
Office Hours |
每週四 12:00~13:00 備註: TA office hours:
林芃廷 r10921092@ntu.edu.tw office hour:Mon 10:00-12:00 MD709
王怡堯 r10921104@ntu.edu.tw office hour:Fri 13:20-15:20 MD709 |
指定閱讀 |
相關論文 |
參考書目 |
Design of Approximation Algorithms, Williamson and Shmoys
Randomized Algorithms, Motwani and Raghavan
Approximation Algorithms, Vazirani
|
評量方式 (僅供參考) |
No. |
項目 |
百分比 |
說明 |
1. |
作業 |
40% |
約四次作業 |
2. |
期中考 |
30% |
|
3. |
期末考 |
30% |
|
|
針對學生困難提供學生調整方式 |
上課形式 |
以錄影輔助, 提供學生彈性出席課程方式 |
作業繳交方式 |
|
考試形式 |
|
其他 |
|
|
週次 |
日期 |
單元主題 |
第1週 |
|
Course Overview
Knapsack Problem
PTAS/FPTAS |
第2週 |
|
Approximation Algorithms: Subset Sum and Bin Packing |
第3週 |
|
Linear Programming, ILP & LP relaxation, Vertex Cover, Set Cover |
第4週 |
|
Integrality Gap, Facility Location Problem, LP Duality |
第5週 |
|
Primal-Dual Algorithms (Set Cover, Facility Location) |
第6週 |
|
Greedy and Local Search Algorithms (Facility Location, k-median) |
第7週 |
|
Solving Linear Programs (Simplex Method, Ellipsoid Method), HW solutions |
第8週 |
|
Midterm |
第9週 |
|
Midterm solutions, Randomized Algorithms, Derandomization |
第10週 |
|
Randomized Rounding |
第11週 |
|
Hashing |
第12週 |
|
Markov Chain, Random Walk |
第13週 |
|
Counting and Sampling |
第14週 |
|
Streaming Algorithms, Online Algorithms |
第15週 |
|
Online Algorithms, HW3-4 solutions, Recap |
第16週 |
|
Final Exam |
|