Hsu-Chun Yen's Homepage

			Electrical Engineering

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

資料結構與程式設計

Data Structures and Programming

Spring 2019

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: (1)顏玓德博理館606室 bottlebottle13@gmail.com

(02) 33663700 ext 6606

(2) 陳與賢電機二館449 chenuxian@gmail.com

Announcements

成績登錄 (last updated 6/30)
可於6月26日(三) 3:00-5:00 PM 前來計算機及資訊網路中心220室看期末考考卷成績。
Final Exam (Solution): 6/18 (Tue) 9:10- 12:00

Office hours for Final:

顏玓德博理館606室 6/13 (四) 2:00 - 5:00 PM

陳與賢電機二館449 6/14 (五) 2:00 - 5:00 PM

顏嗣鈞計算機及資訊網路中心二樓220 6/17 (一) 2:00 - 4:30 PM

Sample final exam: (Spring 2018) (Spring 2017) (Spring 2016) (Spring 2015) (Spring 2014), (Spring 2010), (Spring 2007) (Fall 2004; Solutions) (Fall 2003 ) (Spring 2003) (Fall 2000)
Homework #4: (Solutions) due June 4, 2019
Programming Assignment #2; Note; baboon.ascii coins.ascii dragon.ascii(Due: June 14, 3PM)
Homework #3: (Solutions) due May 14, 2019 (評分有問題請找陳與賢助教)
Midterm Exam (Solutions): Tuesday 4/16, 9:10 - 12:00
Office hours for midterm:

顏玓德博理館606室 4/11 (四) 2:00 - 4:00 PM

陳與賢電機二館449 4/12 (五) 10:00 - 12:00 AM

顏嗣鈞計算機及資訊網路中心二樓220 4/15 (一) 2:00 - 4:00 PM

Sample midterms (Fall 2000, Solutions) (Spring 2003 , Solutions) (Fall 2003, Solutions) (Fall 2004) (Spring 2007, Solutions) (Spring 2010)(Spring 2014)(Spring 2015)(Spring 2016) (Spring 2017) (Spring 2018)
Programming Assignment #1; Note; input.txt; (ref)output.txt (Due: May 17, 3PM)
Homework #2: (Solutions) due April 9, 2019 (評分有問題請找顏玓德助教)
Homework #1: (Solutions) due March 19, 2019 (評分有問題請找顏玓德助教)
3/5 (二) 因為老師早上8:40-9:10 要參加校內會議，上課時間改由 9:20 開始。

Class Notes:

Topics
	PRELIMINARIES	Introduction. Asymptotic Notations. Algorithm Analysis	1.pdf 2.pdf
	LISTS, STACKS, and QUEUES	Abstract data types. Stacks. Queues. Lists. List operations. List representations. List traversals. Doubly linked lists.	3.pdf
	TREES:	Tree operations. Tree representations. Tree traversals. Threaded trees. Binary trees. AVL trees. 2-3-4 trees. B-trees. Red-black trees. Binomial trees. Splay trees, and more.	4a.pdf 4b.pdf 4c.pdf 4d.pdf 4e.pdf
	HASHING	Chaining. Open addressing. Collision handling.	8.pdf Universal/Perfact Hashing
	PRIORITY QUEUES	Binary heaps. Binomial heaps. Fibonacci heaps. Min-max heaps. Leftist heaps. Skew heaps.	5a.pdf 5b.pdf 5c.pdf 5d.pdf
	AMORTIZED ANALYSIS		4f.pdf 4g.pdf Skew heap Additional Examples
	SORTING	Insertion sort. Selection sort. Quicksort. Heapsort. Mergesort. Shellsort. Lower bound of sorting.	6.ppt
	DISJOINT SETS	Set operations. Set representations. Union-find. Path compression.	7.pdf
	GRAPHS	Graph operations. Graph representations. Basic graph algorithms. Algorithm design techniques	9.ppt
	ADVANCED DATA STRUCTURES	Tries. Skip lists. Treaps. Top-down splay trees, and more	Skip lists Pairing Heaps

Textbook:

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

Addison-Wesley, 2006/2013

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.