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

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

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

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

課程特色 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

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

教學團隊 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(薛祐婷) E-mail: dsa1@csie.ntu.edu.tw All members of the teaching team will receive e-mails sent to this address.

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

上課時間及地點 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 機動調整下課時機及長度

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

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

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

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

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

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

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

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

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