|
|
|
General Information
|
|
|
|
Lecturer:
|
Wing-Kai
Hon
|
韓永楷
|
|
|
wkhon @
cs.nthu.edu.tw / EECS 741
|
|
|
Consultation
hour: 9—10am, Monday
|
|
Tutors:
|
Frank
|
邱聖元
|
|
|
bigbite @
gmail.com / 綜二734
|
|
|
Consultation
hour: 2—3pm, Thursday
|
|
|
Wisely
|
古宗翰
|
|
|
wiselyku @
gmail.com / 綜二717
|
|
|
Consultation
hour: 9—10am, Friday
|
|
|
Foga
|
劉富翃
|
|
|
g9662587 @
oz.nthu.edu.tw / 綜二734
|
|
|
Consultation
hour: 2—3pm, Monday
|
|
|
Jenny
|
劉向瑄
|
|
|
g9662647 @
oz.nthu.edu.tw / 綜二734
|
|
|
Consultation
hour: 2—3pm, Wednesday
|
|
|
|
Announcement
|
|
|
|
Final Exam
Time: Jun 23,
1010—1240
Scope: Notes 17—24, 26, 27
Homework 6, 7
|
|
Jun 21:
|
Solns for HW 6 [pdf]
and 7 [pdf]
posted
|
|
Jun 21:
|
Tutorial on NP-Complete
[pdf]
posted
|
|
|
|
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]
|
|
3
|
Recurrences
|
[pdf]
|
|
4
|
Heapsort
|
[pdf]
|
|
5
|
Quicksort
|
[pdf]
|
|
**
|
Probability and Expectation
|
[pdf]
|
|
6
|
Sorting in Linear Time
|
[pdf]
|
|
7
|
Lower Bound on Comparison Sorts
|
[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 (Insertion, Union,
Extract-Min)
|
[pdf]
|
|
19
|
Fibonacci Heap II (Decrease-Key, Delete,
Max-Deg)
|
[pdf]
|
|
20
|
Disjoint Sets I (Linked List)
|
[pdf]
|
|
21
|
Disjoint Sets II (Union by Size, Union by Rank, Path
Compression)
|
[pdf]
|
|
22
|
Graph Algorithms I (BFS)
|
[pdf]
|
|
23
|
Graph Algorithms II (DFS)
|
[pdf]
|
|
24
|
Graph Algorithms III (Topological Sort)
|
[pdf]
|
|
25
|
Graph Algorithms IV (Strongly Connected
Components)
|
[pdf]
|
|
26
|
Minimum Spanning Trees
|
[pdf]
|
|
27
|
Single-Source Shortest Paths
|
[pdf]
|
|
Tutorial
|
Topics
|
Files
|
|
1
|
Classwork for Lecture 2
|
[pdf]
|
|
2
|
Writing Good Answers, Homework 1 Hints
|
[pdf]
|
|
3
|
Homework 1 Solution, Homework 2 Hints
|
[hw1sol]
[hw2hints]
|
|
4
|
Random Selection
|
[pdf]
|
|
5
|
Catalan Number
|
[pdf]
|
|
6
|
Homework 4 Hints
|
[pdf]
|
|
7
|
Hirschberg’s Trick for LCS Problem
|
[pdf]
|
|
8
|
Ackermann Function
|
[pdf]
|
|
9
|
KMP Algorithm, Suffix Trees and Suffix Arrays
|
[kmp]
[suffix-tree]
|
|
10
|
Theory of Computation
|
[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: 21 June 2009
|