Data Structures, Fall 2016

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.

• 01/23: grade report revised (again on 01/25).
• 01/21: Grade Report available; contact Yih-Kuen Tsay by 5PM 01/23 if you have any question or request.
• 01/03: the final exam of DS 2016 can be found in the old_exams.zip file announced on 11/01.
• 01/03: Suggested solutions for HW#9 avilable.
• 01/03: slides from TA sessions: TA Session #4.
• 12/25: HW#10 due 2017/01/03.
• 12/18: slides for Graphs available.
• 12/12: HW#9 due 12/26.
• 12/12: slides for Hashing and for Balanced Search Trees available.
• 12/05: HW#8 due 12/12.
• 12/05: slides for Heaps available.
• 11/28: HW#7 due 12/05.
• 11/27: slides for Trees (the Implementations part) available.
• 11/21: Suggested solutions for midterm avilable.
• 11/21: slides from TA sessions: TA Session #3.
• 11/21: slides for Trees (the ADT part) available.
• 11/14: slides for Queues available.
• 11/04: slides from TA sessions: TA Session #1, TA Session #2.
• 11/01: HW#6 due 11/21.
• 11/01: old exams.
• 10/31: slides for Algorithm Efficiency and for Sorting available.
• 10/30: HW#5 due 11/14.
• 10/24: slides for Lists: The ADT and Its Uses and for Lists: Implementations available.
• 10/17: HW#4 due 10/24.
• 10/17: Ceiba course site ready; entering via theCeiba main site gets better functionality (as advised by Ceiba developers).
• 10/17: slides for Stacks: The ADT and Its Uses and for Stacks: Implementations available.
• 10/04: HW#3 due 10/17.
• 10/04: HW#2 due 10/11.
• 10/03: slides for Link-Based Implementations along with example programs available.
• 09/26: slides for Review of C++ and for Array-Based Implementations along with example programs available.
• 09/19: HW#1 due 09/26.
• 09/18: slides for Recursion available.
• 09/12: slides for Data Abstraction available.
• 09/12: website announced. This website is the primary source of all up to date course information and syllabus of Data Structures 2016; there is no separate PDF version for the syllabus.

Yih-Kuen Tsay (蔡益坤), NTU IM Dept., 3366-1189, Xtsay@ntu.edu.twX (between the enclosing pair of X's).

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.

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

Carlos Chang (張永叡), Xjake080449@gmail.comX (between the enclosing pair of X's).
Po-Chuan Chien (簡伯銓), Xr04725015@ntu.edu.twX (between the enclosing pair of X's).

• [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.

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/17, 10/31, 11/21, and 12/26.)

• Introduction (1/3 week: 9/12a)
• Data Abstraction [CH: Ch. 1] (2/3 week: 9/12b) [slides]
• Recursion [CH: Ch. 2,5] (1 week: 9/19) [slides]
• C++: A Review [CH: C++ Interludes] (1 week: 09/26a, 10/03a) [slides: Part 1] (other parts are merged to the following two sets of slides)
• Array-Based Implementations [CH: Ch. 3] (.5 week: 09/26b) [slides, example programs]
• Link-Based Implementations [CH: Ch. 4] (.5 week: 10/03b) [slides, example programs]
• Stacks: The ADT and Its Uses [CH: Ch. 6] (1 week: 10/17*) [slides]
• Stacks: Implementations [CH: Ch. 7] (.5 week: 10/24a) [slides]
• Lists [CH: Ch. 8,9] (.5 week: 10/24b) [slides: ADT, Implementations]
• Algorithm Efficiency [CH: Ch. 10] (.5 week: 10/31a*) [slides]
• Sorting and Efficiency [CH: Ch. 11] (.5 week: 10/31b) [slides]
• Midterm (2016/11/07)
• Queues [CH: Ch. 13,14] (1 week: 11/14) [slides: ADT, Implementations]
• Trees [CH: Ch. 15,16] (2 weeks: 11/21*, 11/28) [slides: ADT, Implementations]
• Heaps [CH: Ch. 17] (1 week: 12/05) [slides]
• Hashing [CH: Ch. 18] (1 week: 12/12) [slides]
• Balanced Search Trees [CH: Ch. 19] (1 week: 12/19) [slides]
• Graphs [CH: Ch. 20] (1 weeks: 12/26*) [slides]
• Final (2017/01/09)

• MIT OpenCourseWare: Advanced Data Structures
• Stanford Coursera: Algorithms: Design and Analysis, Part 1
• Mathematical Induction (a Wikipedia page)
• Animated Sorting Algorithms

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