Tentative Lecture and Activities Schedule
|
Date |
Topics |
|
Homework |
Comment |
|
8/24 |
Introduction |
Ch. 1-2 |
|
|
|
|
Growth of Functions |
|
|
|
|
8/31 |
Data Structures, Binary Search Trees, Heaps |
|
|
|
|
|
Divide&Conquer (DC): MergeSort |
Sec. 2.3 |
|
|
|
9/9 |
DC: Recurrences |
|
|
|
|
9/14 |
DC: Quick Sort |
|
|
|
|
9/16 |
DC: Radix Sort, Selection |
Ch. 8-9 |
Hwk#1 due |
|
|
|
DC: Strassen's |
Sec. 28.1-28.2 |
|
|
|
9/21 |
DC: Convex Hulls |
Sec. 33.3 |
|
|
|
|
Randomized Algorithms (RA), RQuickSort |
Sec. 5.1-5.3 |
|
|
|
9/28 |
RA: Skip Lists |
Handouts |
Hwk#2 due |
|
|
|
Disjoint Sets |
Sec. 21.1-21.3 |
|
|
|
10/5 |
Exam I |
|
|
|
|
|
Elementary Graph Algorithms |
Sec. 22.1-22.3 |
|
|
|
10/14 |
Greedy: Minimum Spanning Tree |
|
|
|
|
10/19 |
Greedy: Single Src Shortest Paths (Dijkstra) |
Sec. 24.3 |
Hwk#3 due |
|
|
|
Dynamic Programming (DP) |
Sec. 15.2-3 |
|
|
|
10/26 |
DP: LCS |
Sec. 15.4 |
|
|
|
|
DP: Bellman-Ford, All-Pairs Shortest Paths |
Sec. 24.1, 25.1-25.2 |
|
|
|
11/2 |
Net Flow |
Sec. 26.1 |
|
|
|
|
Max Flow: Ford-Fullerson |
Sec. 26.2 |
Hwk#4 due |
|
|
11/9 |
Exam II |
|
|
|
|
11/11 |
Lower Bound and Reduction |
Sec. 8.1, page 969-970 |
|
|
|
11/16 |
NP: |
Preface of |
|
|
|
|
NP: 3SAT |
Sec. 34.4 |
|
|
|
11/23 |
NP: Clique, VC, Subset Sum, Partition |
Sec. 34.5.1-2, 5 |
Hwk#5 and paper due |
|
| 11/30 | Review | |||
|
12/2 |
Exam III |
|
|
|