|
|
|
General Information
|
|
|
|
|
Tutor: Mark
|
簡裕峰
|
|
|
cyf @
cs.nthu.edu.tw
|
|
|
綜二 734
|
|
|
|
|
|
Tutor: Bite
|
邱聖元
|
|
|
bigbite_saint @
yahoo.com.tw
|
|
|
綜二 734
|
|
|
|
|
|
|
Tutor: Foga
|
劉富翃
|
|
|
g9662587 @
oz.nthu.edu.tw
|
|
|
綜二 734
|
|
|
|
|
|
|
Tutor: Jenny
|
劉向瑄
|
|
|
alien.cis91 @
nctu.edu.tw
|
|
|
綜二 734
|
|
|
|
|
|
|
|
|
Announcement
|
|
Final Exam
Date: June 17, 2008 (Tue)
Time: 10:10—12:10
Scope:
Mainly Lectures 22-26
But should be familiar with
basic
stuffs (Lectures
2-3) and
time
bounds of the
data structures (Lectures
17-21)
|
|
June 14:
|
Solutions for Homework 4 [pdf]
and Homework 5 [pdf]
posted
|
|
June 10:
|
Notes 27 (final-version) [pdf]
posted
(Slides added:
Pages 33 to 45)
(Slides updated: Pages 38 and 39)
Notes 28 [pdf]
still in preparation
|
|
June 03:
|
Notes 26 (full-version) [pdf]
posted
(Slides added:
Pages 21 to 40)
|
|
May 26:
|
Notes 24 [pdf]
updated
(Slides updated:
Pages 9 and 17)
|
|
|
|
Meeting Times:
|
|
|
Tue 1010—1200, Thu 1110—1200
|
|
|
 Course Materials
|
Lecture
|
Topics
|
Files
|
|
References
|
Notes by Prof BF Wang
|
[link]
|
|
0
|
Overview
|
[pdf]
|
|
1
|
Getting Started
|
[pdf]
|
|
2
|
Growth of Function
|
[pdf]
|
|
***
|
Classwork for Lecture 2
|
[pdf]
|
|
3
|
Recurrences
|
[pdf]
|
|
4
|
Heapsort
|
[pdf]
|
|
5
|
Quicksort
|
[pdf]
|
|
***
|
Probability & Expectation
|
[pdf]
|
|
6
|
Sorting in Linear Time
|
[pdf]
|
|
7
|
Lower Bound for Comparison Sort
|
[pdf]
|
|
8
|
Order Statistics
|
[pdf]
|
|
9
|
Dynamic Programming I (Assembly Line,
Memoization)
|
[pdf]
|
|
10
|
Dynamic Programming II (Matrix-Chain Multiplication)
|
[pdf]
|
|
11
|
Dynamic Programming III (Optimal BST)
|
[pdf]
|
|
12
|
Dynamic Programming IV (Longest Common Subsequence)
|
[pdf]
|
|
13
|
Greedy Algorithm
|
[pdf]
|
|
14
|
Amortized Analysis I (Aggregate Method)
|
[pdf]
|
|
15
|
Amortized Analysis II (Accounting
Method, Potential Method)
|
[pdf]
|
|
16
|
Amortized Analysis III (Dynamic Table)
|
[pdf]
|
|
17
|
Binomial Heap
|
[pdf]
|
|
18
|
Fibonacci Heap I (Insert / Find-Min / Union /
Extract-Min)
|
[pdf]
|
|
19
|
Fibonacci Heap II (Decrease-Key / Delete / MaxDeg)
|
[pdf]
|
|
20
|
Data Structures for Disjoint Sets
I (Linked List)
|
[pdf]
|
|
21
|
Data Structures for Disjoint Sets
II (Disjoint-Set Forest)
|
[pdf]
|
|
22
|
Elementary Graph Algorithms I (BFS)
|
[pdf]
|
|
23
|
Elementary Graph Algorithms II (DFS)
|
[pdf]
|
|
24
|
Elementary Graph Algorithms III
(Topological Sort)
|
[pdf]
|
|
25
|
Elementary Graph Algorithms IV
(Strongly Connected)
|
[pdf]
|
|
26
|
Minimum Spanning Tree (Kruskal / Prim /
Borůvka)
|
[pdf]
|
|
27
|
Single-Source Shortest Path (Dijkstra /
DAG / Bellman-Ford)
|
[pdf]
|
|
28
|
All-Pairs Shortest Path (Matrix /
Floyd-Warshall / Johnson )
|
[pdf]
|
 Teaching Plan
|
1
|
Basics
|
Growth of Function, Solving Recurrences
|
|
2
|
Sorting & Order Statistics
|
Heapsort, Quicksort, Bucketsort, Finding
Median
|
|
3
|
Basic Data Structures
|
Red-Black Tree, Interval Tree, Hash Tables
|
|
4
|
Advanced Design & Analysis
|
Dynamic Program, Greedy Algorithm,
Amortization
|
|
5
|
Advanced Data Structures
|
Binomial Heap, Fibonacci Heap, Union-Find
|
|
6
|
Graph Algorithms
|
Topological Sort, MST, Shortest Path, Max
Flow
|
|
7
|
Selected Topics
|
String Matching, NP-complete, Approx Algo
|
Last updated: 10 June 2008
|