※ 本文是否可提供臺大同學轉作其他非營利用途？（須保留原作者 ID）
（是／否／其他條件）：是


哪一學年度修課：

105-2

ψ 授課教師 (若為多人合授請寫開課教師，以方便收錄)

陳和麟

λ 開課系所與授課對象 (是否為必修或通識課 / 內容是否與某些背景相關)

電機所選修

δ 課程大概內容

2/21 Course Overview, Knapsack Problem
2/28 (No Class)
3/07 Approximation Algorithms: Subset Sum and Bin Packing
3/14 Linear Programming, ILP & LP relaxation, Vertex Cover, Set Cover
3/21 Integrality Gap, Facility Location Problem, LP Duality
3/28 Primal-Dual Algorithms (Set Cover, Facility Location)
--------------------------期中考範圍-------------------------------
4/04 (No Class)
4/11 Solving Linear Programs(Simplex & Ellipsoid Methods), HW solutions
4/18 Midterm
4/25 Midterm solutions, Randomized algorithms, Derandomization
5/02 Hash Tables, Uniform Hashing, Sterling's formula,
Universal Hashing, Perfect Hashing
5/09 Chernoff Bound, Dynamic Resizing, Consistent Hashing
5/16 Markov Chain, Random Walk
5/23 Counting and Sampling
6/06 Streaming Algorithms, Online Algorithms
--------------------------期末考範圍-------------------------------
6/13 Online Algorithms, HW3-4 solutions, Recap
6/20 Final(online algorithm 不考)

前半學期是Approximation algorithm
後半學期是Randomized algorithm
這學期星期二放好多假所以streaming algorithm和online algorithm講比較少

Ω 私心推薦指數(以五分計)

★★★★★
滿天星阿！

η 上課用書(影印講義或是指定教科書)

沒有，但老師有提供三本參考書
Design of Approximation Algorithms by Williamson and Shmoys
Randomized Algorithms by Motwani and Raghavan
Approximation Algorithms by Vazirani

μ 上課方式(投影片、團體討論、老師教學風格)

板書

σ 評分方式(給分甜嗎？是紮實分？)

紮實甜
作業40%，期中考30%，期末考30%

有五次作業，總分是60+100+95+80+80=415，除以4當作作業成績
期中考全班平均 39.7，標準差21.4 調分方式：原始分數*0.8+44
期末考全班平均 55 ，標準差 25 調分方式：原始分數*0.8+38~40

ρ 考題型式、作業方式

每次作業大概五題，都是演算法的設計題以及證明題
考試難度跟作業差不多，考前一次上課會解答作業跟說考試內容
作業不接受補交，期限是繳交日的第一堂下課！

ω 其它(是否注重出席率？如果為外系選修，需先有什麼基礎較好嗎？老師個性？
加簽習慣？嚴禁遲到等…)

我記得沒錯的話是一類加選，所以直接選就好
基礎要有演算法的概念

Ψ 總結

老師很認真準備，而且老師觀念講的非常清楚
作業認真想，上課認真聽絕對可以學到很多東西
考試真的有難度看成績就知道，但這門課真的讓我有很大的收穫
考試成績會在一個禮拜內出來，會在期中期末考題目卷上寫最晚公布成績的時間
雖然老師說之後幾年內應該不會再開這門課
但老師說有想要開其他課的打算，可以期待一下
寫一下評價推一下老師（雖然版上很多篇了哈哈

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.115.202.112
※ 文章網址: https://www.ptt.cc/bbs/NTUcourse/M.1499070488.A.82E.html