Instructor:

Prof. 黃鐘揚 Chung-Yang (Ric) Huang, Department of Electrical Engineering
Office hours: Stop by or (better) by e-mail appointment
Office: EE Building II, Room 444
Phone: 3366-3644
Email: ric@cc.ee.ntu.edu.tw

TA:

Name: 徐常紘 吳政穎 吳濟安

Email: r97921023 at ntu.edu.tw d97943038 at ntu.edu.tw gro070916 at yahoo.com.tw

Office hours: By e-mail appointments (Title started with [DSnP])

Time:

Wednesday 9:10pm – 12:00pm

Location:

Ming-Da Building Room 205

Objectives:

In this class, you will learn the importance of various data structures, and how to cleverly design and utilize them in object oriented programming (C++). You will also be guided to work on Linux workstations.

Course Description:

The lectures of this class are divided into 4 parts:

(1) Introduction: Through in-depth discussion, the students are guided to comprehend the true meaning of why they should learn data structure and eventually appreciate its importance. Basic knowledge about Linux workstations will also be covered so that the students can survive on the later homework and project assignments.

(2) Polishing your programming skill: Afraid of writing programs? Or having trouble in managing large program assignment? Try to answer this basic C++ question: “what’s the difference between object and pointer type of variables?” In this part of the class we will first review the rationale of how the different C++ constructs are defined, followed by some basic software engineering guidance, and concluded with a memory management implementation.

(3) Data structure revisited: You may have learned about various types of data structures but you may not know when and how to use them wisely. We will look into the implementation details of various abstract data types, from “linked list”, “dynamic array”, “set and map”, “tree and graph”, to “hash and cache”. You will have the chance to create you own version of the above data types in C++ template classes.

(4) Class project: The topic for the class project may vary from year to year. Here’s what we did last year: “Binary Decision Diagram (BDD)” is a compact and canonical representation of Boolean functions. It has been widely used in various fields like logic synthesis and verification. Its implementation includes the utilization of “graph”, “hash”, “cache” and “dynamic array”, etc. It also requires the understanding of memory management and familiarity of recursive algorithms. Therefore, it serves a very good topic to conclude this class as the final project.

Grading (may subject to change):

· Homework 60%

· Final project 40%

· Bonus TBD

The final grades are subject to linear adjustment. Instructor will determine the mid-point and standard deviation.

Required textbook:

1. None, but you are encouraged to use some data structure or programming textbook as references.

2. Class slides: Please download and/or print out for yourself.

3. Referenced papers & handouts

Prerequisites:

1. 程式設計 (Computer Programming in C++)

Links:

1. Class website: http://cc.ee.ntu.edu.tw/~ric/teaching/DataStructureProgramming/latest/

2. BBS discussion board: telnet://ptt.cc --> EE_DSnP