data structure and algorithm

Presentation on theme: "data structure and algorithm"— Presentation transcript:

1 data structure and algorithm
Prof. Hsin-Mu (Michael) Tsai (蔡欣穆) Spring 2012

2 這堂課學什麼? 練功 什麼是資料結構? 什麼是演算法? 時間與空間複雜度分析 各種資料結構+演算法的用法+實作
以及, 許多許多的程式撰寫練習(作業) 練功

3 你需要什麼才能修這門課? 兩樣東西: 附帶條件: C Programming (大多同學上學期修過程式設計) 基礎的數學 (高中程度)
很多時間練功(寫作業) 多來上課 中午不要吃太飽(才不會睡著) 上課跟老師互動

4 課程大綱 Topics: Graphs Basic concepts Sorting Arrays and structures
Stacks and queues Linked lists Trees Graphs Sorting Hashing Priority queues Other search structures 這就是課程大綱! 期末教學意見調查不要再說 老師沒有在學期開始列出課程大綱了!

5 課程特色 My goal: 80% of the students will understand 80% of the content
Easy lectures, hard homework assignments 2 Graduate TAs + 4 Undergraduate TAs: lots of office hours Use lots of animations 老師會用冷笑話冷醒睡著的同學 上課你沒有弄懂, 我不會放棄的 你沒聽懂, 我就再講一次 你有問題(沒有笨問題), 我就回答你(如果我會的話) 當我問有沒有聽懂的時候, 請理我一下 Q_Q

6 English Chinese slides + Mandarin/English lectures
Homework + exam will be in English (feel free to use Chinese to answer) Reading assignments will be given If you don’t understand, AAAAASSSSSSSKKKKK. Lots of communication methods

7 教學團隊 Name Office hour Room Michael Tsai (蔡欣穆) Wednesdays 11:00-12:00 R316 Hsin Miao(繆昕) Tuesdays 13:00-14:00 R508 Ming-Chang Li(李明璋) Thursdays 13:00-14:00 YunJu Lee(李昀儒) Thursdays 18:30-20:00 R204 Eric Lee(李冠穎) Harry Chen(陳彥儒) Fridays 9:10-10:00 R217 Orina Shiue(薛祐婷) All members of the teaching team will receive s sent to this address.

8 通訊 課程網頁: http://www.csie.ntu.edu.tw/~hsinmu/courses/dsa_12spring
[Office hours] 請多加利用. [學生老師/助教] 課程相關的所有問題, 請 寄 給 發文在ptt2上的HsinMu板 Facebook Group (網址在課程網頁上) 請來我們的Office hour發問 [老師/助教學生] [主要]會寄 到CEIBA上登記的 信箱 (大部分人是學校 , 不是系上信箱, 請注意!) [次要]部分訊息會請助教發在Facebook Group上+ptt2版上 (門可羅雀 T_T)

9 上課時間及地點 Location: CSIE Building 102
Time: Tuesdays, NTU class time for 6,7,8 第6節 14：20～15：10 第7節 15：30～16：20 第8節 16：30～17：20 How about 14:20-15:10, 15:20-16:10, 16:20-17:10? 150 minutes of class, 20 minutes of break, 14:2017:20 機動調整下課時機及長度

10 課本 (1/2) Data Structures and Algorithms Made Easy, Second Edition, 2011, CareerMonk Publications, by Karumanchi

11 課本(2/2) Introduction to Algorithms, 3rd edition, 2009, MIT Press by Cormen, Leiserson, Rivest, and Stein *借用呂學一老師2010 Fall投影片中的圖片

12 DATA STRUCTURE AND ALGORITHM I
HSIN-MU TSAI, FALL 2010 參考書籍 Fundamentals of Data Structures in C, 2nd Edition, 2008 Horowitz, Sahni, and Anderson-Freed

13 成績計算方式 6次作業, 占48%, 期中考 22% (涵蓋期中考前課程內容) 期末考 30% (涵蓋全課程內容)
最佳的一次加重50%, 最差的一次減重50% Sum(HW1-6)+Max(HW1-6)*.5-Min(HW1-6)*.5 期中考 22% (涵蓋期中考前課程內容) 期末考 30% (涵蓋全課程內容) 偶爾點名, 很多次不到的話… 期末成績加總後不會調整 等第之對應由老師與助教於學期末決定 (會和另外一班一起調整等第分布) 根據經驗, 只要作業都有寫有交, 考試考卷每題都有寫不放棄, 就很難被當 會發生什麼事情, 我也不知道.

14 作業 分程式作業 + 手寫作業 程式作業: 每次約1題 手寫作業: 每次4-5題 閱讀作業: 使用Subversion繳交
由四位大學部助教負責(人工)批改 自己思考怎麼產生測試資料也是作業的一部分 手寫作業: 每次4-5題 用手寫的方法做演算法的證明與分析 或者用手寫的方式設計演算法 閱讀作業: 課本或其他英文閱讀材料 可能在考試或作業中出現

15 作業 鼓勵討論 每一題都請註明參考的資料/討論的同學 絕對不能照抄 (請了解之後, 用自己的話寫/自己撰寫程式碼)
例1: 本題參考wikipedia上面的linked list 網頁(網址...) 例2: 本題跟許若漢討論過 例3: 本題參考課本第xxx頁 絕對不能照抄 (請了解之後, 用自己的話寫/自己撰寫程式碼) 抓到抄襲的, 本課程成績為F (當掉)

16 Zero-tolerance政策: 遲交&抄襲
遲交 = 該次作業0分 (但是我們鼓勵你交上來, 助教會幫你批改, 期末可能可以做為少量修正成績用) 作業抄襲(程式或手寫) = 本學期成績為F (不是只有該次0分) 考試作弊 =本學期成績為F 以上均無第二次機會 請注意! 抄襲/作弊 以校規論處. 訊息: 本學期有>=6位助教

17 其他事項 加退選 對這門課的期望? 希望學到什麼? Review C Pointers HW0會在今天出現, 下周四前繳交
要加選的同學, 下課找助教登記 HW0繳交後, 我們會 給你加選代碼 微小的可能: 人數過多, 則我們以本系生優先 對這門課的期望? 希望學到什麼? Review C Pointers

18 記得要做的事情 CEIBA上的e-mail確定收得到 課本趕快買(拿)到 每天睡飽(not in the class), 迎接本學期的挑戰
趕快看HW0怎麼寫, 下星期四要交