Yih-Kuen Tsay's Wiki @ IM.NTU

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======Data Structures, Fall 2017======
This is an introductory course on data structures, concerning the various ways of organizing data so that the data can be accessed and manipulated efficiently by an application. 
A central concept is that of an abstract data type, which is a collection of data and a set of operations on the data.
The course therefore focuses on the fundamental concepts, techniques, and tools for the design and implementation of abstract data types, following the teaching of object-oriented design and programming for computer problem solving.

=====Announcements=====
  * 01/22: Grade Report available; contact Yih-Kuen Tsay by 5PM 01/23 if you have any question or request.
  * 01/03: {{courses:ds2017:ds2017_hw9s.pptx|Suggested solutions for HW#9}} avilable.
  * 01/03: slides from TA sessions: {{courses:ds2017:DS2017_TA4.pptx|TA Session #4}}.
  * 12/18: slides for Graphs available.
  * 12/18: {{courses:ds2017:hw10.pdf|HW#10}} due 2018/01/02.
  * 12/11: {{courses:ds2017:hw9.pdf|HW#9}} due 12/25.
  * 12/11: slides for Balanced Search Trees available.
  * 12/04: slides for Dictionaries and for Hashing available.
  * 11/27: {{courses:ds2017:hw8.pdf|HW#8}} due 12/04.
  * 11/20: slides from TA sessions: {{courses:ds2017:DS2017_TA3.pptx|TA Session #3}}.
  * 11/20: slides for Heaps available.
  * 11/20: {{courses:ds2017:ds2017mid_s.pdf|Suggested solutions for midterm problems}} avilable.
  * 11/13: {{courses:ds2017:hw7.pdf|HW#7}} due 11/20.
  * 11/13: slides for Trees (Terminology and ADTs) and for Tree Implementations available.
  * 10/30: slides from TA sessions: {{courses:ds2017:DS2017_TA1.pptx|TA Session #1}}, {{courses:ds2017:DS2017_TA2.pptx|TA Session #2}}.
  * 10/30: {{courses:ds2017:hw6.pdf|HW#6}} due 11/13.
  * 10/30: slides for Queues available.
  * 10/23: {{courses:ds2017:old_exams.zip|old exams}}.
  * 10/23: slides for Algorithm Efficiency and for Sorting available.
  * 10/16: {{courses:ds2017:hw5.pdf|HW#5}} due 10/30.
  * 10/16: slides for Lists: The ADT and Its Uses and for Lists: Implementations available.
  * 10/16: {{courses:ds2017:hw4.pdf|HW#4}} due 10/23.
  * 10/16: Ceiba course site (ID: 1061ds2017) ready; entering via the{{https://ceiba.ntu.edu.tw|Ceiba main site}} gets better functionality (as advised by Ceiba developers).
  * 10/02: {{courses:ds2017:hw3.pdf|HW#3}} due 10/16.
  * 10/02: slides for Stacks: The ADT and Its Uses and for Stacks: Implementations available  
  * 09/29: slides for Link-Based Implementations along with example programs available.
  * 09/25: {{courses:ds2017:hw2.pdf|HW#2}} due 10/02.
  * 09/25: slides for Review of C++ and for Array-Based Implementations along with example programs available.
  * 09/18: {{courses:ds2017:hw1.pdf|HW#1}} due 09/25.
  * 09/18: slides for Recursion available.
  * 09/11: slides for Data Abstraction available.
  * 09/08: website announced. This website is the primary source of all up to date course information and syllabus of Data Structures 2017; there is no separate PDF version for the syllabus.
=====Instructor=====
[[http://im.ntu.edu.tw/~tsay/|Yih-Kuen Tsay (蔡益坤)]], NTU IM Dept.,
3366-1189, ''Xtsay@ntu.edu.twX'' (between the enclosing pair of X's).

=====Lectures=====
Monday 2:20~5:20PM, Room 103, Management Building 1. \\ TA
sessions will be scheduled prior to some of the class meetings between 1:20
and 2:10PM; see the course schedule below.

=====Office Hours=====
Tuesday 1:30~2:00PM, Wednesday 1:30~2:00PM, or by appointment, Room 1108,
Management Building 2.

=====TAs=====
Carlos Chang (張永叡), ''Xjake080449@gmail.comX'' (between the enclosing pair of X's). \\
Hung-Chih Chen (陳泓志), ''Xr06725012@ntu.edu.twX'' (between the enclosing pair of X's).

=====Textbooks=====
  * [CH] F.M. Carrano and T. Henry, "Data Abstraction and Problem Solving with C++: Walls and Mirrors," 6th Edition, Pearson, 2013 (International Edition).
  * Supplementary readings.

=====Syllabus/Schedule (with links to notes/slides)=====
The course will cover most of the main textbook [CH] in essentially the same order, plus supplementary readings. (Note: a TA session will precede a class meeting whose date is marked with an *. There are four TA sessions on 10/16, 10/30, 11/20, and 12/25.)
  *Introduction (1/3 week: 9/11a) 
  *Data Abstraction [CH: Ch. 1] (2/3 week: 9/11b) [{{courses:ds2017:DS2017_01_DataAbstraction.pptx|slides}}]
  *Recursion [CH: Ch. 2,5] (1 week: 9/18) [{{courses:ds2017:DS2017_02_Recursion.pptx|slides}}]
  *C++: A Review [CH: C++ Interludes] (1 week: 09/25a, 09/30a)  [slides: {{courses:ds2017:DS2017_03_CPP1.pdf|Part 1}}] (other parts are merged to the following two sets of slides)
  *Array-Based Implementations [CH: Ch. 3] (.5 week: 09/25b) [{{courses:ds2017:DS2017_04_ArrayBag.pptx|slides}}, {{courses:ds2017:DS2017_04_exampleprograms.zip|example programs}}]
  *Link-Based Implementations [CH: Ch. 4] (.5 week: 09/30b) [{{courses:ds2017:DS2017_05_LinkedBag.pptx|slides}}, {{courses:ds2017:DS2017_05_exampleprograms.zip|example programs}}]
  *Stacks: The ADT and Its Uses [CH: Ch. 6] (1 week: 10/02) [{{courses:ds2017:DS2017_06a_Stacks.pptx|slides}}]
  *Stacks: Implementations [CH: Ch. 7] (.5 week: 10/16a*) [{{courses:ds2017:DS2017_06b_StacksImplementations.pptx|slides}}]
  *Lists [CH: Ch. 8,9] (.5 week: 10/16b) [slides: {{courses:ds2017:DS2017_07a_Lists.pptx|ADT}}, {{courses:ds2017:DS2017_07b_ListsImplementations.pptx|Implementations}}]
  * Algorithm Efficiency [CH: Ch. 10] (.5 week: 10/23a)  [{{courses:ds2017:DS2017_08_AlgorithmEfficiency.pptx|slides}}]
  *Sorting and Efficiency [CH: Ch. 11] (.5 week: 10/23b)   [{{courses:ds2017:DS2017_09_SortingAndEfficiency.pptx|slides}}]
  *Queues [CH: Ch. 13,14] (1 week: 10/30*) [slides: {{courses:ds2017:DS2017_10a_Queues.pptx|ADT}}, {{courses:ds2017:DS2017_10b_QueuesImplementations.pptx|Implementations}}]
  * **Midterm** (**2017/11/06**)
  *Trees [CH: Ch. 15,16] (2 weeks: 11/13, 11/20*) [slides: {{courses:ds2017:DS2017_11a_Trees.pptx|ADT}}, {{courses:ds2017:DS2017_11b_TreesImplementations.pptx|Implementations}}]
  *Heaps [CH: Ch. 17] (1 week: 11/27) [{{courses:ds2017:DS2017_12_Heaps.pptx|slides}}]
  *Dictionaries [CH: Ch. 18] (.5 week: 12/04a)  [{{courses:ds2017:DS2017_13_Dictionaries.pptx|slides}}]
  *Hashing [CH: Ch. 18] (.5 week: 12/04b)  [{{courses:ds2017:DS2017_14_Hashing.pptx|slides}}]
  *Balanced Search Trees [CH: Ch. 19] (1.5 weeks: 12/11, 12/18a*) [{{courses:ds2017:DS2017_15_BalancedSearchTrees.pptx|slides}}]
  *Graphs [CH: Ch. 20] (1.5 weeks: 12/18b, 12/25)  [{{courses:ds2017:DS2017_16_Graphs.pptx|slides}}]
  * **Final** (**2018/01/08**)
=====References=====
  * MIT OpenCourseWare: [[http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/|Advanced Data Structures]]
  * Stanford Coursera: [[https://www.coursera.org/course/algo|Algorithms: Design and Analysis, Part 1]]
  * [[http://en.wikipedia.org/wiki/Mathematical_induction|Mathematical Induction]] (a Wikipedia page)
  * [[http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html|Animated Sorting Algorithms]]

=====Grading=====
Homework (including programming exercises/projects) 30%, Participation 10%, Midterm 30%, Final 30%.