資料結構與程式設計

Data Structures and Programming

Spring 2010

　

Instructor:    顏嗣鈞

Class:    Monday:  9:10-12 AM,   Room BL-112 (博理館)

Office:    BL-525 (博理館)

Phone:    3366-3581

E-mail:     yen@cc.ee.ntu.edu.tw 

Office Hours:    By appointment 
Class Web page: http://cc.ee.ntu.edu.tw/~yen/courses/ds10.html

TA: 廖強棋  博理603 chiangchi@arbor.ee.ntu.edu.tw

PREREQUISITES: Familiarity in C, C++, or JAVA. 

　　

ANNOUNCEMENTS:

 

n          作業一二、程式一、期中考、期末考成績 (Updated 3:30 PM, 7/5)

如成績有問題或要看期末考考卷，請於星期五(7/2) 下午5:00~6:00 到博理館603 找助教，或另外和助教以E-mail 約定時間(最遲星期一下午五點前完成看考卷)

 

n         Final exam will be held on June 21.

n          考試範圍: Chapter 6: 213-225;  229-250; Chapter 8: 315-331;  Chapter 11: 491-513;  Chapter 12: 525-534; 540-549,  and class notes

n          Sample final exam: (Spring 2007)  (Fall 2004: Final Exam; Solutions) (Fall 2003:  Final Exam; Solutions ) (Spring 2003) (Fall 2000: exam, solution)

 

n          Programming assignments  (Instructions)

Assignment  # 1 (input data)  (pdf) (ps)  due:  May 17 (Monday)

Assignment # 2:  (description) due:  June 27 (Sunday; 23:59 PM)

– strict

 

n          Homework # 1:  (Solutions) Due: April 12 (Monday)

n          Homework # 2:  (Solutions) Due: May  24 (Monday)

 

n          Midterm exam will be held on April 26. (midterm solution)

n          考試範圍: Chapter 2: 43-63;  Chapter 3: 71-74, 83-107;  Chapter 4: 113-159   Chapter 12: 517-525 and class notes

n          Sample midterms (Fall 2000, Solutions) (Spring 2003) (Fall 2003, Solutions) (Fall 2004) (Spring 2007, Solutions) 

TOPICS:

lPRELIMINARIES: ( 1 ) Introduction, (2) Asymptotic Notations, (3) Algorithm Analysis.

lABSTRACT DATA TYPES: (4) Stacks, Queues, Lists, List operations, List representations, List traversals, Doubly linked lists.

lTREES: (5, 6)   Tree operations, Tree representations, Tree traversals, Threaded trees, Binary trees, (7) AVL trees, (8) (9) Splay trees, (10) 2-3 trees, B-trees, Red-black trees, Binomial trees,  (11) AA-trees and more.

l HASHING: (25)  Chaining, Open addressing, Collision handling.

lPRIORITY QUEUES:     (12) Binary heaps. (13) Binomial heaps. (14) Fibonacci heaps. (15a,  15b) Leftist heaps,  Skew heaps,  (16) Min-max heaps.. (17) Pairing heaps

lAMORTIZED ANALYSIS   (18, 19, 20) 

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

lDISJOINT SETS:  (21, 22)  Set operations, Set representations, Union-find, Path compression.

lGRAPHS: Graph operations, Graph representations, Basic graph algorithms, Algorithm design techniques. 

l ADVANCED DATA STRUCTURES:  Tries,  (24) Skip lists (23),   Treaps, Top-down splay trees.

TEXTBOOK 

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

Addison-Wesley, 2006 

 

COURSE REQUIREMENTS: There will be homework/programming assignments, one midterm exam, and a final exam. The weightings within the semester grade will be: 

　

            Homework + Programming Assignment 30%

            Midterm35%

            Final exam 35%

　

HOMEWORK: Only homework/prog. assignments turned in by the due date is guaranteed to be graded. Any special circumstances that cause difficulty in meeting the deadlines should be brought to the attention of the instructor in advance. 

　

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.