Disclaimer: The following schedule lists the major topics which we will cover and the expected due dates for the assignments. This is my best guess on how the course will proceed. It is subject to change. Changes will be announced in class.
(Last Updated: 04/24/01 )
| Week | Topics due | Due |
| 1. Tuesday Mar 27 | Administrivia, Models of Computation, Complexity Definitions |
Hw1 Assigned |
| 1. Thursday Mar 29 | Asymptotic Notation, Strassen Mult. Master Thm. |
|
| 2. Tuesday Apr 3 | Master Thm. Proof, Substitution Method, Char. Eq (handout) |
|
| 2. Thursday Apr 5 | Char. Eq. Method(continued), HeapSort, QuickSort |
|
| 3. Tuesday Apr 10 | Quicksort and Randomized Quicksort
Sorting lower bounds |
Hw1 due Hw2 Assigned |
| 3. Thursday Apr 12 | Counting sort, Radix sort Selection, Median of medians |
|
| 4. Tuesday Apr 17 | Bounds via Adversary Arguments (handout) | |
| 4. Thursday Apr 19 | Binary Trees Red-Black Trees |
|
| 5. Tuesday Apr 24 | Red-Black Trees(cont) Binomial Heaps |
Hw 2 due Hw 3 assigned |
| 5. Thursday Apr 26 | Fibonacci Heaps | |
| 6. Tuesday May 1 | Fibonacci Heap analysis Amortization |
|
| 6. Thursday May 3 | Disjoint Sets |
Hw 3 due |
| 7. Tuesday May 8 | MIDTERM EXAM ?? | |
| 7. Thursday May 10 | Decision Problems, Encodings Polynomial Reductions |
|
| 8. Tuesday May 15 | Examples of Reductions | |
| 8. Thursday May 17 | The classes NP and co-NP, NP-completeness |
|
| 9. Tuesday May 22 | Dynamic Programming, Matrix Mult. Order, LCS, Floyd-Warshall O-1 Knapsack, Pseudo-Polynomial, |
|
| 9. Thursday May 24 | Greedy Knapsack, Activity Selection, Minimum Spanning Trees | |
| 10. Tuesday May 29 | Matroids, Scheduling | |
| 10. Thursday May 31 | Review (Last class) | |
| Monday June 4 | FINAL EXAM 8-11am |