交大修課心得 - 演算法概論

課程綱要

課程名稱：（中文授課）演算法概論

授課教師：蔡錫鈞

修課年度：107上 資訊共同 – 必修

使用書籍：Introduction to Algorithms (3rd Edition)

心得

教了什麼

投影片上課，投影片都放在 https://people.cs.nctu.edu.tw/~sctsai/algo/ ，老師的投影片算滿有名的 (?)，隨便在 Google 下關鍵字都會找到 XDD

1. Introduction, Recurrence, Divide and Conquer, FFT
2. HeapSort, Segment Tree, QuickSort, Linear time Sorting and Median Selection
3. Hash tables and applications
4. Dynamic Programming
5. Greedy Method
6. Amortized analysis
7. B-tree
8. Fibonacci Heap
9. DisjointSet
10. ElementaryGraphAlgorithms
11. Minimum Spanning Tree
12. Shortest Paths, sinlnge source and all pairs
13. Maximum Flow
14. NP-complete

上課方式

投影片上課。上課講滿多證明的，如果想了解整個演算法的前因後果推薦去上一下課。

完全不點名。

考試作業

• 考試 (75%)
  • 期中考 20%
  • 期末考 25%
  • 上機考*2 30%
• 作業 (25%)
  • 手寫作業 10%
  • 程式作業 15%

手寫作業這學期有兩次，時間在期中考前，大部分題目都是從 CLRS 裡面挑出來，但助教會很要求詳細的證明，所以亂證或是省略一些過程都會被扣分數。

程式作業除了考試周，其餘每周固定會有兩題，要自己去 https://oj.nctu.me 解。考試的內容有些會從作業裡拿出來變化一下。

期末考可以帶一張 A4 的大抄進考場。

期中期末的上機考都會部份給分，不會因為 WA, TLE 就給 0 分，是一筆一筆測資累積的。

期末成績好像會有些微調分，但怎麼調的不太清楚。

後記

這學期比較神奇的地方是因為期中的時候 FOJ 的 db 好像壞了，所以期中考的成績還有之前的一些作業都消失了，所以期末總成績好像也就只有算到期末考的成績。

這是我同學去跟助教 argue 才知道的事 (因為他期中考考比較好XD)