[評價] 111-1 陳倩瑜 資料結構與演算法實務
※ 本文是否可提供臺大同學轉作其他非營利用途？（須保留原作者 ID）
（是／否／其他條件）：是
哪一學年度修課：
111-1
ψ 授課教師 (若為多人合授請寫開課教師，以方便收錄)
陳倩瑜
λ 開課系所與授課對象 (是否為必修或通識課 / 內容是否與某些背景相關)
生機系/所選修 and 生機系人工智慧領域專長課程
δ 課程大概內容
具體可以看台大課程網，以下為實際上課進度
Union-Find
Analysis of Algorithms
Bags, Queues, and Stacks
Elementary Sort
Merge Sort
Quick Sort
Priority Queues
──────────期中考到這裡────────────────
Symbol Table
Binary Search Trees
Balanced Search Trees
Geometric Applications of BSTs
Undirected Graphs
Directed Graphs
Minimum Spanning Trees
Shortest Paths
──────────期末考到這裡────────────────
Hash Table和Dynamic Programming都來不及講了，期末考之後老師在NTU Cool上上傳了
兩年前的影片作為補充。
課程網上提到的 (optional)String相關的演算法更是完全沒時間上到。
Ω 私心推薦指數(以五分計) ★★★★★
·整體 ★★★★★
推就一個字！
·想修甜甜的資料結構與演算法 ★★★★★
·想修涼涼的資料結構與演算法 ★★★★★
·想修甜甜涼涼的普通選修課 ☆
看看隔壁資工的DSA，我覺得不需要別的解釋了吧，這已經是最甜涼的資料結構與演算法
相關課程了！
但是！甜涼只是相對於其他資料結構或者演算法課程而言的。完全不想花時間的話，還是
不要來學資料結構與演算法了。雖然這課很甜，個人也覺得很涼，但開學一開始加簽到
120人，退選加停修後只剩下74個同學堅持到最後。畢竟資料結構和演算法本身就不是容
易學的東西。
如果只是想當甜涼選修，請高抬貴手不要來搶加簽名額（哭）。
·留學要刷GPA ★★★★★
·找工作要刷題 ★★★
我個人是上半年有選資工的DSA，但因為半路突然發現資工的課給分超級慘烈，於是決定
停修。畢竟要留學的話，刷GPA比啥都重要。
PDSA應該是最容易刷GPA的相關課程了吧。
反正課程描述都差不多，爽爽拿高分不好嗎？
但如果是為了找工作的話，這門課其實並沒有資工DSA那麼扎實。不過如果只是想對資料
結構與演算法了解個大概，然後有能力自己刷LeetCode的話，完全是夠了。
·想學習實用資料結構與演算法 ★★★★★
課程內容最大的特色，應該就是強調資料結構與演算法的實際應用面向了。比如講
Union-Find時會帶出percolation問題，講Sorting時會提到convex hull問題，講
Priority Queues時會講到event-driven simulation。應該很適合想要實際使用程式的工
程科系的同學。
·想學習基礎資料結構與演算法 ★★★★★
·非電資科系想在未來挑戰資工DSA ★★★★★
個人感覺台大的普通程式課，和遍地IOI電神的資工DSA，是有極大的gap的。
如果是非電資科系，但有一顆想要學程式的心的話，
先修一下PDSA對資料結構與演算法有一個大致的了解，再去資工打Boss，
是一個非常好的過渡。
·電神 ☆
·已經在刷LeetCode ☆
這門課只教基礎的資料結構與演算法，
強者還是直接去資工和IOI電神們神仙打架吧。
η 上課用書(影印講義或是指定教科書)
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne
以及配套網站、投影片
μ 上課方式(投影片、團體討論、老師教學風格)
實體、遠距直播、NTUCool課程影片三種方式任選，出席完全不管，很自由。
課程影片上傳得非常及時，一般下午的課，當天晚上就會傳上去。
我個人是因為NTUCool可以倍速播放所以都直接看課程影片。
此外，還有一個臉書社團來發各種通知。
老師上課最大的特點，就是會一行一行帶著大家看code，講解非常仔細，且樂於解答同學
的問題。所以不用怕演算法通靈！跟著上課的進度一定可以理解的。
TA hour一般每週兩次，主要是作業答疑，會根據當週的作業情況調整，不過我一次都沒
去過啦。但平時偶爾問一些問題，可以感覺到助教們都非常認真負責。
σ 評分方式(給分甜嗎？是紮實分？)
Homework: 50%
Midterm: 20%
Final: 30%
最後應該有調一點分，
我個人原始分換算A，最後A+，不過怎麼調的就不清楚了。
ρ 考題型式、作業方式
1.作業
說好的作業很硬呢？特甜涼好嘛！
一共十題，只有程式題，沒有手寫題，用online judge批改，限定使用Java寫，都是與上
課內容直接相關的題目。我個人的話，最前面一些題目堅持手刻，最多花一個工作日就可
以全部AC。有部分比較簡單的題目call library的話極快，比如最後一個作業20分鐘就AC
了。不過感覺還是手刻的給自己的印象比較深刻。
然後比較讓我吐槽的一點是，很多題naive implementation竟然也能拿個60-80分！！！
蛤？？？這也太涼了吧！！！開學時說好的這課loading挺重的呢？？？
Too young, too simple！！！
最後應該是有28位同學拿滿作業分數，50多位同學拿到90%以上的分數。全班總共才74人
誒！
唯一一次比較有挑戰的是HW7有關Geometric Search的competition，速度前10%的同學總
成績額外加3分（7人）。好像最後似乎只有一位最快的同學刻出了KD Tree……我反正沒
刻出來，最後連普通的RB Tree都來不及補了（哭）。
此外，還有選6道LeetCode的題目（4道Easy和2道Medium），讓有興趣的同學可以自己練
，不過不強求。
總體而言感覺這個作業量對於想要簡單了解一下各種資料結構與演算法來說是夠了，但是
想要比較熟悉的話，最好還是自己再找點題去做。
想想隔壁資工的DSA，一次作業手寫滿分300分，一道LeetCode Hard難度的題目也就20分
；再想想資工的程式題，教紅黑樹，作業出吉如一線段樹套treap修改區間值......
想要甜涼作業的都快來修生機的PDSA吧！
2.考試
期中考試20%，教到哪裡就考哪裡，平均分56.89，最高分89。
期末考試30%，名義上是整學期都要考的，但是實際上感覺都是後半學期的內容，平均分
41.9，最高分79。
相比於作業的甜涼，考試就頗有難度了。內容有選擇、證明、寫pseudo code解題之類的
。有一些在上課時提到過，這個點可能會考。基本上就是投影片細節+一些比較通靈的問
題。
比如說，期末考最後一題考了Graph Coloring。
蛤？？？為什麼考試會出NP Complete的問題？？？！！！
看到這題我就嚇傻了好嘛！
反正這題沒人拿滿分，最多也就是greedy解。
大概是作業太甜了所以拿考試來控制一下分數吧。
ω 其它(是否注重出席率？如果為外系選修，需先有什麼基礎較好嗎？老師個性？
加簽習慣？嚴禁遲到等…)
1.Prerequisite
只需要會一種程式語言就可以了。不會Java也沒關係，因為一開始不會用到generic，
inheritance之類的內容，所以開學再學完全來得及。我覺得差不多修過商程設或者非
電資的程式課就夠了。
2.加簽方式
想要加簽的人太多了，所以最後採用抽籤方式，高年級與第一堂課到場者有優先權，97抽
40，加上初選湊滿120人。但是！HW1大勸退！大概有些同學程式基礎不夠，加上一上來就
講Union-Find，其實相比從linked list與stack開始講，要難理解一些。兩週後退選到只
剩90人，到了期末最後只有74人了。
感覺以後加簽的時候可能可以設計一個HW0讓大家不要誤入qwq
畢竟加簽抽籤實在是太刺激啦。
Ψ 總結
非常幸運能抽中PDSA的加簽名額！
順利拿到滿意的成績也非常開心！
推給所有非電資但想要學寫程式的同學！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.95.183 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/NTUcourse/M.1673449860.A.CE0.html
※ 編輯: JapanSpitz (101.12.95.183 臺灣), 01/11/2023 23:21:56
※ 編輯: JapanSpitz (140.112.25.99 臺灣), 01/12/2023 15:52:57
※ 編輯: JapanSpitz (140.112.25.99 臺灣), 01/12/2023 15:53:36