一、課程說明(Course Description)
授課內容:
本課程每週將針對 1~2 個主題,於課堂上講解該主題所需的演算法以及實作注意事項與技巧,然後要求同學完成 1~2 個程式作業,讓修課同學能夠在實作中更加了解演算法,提升實作能力。除了典型的問題外,每週也會講解1~2 個精彩的進階題目供同學討論與欣賞。期中與期末考都將採上機方式進行。由於課程重點是實作,將會略過大部分的證明,以實作技巧作為本課程的重心,方法(演算法與資料結構)優劣的評估也完全由實作觀點出發。
二、指定用書(Text Books)
課程中發給講義
三、參考書籍(References)
參考資料
[1] S. Anderson-Freed, E. Horowitz, and S. Sahni, Fundamentals of Data Structures in C, Computer Science Press
[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2003.
[3] ACM On-line Judge: http://acm.uva.es/problem/
[4] IOI 歷屆試題: http://olympiads.win.tue.nl/ioi/
四、教學方式(Teaching Method)
五、教學進度(Syllabus)
課程大綱 (暫定)
以下課題將視時間做調整,較進階的課題時間夠才教。另外,由於課程重點是實作,將會略過大部分的證明,以實作技巧作為本課程的重心,方法的優劣也完全由實作觀點出發。
1. Warm-up:簡介課程所採用的實作環境、debugging 和 testing 的技巧,以及一些寫程式的好習慣 (如: top-down design、modularization、避免使用 pointers 與 dynamic memory allocation 等)。
2. Sorting:介紹兩個實作上最好的sorting algorithms
3. Input processing and useful string functions:當遇到複雜的input格式時,如何對input作process,並介紹一些有用的string functions 來幫助 text processing
4. Big numbers:當運算的數字大小超過程式語言的表示範圍時,實作上該如何克服?
5. Prime numbers:介紹質數的性質以及一些質數相關問題的實作方式,如因數分解、中國餘式定理、Goldbach’s Conjecture等。
6. Binary search
7. Greedy method:介紹利用greedy method可以解決的一系列經典問題
8. Dynamic programming:介紹利用dynamic programming 可以解決的一系列經典問題,並講解實作上需要注意的技巧 (如:填表順序的選取與利用 recursive call 完成 backtracking等)。
9. Branch and bound:透過一系列經典問題讓同學熟悉 Branch and bound 這個實作技巧。
10. Representation of graphs:介紹在實作上 directed graph與 undirected graph 的最有效表示法。
11. Representation and recognition of trees:介紹在實作上 tree 的最有效表示法,以及如何判斷一個給定的graph是否為tree。另外,也會介紹一些基本的 tree algorithms (如traversal、計算 diameter等)。
12. Depth first search and breadth first search:介紹如何判斷DFS 與 BFS 的使用時機,以及在實作上所須注意的問題。
13. Shortest paths:介紹最經典的 shortest path algorithms,並教導同學在實作上該如何選擇對題目而言最簡單有效的實作方法以及資料結構。
14. Disjoint sets and minimum spanning trees:介紹disjoint set以及minimum spanning trees等問題的最有效實作方法。
15. Computational geometry and Euler tours:介紹幾個計算幾何上的經典問題以及最簡單有效的實作方法。
16. Maximum flows:介紹 Ford-Fulkerson method 以及簡單實作技巧,並介紹bipartite matching 與 minimum cost flow等應用。
17. Simulation:透過幾個經典問題讓同學熟悉撰寫 simulation 程式的技巧並說明一些設計時應注意的事項與可能掉入的陷阱。
18. Mathematics problems:介紹如高斯消去法等有名的數學題目,以及實作時該注意的問題。
六、成績考核(Evaluation)
(暫定)
1. 程式作業 50%
2. 上機期中考 20%
3. 上機期末考 30%
七、可連結之網頁位址
開學後公布