Instructor: 顏嗣鈞
Email: hcyen(_at_)ntu.edu.tw
Time:
9:1012:00 AM, Tuesday
Place: Room
BL113
Office phone:
(02) 3366 3581
Office hours:
by appointment
TA:
張以潤 (博理館
606; Email: au3bjp4(_at_)gmail.com )
Announcement

期中考、期末考、作業14成績、程式一、二成績(updated 7/6
10:00 AM) 。

要看期末考卷的同學，請於7/1(三)下午3:30  5:00 間到博理館525室。

Final exam solution

期末考:
6/23 (星期二) : (考試範圍:
講義 8.ppt  21.ppt)

Homework #4: due June 23, 2015

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

Programming Assignment #2:
(Instructions) due: 6/26 (星期五) 23:59 PM (Absolute Deadline)

Midterm solution

補課: 五月三十日(六) 9:10  12:00; 博理113

Homework #3: due May 26, 2015

Programming Assignment #1: (Input
data) (Instructions) due May 12, 2015.

Midterm will be
held on April 28.

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

Homework #2: due April 21, 2015.

Homework #1: due March 31, 2015.

因老師出國開會，April
14 暫停上課， 之後再補課。
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. 23 trees. Btrees. Redblack 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. Minmax 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. Unionfind. 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.
Topdown splay trees, and more 
17.ppt
18.pdf
21.ppt 

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. 