|
Instructor: 顏嗣鈞
E-mail: hcyen(_at_)ntu.edu.tw
Time:
9:10-12:00 AM, Tuesday
Place: Room
BL-11 3
Office phone:
(02) 3366 3581
Office hours:
by appointment
TA:
顏玓德
博理館606室
bottlebottle13@gmail.com
or
d02921016@ntu.edu.tw
(02)
33663700 ext 6606
Announcements
-
作業1~4、期
中考、期末考、程式成績登錄(7/4
更新)
-
程式作業繳交情形 (7/2 更新): 如已交但未被登錄，請盡速與助教連絡
bottlebottle13@gmail.com
or
d02921016@ntu.edu.tw
-
期末考解答
-
Final Exam: 9:10 -
12:00 AM, Tuesday, June 21.
-
期末考範圍:
講義
4g.pdf ~ 9.ppt (包括
red-black trees, hashing, priority queues, sorting, disjoint sets,
graphs)
-
Sample final exam:
(Spring
2015) (Spring
2014), (Spring
2010),
(Spring
2007)
(Fall
2004;
Solutions) (Fall
2003 ) (Spring
2003) (Fall
2000)
-
Programming assignment #2:(polygon1;
polygon2;
polygon3) due: 23:59 PM, June
26,
2016
-
Homework # 4:
(Solutions) Due
June 7 (Tuesday)
-
Midterm solution;
成績分佈
-
Homework # 3:
(Solutions) Due May 10 (Tuesday)
-
Programming assignment #1
(input1;
input2): due: 23:59 PM, June 12,
2016
-
Midterm is held on April 19
(Tuesday) at 9:10 in Room BL-113.
-
Sample midterms
(Fall
2000,
Solutions) (Spring
2003 ,
Solutions) (Fall
2003,
Solutions) (Fall
2004) (Spring
2007,
Solutions) (Spring
2010)(Spring
2014)(Spring
2015)
-
Homework # 2:
(Solutions) Due April 12 (Tuesday)
-
Homework # 1:
(Solutions) Due March 22 (Tuesday)
Class Notes:
|
Topics |
| |
|
PRELIMINARIES |
Introduction. Asymptotic Notations. Algorithm Analysis
|
1.ppt
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
4e.pdf
4f.pdf
4g.pdf
|
|
|
HASHING |
Chaining. Open addressing. Collision handling.
|
5.pdf |
|
|
PRIORITY
QUEUES |
Binary heaps. Binomial heaps. Fibonacci heaps. Min-max heaps. Leftist heaps.
Skew heaps.
|
6a.pdf
6b.pdf
6c.pdf
6d.pdf
6e.pdf |
|
|
AMORTIZED
ANALYSIS |
|
4d.pdf |
|
|
SORTING |
Insertion sort. Selection sort. Quicksort. Heapsort. Mergesort. Shellsort.
Lower bound of sorting.
|
7a.ppt
7b.pdf
|
|
|
DISJOINT
SETS |
Set operations. Set representations. Union-find. Path compression.
|
8.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 |
kd-trees
Skip lists
Tries
Dynamic programming
|
|
|
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. |
