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 2015======
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=====
  * 12/07: slides for Trees (the ADT part) available.
  * 11/30: {{courses:ds2015:hw7.pdf|HW#7}} due 12/07.
  * 11/30: slides for Queues available.
  * 11/23: slides for Algorithms Efficiency and for Sorting available (revised 11/29).
  * 11/21: slides for Lists (the ADT part) available.
  * 11/19: {{courses:ds2015:hw5.pdf|HW#5}} due 11/30.
  * 11/16: slides for Stacks: Implementations available (revised 11/17).
  * 11/07: slides from TA sessions: {{courses:ds2015:DS2015_TA2.pdf|TA Session #2}}.
  * 11/02: {{courses:ds2015:hw6.pdf|HW#6}} due 11/16; HW#5 will be given shortly.
  * 11/02: slides for Stacks: The ADT and Its Uses available.
  * 10/27: reminder: there will be a TA session on 11/02.
  * 10/27: slides for lectures on 10/19 and 10/26 revised.
  * 10/26: {{courses:ds2015:hw4.pdf|HW#4}} due 11/02.
  * 10/26: slides for Link-Based Implementations available.
  * 10/19: {{courses:ds2015:hw3.pdf|HW#3}} due 10/26.
  * 10/13: slides from TA sessions: {{courses:ds2015:DS2015_TA1.pdf|TA Session #1}}.
  * 10/11: slides for Advanced Constructs of C++ and for Array-Based Implementations along with example programs available.
  * 10/11: {{courses:ds2015:hw2.pdf|HW#2}} due 10/19.
  * 10/05: slides for Recursion available.
  * 09/21: {{courses:ds2015:hw1.pdf|HW#1}} due 10/05.
  * 09/21: slides for Data Abstraction available.
  * 09/14: this website announced.

=====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).\\
With guest lectures by Prof. Chien Chin Chen and Prof. Ling-Chieh Kung.

=====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=====
Passion Tsai (蔡培暄), ''Xpassion13920@gmail.comX'' (between the enclosing pair of X's). \\
Po-Chuan Chien (簡伯銓), ''Xr04725015@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/12, 11/02, 11/30, and 12/28.)
  *Introduction (.5 week: 9/14a) 
  *Data Abstraction [CH: Ch. 1] (1 week: 9/14b, 9/21a) [{{courses:ds2015:DS2015_01_DataAbstraction.pptx|slides}}]
  *Recursion [CH: Ch. 2,5] (1.5 weeks: 9/21b, 10/05) [{{courses:ds2015:DS2015_02_Recursion.pptx|slides}}]
  *C++: Advanced Constructs [CH: C++ Interludes] (2 weeks: 10/12*, 10/19b, 10/26b)  [slides: {{courses:ds2015:DS2015_03_CPP1.pdf|Part 1}}, {{courses:ds2015:DS2015_04b_CPP2.pdf|Part 2}}, {{courses:ds2015:DS2015_05b_CPP3.pdf|Part 3}}] 
  *Array-Based Implementations [CH: Ch. 3] (.5 week: 10/19a) [{{courses:ds2015:DS2015_04a_ArrayBag.pdf|slides}}, {{courses:ds2015:ds2015_04_exampleprograms.zip|example programs}}]
  *Link-Based Implementations [CH: Ch. 4] (.5 week: 10/26a) [{{courses:ds2015:DS2015_05a_LinkedBag.pdf|slides}}, {{courses:ds2015:ds2015_05_exampleprograms.zip|example programs}}]
  *Stacks: The ADT and Its Uses [CH: Ch. 6] (1 week: 11/02*) [{{courses:ds2015:DS2015_06a_Stacks.pptx|slides}}]
  * **Midterm** (**2015/11/09**)
  *Stacks: Implementations [CH: Ch. 7] (.5 week: 11/16a) [{{courses:ds2015:DS2015_06b_StacksImplementations.pptx|slides}}]
  *Lists [CH: Ch. 8,9] (.5 week: 11/16b) [slides: {{courses:ds2015:DS2015_07a_Lists.pptx|ADT}}, {{courses:ds2015:DS2015_07b_ListsImplementations.pptx|Implementations}}]
  *Algorithm Efficiency [CH: Ch. 10] (.5 week: 11/23a)  [{{courses:ds2015:DS2015_08_AlgorithmEfficiency.pptx|slides}}]
  *Sorting and Efficiency [CH: Ch. 11] (.5 week: 11/23b)   [{{courses:ds2015:DS2015_09_SortingAndEfficiency.pptx|slides}}]
  *Queues [CH: Ch. 13,14] (1 week: 11/30*) [slides: {{courses:ds2015:DS2015_10a_Queues.pptx|ADT}}, {{courses:ds2015:DS2015_10b_QueuesImplementations.pptx|Implementations}}]
  *Trees [CH: Ch. 15,16] (2 weeks: 12/07, 12/14) [slides: {{courses:ds2015:DS2015_11a_Trees.pptx|ADT}}, {{courses:ds2015:DS2015_11b_TreesImplementations.pptx|Implementations}}]
  *Heaps [CH: Ch. 17] (1 week: 12/21) 
  *Balanced Search Trees [CH: Ch. 19] (1 week: 12/28*) 
  *Graphs [CH: Ch. 20] (1 week: 2016/01/04) 
  * **Final** (**2016/01/11**)
=====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) 30%, Participation 10%, Midterm 30%, Final 30%.
Yih-Kuen Tsay's Wiki @ IM.NTU

User Tools

Site Tools

Page Tools
