|
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:
(1)顏玓德 博理館606室
bottlebottle13@gmail.com
(02)
33663700 ext 6606
(2)謝宗宏
博理館606室
r06921038@ntu.edu.tw
(02)
33663700 ext 6606
Announcements
-
期末考成績，可於七月九日(一)
10:00-11:30 前來計算機及資訊網路中心220室看考卷。如有問題請聯絡 (期中考
、期末考:顏嗣鈞) (作業一、三、程式二:謝宗宏) (作業二、四、程式一: 顏玓德)
-
成績登錄
如有問題請聯絡 (期中考:顏嗣鈞) (作業一:謝宗宏) (作業二、程式一: 顏玓德)
-
期末考 (Solutions) 6月26日 (二) 9:10 - 12:00; 範圍: 4c-4g; 5;
6a-6d; 7; 8 (不包括 union/find 的 amortized 分析); 9 (不包括 Bellman-Ford 演算法)
-
Instructor's
office hours for
期末考: 6/21(四) 3:00 ~ 5:00PM or 6/25(一) 3:00 ~ 5:00PM ，計算機及資訊網路中心220室
-
Homework #4
(更新):
due June 19, 2018
-
Programming Assignment #2: due:
June 25, 2018
程式繳交中文說明 (Test
case);
程式輸入:
tree.txt
-
Sample final exam:
(Spring
2017) (Spring
2016) (Spring
2015) (Spring
2014), (Spring
2010),
(Spring
2007)
(Fall
2004;
Solutions) (Fall
2003 ) (Spring
2003) (Fall
2000)
-
Homework #3
(Solutions):
due May 29, 2018
-
Programming Assignment #1: due:
May 27, 2018 (A brief intro. to PageRank)
程式繳交中英文說明(5/14更新)。 程式輸入:
Web pages;
list.txt
-
期中考(Solutions): 五月一日 (二) 9:10 - 12:00
(範圍: 講義1~4b)
Instructor's
office hours for midterm:
4/30(一) 10:00 ~ 11:45AM or 2:30 ~ 3:30 PM ，計算機及資訊網路中心220室
-
Homework #2
(Solutions):
due April 24, 2018
-
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)
-
Homework #1
(Solutions):
due March 27, 2018
-
三月六日(二)老師因為公務需至校外開會，停課一次。
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
3+.ppt |
|
|
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.
|
7.ppt |
|
|
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 |
Skip lists
Pairing Heaps
Tries |
|
|
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. |
