|
HOME
COURSE SCHEDULE
HOMEWORK
PROJECTS
OFFICE HOURS
COURSE NOTE
SUPPLEMENTALS
|
Tentative Course Schedule
| Date |
Topic |
Post |
Due |
Ref |
|
|
|
|
|
| Sep 3 |
Introduction |
|
|
[1] Chap 1, [2] Chap 1 |
| Sep 5 |
Induction |
|
|
[2] Chap 2 |
| Sep 8 |
Induction |
|
|
[2] Chap 2 |
| Sep 10 |
Analysis of Algorithm |
|
|
[1] Chap 2 |
| Sep 12 |
Analysis of Algorithm |
|
|
[1] Chap 2 |
| Sep 15 |
Analysis of Algorithm |
Homework 1 |
|
[1] Chap 2 |
| Sep 17 |
O notation |
|
|
[1] Chap 3, [2] Chap 3 |
| Sep 19 |
O notation, Recurrence Relations |
|
|
[1] Chap 3, 4, [2] Chap 3 |
| Sep 22 |
Recurrence Relations |
|
Homework 1 |
[1] Chap 4, [2] Chap 3 |
| Sep 24 |
Master Theorem |
|
|
[1] Chap 4, [2] Chap 3 |
| Sep 26 |
Basic Data Structures |
|
|
[1] Chap 10, [2] Sec 4.2 |
| Sep 29 |
Basic Data Structures |
Homework 2 |
|
[1] Chap 10, [2] Sec 4.2 |
| Oct 1 |
Binary Search Tree |
|
|
[1] Chap 12, [2] Sec 4.3.3 |
| Oct 3 |
Binary Search Tree |
|
|
[1] Chap 12, [2] Sec 4.3.3 |
| Oct 6 |
Hashing |
|
|
[1] Chap 11, [2] Sec 4.4 |
| Oct 8 |
Hashing |
|
Homework 2 |
[1] Chap 11, [2] Sec 4.4 |
| Oct 10 |
Heap |
Homework 3 |
|
[1] Chap 6, [2] Sec 6.4 |
| Oct 13 |
Heapsort |
|
|
[1] Chap 6, [2] Sec 6.4 |
| Oct 15 |
Quicksort |
|
|
[1] Chap 7, [2] Sec 6.4 |
| Oct 17 |
Finding Median |
|
|
[1] Chap 9, [2] Sec 6.5 |
| Oct 20 |
Sorting in Linear Time |
Prog 1 |
Homework 3 |
[1] Chap 8, [2] Sec 6.4 |
| Oct 22 |
Sorting in Linear Time |
|
|
[1] Chap 8, [2] Sec 6.4 |
| Oct 24 |
Dynamic Programming |
|
|
[1] Chap 15 |
| Oct 27 |
Dynamic Programming |
|
|
[1] Chap 15 |
| Oct 29 |
Dynamic Programming |
|
|
[1] Chap 15 |
| Oct 31 |
Dynamic Programming |
|
|
[1] Chap 15 |
| Nov 3 |
Dynamic Programming |
Homework 4 |
Prog 1 |
[1] Chap 15 |
| Nov 5 |
Dynamic Programming |
|
|
[1] Chap 15 |
| Nov 7 |
Dynamic Programming |
|
|
[1] Chap 15 |
| Nov 10 |
Greedy Algorithm |
|
|
[1] Chap 16 |
| Nov 12 |
Introduction to Graph Theory |
|
|
[1] Sec 22.1, [2] Sec 7.1 |
| Nov 14 |
BFS |
|
Homework 4 |
[1] Sec 22.2, [2] Sec 7.3 |
| Nov 17 |
BFS |
|
|
[1] Sec 22.2, [2] Sec 7.3, Slides |
| Nov 19 |
DFS |
Homework 5 |
|
[1] Sec 22.3, [2] Sec 7.3, Slides |
| Nov 21 |
DFS, Topological Sort |
|
|
[1] Sec 22.4, [2] Sec 7.4 |
| Nov 24 |
Single-Source Shortest Paths |
|
|
[1] Chap 24, [2] Sec 7.5 |
| Nov 26 |
Single-Source Shortest Paths |
Prog 2 |
|
[1] Chap 24, [2] Sec 7.5 |
| Dec 1 |
All-Pairs Shortest Paths |
|
Homework 5 |
[1] Chap 25, [2] Sec 7.7 |
| Dec 3 |
All-Pairs Shortest Paths |
Homework 6 |
|
[1] Chap 25, [2] Sec 7.7 |
| Dec 5 |
Minimum Spanning Tree |
|
|
[1] Chap 23, [2] Sec 7.6 |
| Dec 8 |
Minimum Spanning Tree |
|
|
[1] Chap 23, [2] Sec 7.6 |
| Dec 10 |
NP |
|
Prog 2 |
[1] Chap 34, [2] Chap 11 |
| Dec 12 |
NP |
|
Homework 6 |
[1] Chap 34, [2] Chap 11 |
| [1] Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, Charles E. Leiserson, Introduction to Algorithms, Third Edition, The MIT Press, 2009. |
| [2] Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989. |
|
