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; Email: au3bjp4(_at_)gmail.com )
Announcement
-
期中考、期末考、作業1-4成績、程式一、二成績(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. 2-3 trees. B-trees. Red-black 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. Min-max 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. Union-find. 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.
Top-down 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. |