Electrical Engineering
 
Welcome Biography Research Teaching Publications Awards
Lab Professional Activities Research Projects Links
 
 

資料結構與程式設計

Data Structures and Programming

Spring 2015

 

Instructor: 顏嗣鈞
E-mail:  hcyen(_at_)ntu.edu.tw

Time:  9:10-12:00 AM, Tuesday

Place: Room BL-113

Office phone: (02) 3366 3581

Office hours: by appointment

TA: 張以潤 (博理館 606; Email: au3bjp4(_at_)gmail.com )

     


Announcement


Class Notes:

 

Topics

    PRELIMINARIES Introduction.  Asymptotic Notations. Algorithm Analysis 1.ppt 2.ppt
3.ppt
 
  LISTS, STACKS, and QUEUES

Abstract data types. Stacks. Queues. Lists. List operations. List representations. List traversals. Doubly linked lists.

4.ppt

  TREES:

Tree operations. Tree representations. Tree traversals. Threaded trees. Binary trees. AVL trees. 2-3 trees. B-trees. Red-black trees. Binomial trees. Splay trees, and more.

5.ppt

6.ppt

7.ppt

8.ppt

8a.pdf

8b.ppt

9.ppt

 

  HASHING

Chaining. Open addressing. Collision handling.

20.ppt 
  PRIORITY QUEUES

Binary heaps. Binomial heaps. Fibonacci heaps. Min-max heaps. Leftist heaps. Skew heaps.

10.ppt

11.ppt

12.ppt

13.ppt

14.ppt

 

  AMORTIZED ANALYSIS    
  SORTING

Insertion sort. Selection sort. Quicksort. Heapsort. Mergesort. Shellsort. Lower bound of sorting.

19.ppt
DISJOINT SETS

Set operations. Set representations. Union-find. Path compression.

15.ppt

16.pdf

  GRAPHS

Graph operations. Graph representations. Basic graph algorithms. Algorithm design techniques 

22.ppt
ADVANCED DATA STRUCTURES Tries.   Skip lists.   Treaps. Top-down splay trees, and more 17.ppt

18.pdf

21.ppt

 

 

 

Textbook:

  • Mark Allen Weiss, Data Structures and Algorithm Analysis in C++. (3rd Ed.)

    Addison-Wesley, 2006 


Grading:  

  • Homework/Prog. Assignments: 25-30%

  • Midterm exam: 35-40%

  • Final exam:  35-40% 

 

CHEATING: With the exception of group assignments, the work (including homework, programming assignments, tests) must be the result of your individual effort. This implies that one student should never have in his/her possession a copy of all or part of another student's homework. It is your responsibility to protect your work from unauthorized access. Academic dishonesty has no place in a university, in particular, in NTUEE. It wastes our time and yours, and it is unfair to the majority of students. Any form of cheating will automatically result in a failing grade in the course and will be reported to the Dean's office.

.