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

課程資料

演算法概論

開課：蔡錫鈞老師

修課年度：99資工系

這門課所使用的教科書是：《Introduction to Algorithms》，教到的主題大約為：

• Growth of Functions
• Recurrence
• Divide and Conquer
• Heapsort
• Quicksort
• Sorting in linear time
• Median Selection
• Hash Tables
• Bloom Filter
• Dynamic Programming
• Greedy Algorithms
• Amortized Analysis
• B-trees
• Fibonacci Heaps
• Disjoint Set Operations
• Elementary Graph algorithms
• Minimum Spanning Tree
• Shortest Paths
• Maximum flow

上課方式

使用投影片上課，作業通常得在上課前交，不接受遲交。所有的作業都會公佈在網頁上（在課堂公佈前就貼上課程網站了）投影片上有很多註解，有別班的同學說他自己覺得比他們班的投影片好理解，不妨參考：〈課程投影片〉。

評分方式

成績主要由期中、期末考，手寫及程式作業，以及上機考所決定。不點名，作業會抓抄襲，

小道消息指出，程式作業會搜尋一下網路看你是否直接下載別人的程式。

期中考分數分布：

考試作業

雖然老師一直強調注重實做的能力，認為修這班的學生一定要寫 code，不過覺得程式作業其實沒有想像中繁雜。(至少跟先前修吳育松老師的資料結構比起來，感覺 coding 時間少了很多)

第一個程式作業是實做 merge sort 和 heap sort。第二個是實做 Exercise 9.3-8：在 O(lg n) 時間找出兩個 sorted array 的中位數。第三個作業是修改老師寫到一半的程式碼，實做 chained hash table (事實上只要改數行)。第四個是 DP 有關的三個題目。第五個是實做 Huffman codes 並且作成一個可以壓縮和解壓縮檔案的程式(需要 demo)。第六個是實做跟 Maximum-flow 有關的題目以及跟 A* search algorithm 有關的題目。

大體上除了第五個作業外，都是純粹演算法的題目，而沒有很多實做的細節，所以通常在一百行內就結束，最長也差不多兩百多行。只是有些題目到底要怎麼套用演算法可能需要深切的思考跟那種沒有複雜演算法但實做起來要花很多時間的 project 大不相同。

而手寫的題目大多是證明題，助教對證明嚴謹度十分要求。由於課本後面的解答大多忽略很多細節，所以直接照著寫一定是會被扣分的。（就算用老師公佈的解答寫在期中考上也會被扣分，筆者親身經歷。）筆者覺得寫手寫作業的時間比 coding 長很多。

題外話，在這堂課的訓練之下，寫到後來慢慢自己對嚴謹度的要求也愈來愈高。像是這題：

16.3-7

Generalize Huffman’s algorithm to ternary codewords (i.e., codewords using the symbols 0, 1, and 2), and prove that it yields optimal ternary codes.

筆者為了達到十足的嚴謹度，足足寫了 A4 紙兩面半才證完。(雖然我覺得應該不可能要寫到這種地步才能拿滿分，並且數學好的人說不定可以用短一點又嚴謹的方法證明它吧)

考試方面有期中考和期末考，幾乎都是考考古題，主要仍以證明為主，少部份是操作演算法

還有一兩題是手寫短程式。

還有一個期中上機考，幾乎都是考作業題，如果上機考不好，最後還有個上機補考。

結語

演算法是資工最核心的學科之一，沒事可以多讀讀 Introduction to Algorithms。如果對 online judge 形式的作業不熟悉可以參考：〈基礎程式設計〉。學校的網站上有很多題目可供練習，未來應該會有很多課都採用此一介面來交作業及考試。

想看一下演算法的介紹可參考：演算法筆記。