Hsu-Chun Yen's Homepage

			Electrical Engineering

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

資料結構

Data Structures

Fall 2020

Instructor: 顏嗣鈞

E-mail:  hcyen(_at_)ntu.edu.tw

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

Place: Room BL-113

Office phone: (02) 3366 3581

Office hours: by appointment

TA:

(1) 王璲博理館606室; (02) 33663700 ext 6606 ; D07921012@ntu.edu.tw

(2) 王思涵博理館606室; (02) 33663700 ext 6606 ; stellawang18@gmail.com

(3) 余若萱博理館606室; (02) 33663700 ext 6606 ; q8611027@gmail.com

Announcements

成績登錄 updated 1/25 1:00 AM
期末考成績將於1/21(四) 9AM 前公佈在此，如要看考卷，請於 1/21下午1:30 - 3:00 到計算機及資訊網路中心二樓220
Final Exam: (Solutions) Monday 1/11, 9:10 - 12:00 (期末考範圍: 講義標記紅色部分)
Office hours for final exam:

王思涵博理館606室 1/7（星期四）上午 10:00 - 12:00

王璲博理館606室 1/7（星期四）下午 2:00 - 4:00

余若萱博理館606室 1/8（星期五）上午 10:00 - 12:00

顏嗣鈞計算機及資訊網路中心二樓220 1/6 (三) 上午 9:30 - 12:00
Sample final exam: (Fall 2019) (Spring 2019) (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 Jan. 4, 2021
Programming Assignment #2 (password file) (due: 1/13, 2021)

Note: instructions on how to prepare / submit files for the assignment

Test data: list of hash values to be searched (including some that do not have matching passwords)
Homework #3: (Solutions 王璲) due Dec. 7, 2020
Programming Assignment #1 (due: 12/7) 繳交說明; input (zip file) ; list.txt

Introduction to PageRank; Additional note
Midterm Exam (Solutions): Monday 11/9, 9:10 - 12:00 (範圍: 到Splay trees (included))
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) (Spring 2019) (Fall 2019)
Office hours for midterm:

王璲博理館606室 11/4（星期三）下午 3-5

王思涵博理館606室 11/5（星期四）下午 2-4

余若萱博理館606室 11/6（星期五）上午 10-12

顏嗣鈞計算機及資訊網路中心二樓220 11/6 (五) 2:30 - 5:00 PM
Homework #2: (Solutions 余若萱) due Oct. 26, 2020
Homework #1: (Solutions 王璲) due Oct. 12, 2020 博理館525室拿取
9/21 開始上課教室改到博理113

Class Notes:

Topics
	PRELIMINARIES	Introduction. Asymptotic Notations. Algorithm Analysis.	Introduction Algorithm analysis
	ELEMENTARY STRUCTURES	Arrays vs. Pointers. Abstract data types. Stacks. Queues. Lists. Tree operations. Tree representations. Tree traversals. Binary trees.	Lists, Stacks, and Queues Trees
	SEARCH TREES, BALANCED SEARCH TREES	AVL trees. 2-3-4 trees. B-trees. Red-black trees. Binomial trees. Splay trees. Top-down splay trees. Skip lists, and more.	AVL Trees Splay Trees Amortized Analysis of Splay Trees 2-3 & 2-3-4 Trees Red-black Trees and AA-Trees Range Searching
	HEAPS	Priority queues. Binary heaps. Binomial heaps. Fibonacci heaps. Min-max heaps. Leftist heaps. Skew heaps.	Priority Queue, Binary Heaps Binomial Heaps Fibonacci Heaps Leftist Heaps and Skew Heaps
	HASHING	Hash tables. Chaining. Open addressing. Collision handling. Universal hashing. Perfect hashing.	Hashing (期末考Universal & Perfect Hashing 不考)
	DISJOINT SET UNION/FIND	Set operations. Set representations. Union-find. Path compression.	Disjoint Set Union & Find
	SORTING	Insertion sort. Selection sort. Quicksort. Heapsort. Mergesort. Shellsort. Lower bound of sorting.	Sorting
	RANDOMIZED DATA STRUCTURES	Treaps and Skip Lists	Treaps Skip Lists
	GRAPH DATA STRUCTURES/ALGORITHMS	Graph operations. Graph representations. Basic graph algorithms. Algorithm design techniques.	Graph.ppt
	SUPPLEMENTARY MATERIALS: AMORTIZED ANALYSIS	Amortized complexity. Potential method.	Amortized analysis

Textbook: There is no required textbook for this class. There are some relevant and useful books and materials:

Mark Allen Weiss, Data Structures and Algorithm Analysis in C++. (3rd or 4th Ed.) Addison-Wesley, 2006/2013
Peter Brass, Advanced Data Structures, Cambridge, 2008; https://doi.org/10.1017/CBO9780511800191

http://www-cs.ccny.cuny.edu/~peter/dstest.html
D. Sheehy, Data Structures

https://donsheehy.github.io/datastructures/
Data Structure Visualizations

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Grading:

Homework/Prog. Assignment(s): 20-30%
Midterm exam: 30-40%
Final exam: 30-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.