課程資訊
課程名稱
高等演算法
Advanced Algorithms 
開課學期
105-2 
授課對象
電機資訊學院  電機工程學研究所  
授課教師
陳和麟 
課號
EE5182 
課程識別碼
921 U2590 
班次
 
學分
3.0 
全/半年
半年 
必/選修
選修 
上課時間
星期二7,8,9(14:20~17:20) 
上課地點
明達231 
備註
總人數上限:100人 
Ceiba 課程網頁
http://ceiba.ntu.edu.tw/1052EE5182_adv_alg 
課程簡介影片
 
核心能力關聯
本課程尚未建立核心能力關連
課程大綱
為確保您我的權利,請尊重智慧財產權及不得非法影印
課程概述

In this course, we will study a variety of different techniques for design and analyzing algorithms. We will mostly 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 major topic of this course. Some topics that we will cover are as follows:

1. Approximation Algorithms: Algorithms that find near-optimal solutions with provable performance guarantees in polynomial time. In this course, we will mostly focus on approximate algorithms for NP-hard problems.

2. Randomized Algorithms: Algorithms that use random numbers. We will focus on algorithms with provable success probabilities and/or good expected solution quality.

3. Streaming Algorithms: Algorithms that solves problems on huge 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.

4. Online Algorithm: The input to the problem is not known in advance and arrives over time. An online algorithm needs to make decision on 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 different algorithm design techniques such as hashing, sampling and linear programming. 

課程目標
本課程主要針對從事演算法研究的學生,提供演算法設計的技巧與未來學習的方向。 
課程要求
預修課程: 演算法、機率、離散數學、資料結構 
Office Hours
 
參考書目
Design of Approximation Algorithms by Williamson and Shmoys
(legal electronic version available online)
Randomized Algorithms by Motwani and Raghavan
Approximation Algorithms by Vazirani 
指定閱讀
相關論文 
評量方式
(僅供參考)
 
No.
項目
百分比
說明
1. 
作業 
40% 
約四次作業 
2. 
期中考 
30% 
 
3. 
期末考 
30% 
 
 
課程進度
週次
日期
單元主題
第1週
2/21  Course Overview, Knapsack Problem (Review of prior knowledge) 
第2週
2/28  No Class 
第3週
3/07  Approximation Algorithms: Subset Sum and Bin Packing 
第4週
3/14  Linear Programming, ILP & LP relaxation, Vertex Cover, Set Cover 
第5週
3/21  Integrality Gap, Facility Location Problem, LP Duality 
第6週
3/28  Primal-Dual Algorithms (Set Cover, Facility Location) 
第7週
4/04  No Class 
第8週
4/11  Solving Linear Programs(Simplex & Ellipsoid Methods), HW solutions 
第9週
4/18  Midterm 
第10週
4/25  Midterm solutions, Randomized algorithms, Derandomization 
第11週
5/02  Hash Tables, Uniform Hashing, Sterling's formula, Universal Hashing, Perfect Hashing 
第12週
5/09  Chernoff Bound, Dynamic Resizing, Consistent Hashing 
第13週
5/16  Markov Chain, Random Walk 
第14週
5/23  Counting and Sampling 
第15週
5/30  No Class 
第16週
6/06  Streaming Algorithms, Online Algorithms 
第17週
6/13  Online Algorithms, HW3-4 solutions, Recap