課程名稱 |
資料結構與演算法 DATA STRUCTURES AND ALGORITHMS |
開課學期 |
98-2 |
授課對象 |
生物資源暨農學院 生物機電工程學研究所 |
授課教師 |
陳倩瑜 |
課號 |
BME5902 |
課程識別碼 |
631 U1250 |
班次 |
|
學分 |
3 |
全/半年 |
半年 |
必/選修 |
選修 |
上課時間 |
星期二5(12:20~13:10)星期五3,4(10:20~12:10) |
上課地點 |
電電實驗室農機會議室 |
備註 |
上課教室:電電實驗室與農機館會議室. 總人數上限:30人 |
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/982DSA |
課程簡介影片 |
|
核心能力關聯 |
核心能力與課程規劃關聯圖 |
課程大綱
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
課程概述 |
上課地點補述: 二5在電電實驗室(知武館3F), 五34在農機會議室(農機館2F)
此一課程在於介紹多種常用之資料結構與相關演算法,增進修課學生的程式設計能力,以期未來能在不同領域實際應用。
每週課程計畫進度:
1. Complexity
2. Linear Lists – Array Representation
3. Linear Lists – Linked Representation
4. Arrays and Matrices
5. Stacks
6. Queues
7. Skip Lists and Hashing
8. Binary and Other Trees
9. Priority Queues
10. Greedy Method
11. Divide and Conquer
12. Dynamic Programming
13. Backtracking
14. Branch and Bound
|
課程目標 |
本課程將搭配C++程式編輯,介紹多種可使用的資料結構,引領學生了解現有演算法,解決實際問題。 |
課程要求 |
修過至少一種基本程式設計課程(any language is fine, ext. C, C++, Java, Perl, ...) |
預期每週課後學習時數 |
|
Office Hours |
|
指定閱讀 |
|
參考書目 |
1. Robert Sedgewick, Algorithms in C++, Parts 1-4: Fundamentals, Data
Structure, Sorting, Searching (3rd Edition), Addison-Wesley Professional, 1998.
2. Elliot B. Koffman and Paul A. T. Wolfgang, Objects, Abstraction, Data
Structures and Design: Using C++, Wiley, 2005.
3. Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani, Algorithms,
McGraw-Hill, 2006. (http://www.cs.berkeley.edu/~vazirani/algorithms.html) |
評量方式 (僅供參考) |
No. |
項目 |
百分比 |
說明 |
1. |
作業 |
40% |
約有十次寫程式的作業(使用c/c++) |
2. |
期中考 |
30% |
|
3. |
期末考 |
30% |
|
|
週次 |
日期 |
單元主題 |
第1週 |
02/23, 02/26 |
Introduction / connectivity problem |
第2週 |
03/02, 03/05 |
Connectivity / time analysis |
第3週 |
03/09, 03/12 |
Complexity of algorithms |
第4週 |
03/16, 03/19 |
Recurrences / examples of algorithm analysis |
第5週 |
03/23, 03/26 |
Arrays, linked lists, memory allocation, strings |
第6週 |
03/30, 04/02 |
Lists, stack, queues |
第7週 |
04/05, 04/09 |
國定假日, ADT, stack |
第8週 |
04/12, 04/16 |
ADT / Recursion |
第9週 |
04/19, 04/23 |
Recursion, Divide and Conquer |
第10週 |
04/26, 04/30 |
Midterm (4/30, 10:20am) |
第11週 |
05/04, 05/07 |
Tree Traversal, Recursion |
第12週 |
05/11, 05/14 |
Binary trees |
第13週 |
05/18, 05/21 |
Tree and graph traversal |
第14週 |
05/25, 05/28 |
Sorting |
第15週 |
06/01, 06/04 |
Priority queue and heapsort |
第16週 |
06/08, 06/11 |
Greedy Algorithms, Minimum Spanning Trees |
第17週 |
06/15, 06/18 |
Hashing |
第18週 |
06/22, 06/25 |
Final |
|