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

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

你需要什麼才能修這門課? 兩樣東西: 附帶條件: 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 1 Graduate TAs + 3 Undergraduate TAs (more to come): lots of office hours 許多的動畫 老師會用冷笑話冷醒睡著的同學 上課你沒有弄懂, 我不會放棄的 你沒聽懂, 我就再講一次 你有問題(沒有笨問題), 我就回答你(如果我會的話) 當我問有沒有聽懂的時候, 請理我一下 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 (蔡欣穆) R316 林均達 (彼得) 姜俊宇 (姜姜) 魏佑霖 余孟桓 下周上課公布 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_13spring [Office hours] 請多加利用. [學生老師/助教] 課程相關的所有問題, 請 寄e-mail給 dsa1@csie.ntu.edu.tw 發文在ptt2上的HsinMu板 Facebook Group http://www.facebook.com/groups/tsai.dsa.ada/ 請來我們的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 機動調整下課時機及長度

課本 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 參考書籍 (1/2) Fundamentals of Data Structures in C, 2nd Edition, 2008 Horowitz, Sahni, and Anderson-Freed

參考書籍 (2/2) Data Structures and Algorithms Made Easy, Second Edition, 2011, CareerMonk Publications, by Karumanchi

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

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

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

作業: 期限&遲交&折扣 用手寫的作業無法遲交 (上課前必須繳交) 用svn繳交的作業: (包含程式作業和手寫部分) 可以把手寫部分掃描成電子檔 (pdf), 即可遲交 有一天的遲交緩衝期 分數: 以秒計打折扣. 例如慢3小時交, 則只能得1-3600*3/86400=87.5%的分數 詳細規則會出現在每次作業的最前面

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

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

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