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.
(Last Updated: 09/26/07 )
| Week | Topics due | Due |
| 0. Thursday Sept 20 | Administrivia, Models of Computation, Complexity Definitions | Hw1 Assigned |
| 1. Tuesday Sept 25 | Asymptotic Notation, Strassen Matrix-Mult, Master Thm. | |
| 1. Thursday Sept 27 | Master Thm. Proof, Substitution Method | |
| 2. Tuesday Oct 2 | Substitution Method (cont.), Char. Eq. Method | |
| 2. Thursday Oct 4 | Heaps and HeapSort, QuickSort |
Hw1 due Hw2 Assigned |
| 3. Tuesday Oct 9 | Quicksort(cont.) and Randomized Quicksort | |
| 3. Thursday Oct 11 | Sorting lower bounds, Counting sort, Radix sort | |
| 4. Tuesday Oct 16 | Selection, Median of medians | |
| 4. Thursday Oct 18 | Bounds via Adversary Arguments (handout)
Binary Trees |
Hw 2 due
Hw 3 assigned |
| 5. Tuesday Oct 23 | Red-Black Trees, Binomial Heaps | |
| 5. Thursday Oct 25 | Fibonacci Heaps | |
| 6. Tuesday Oct 30 | Fibonacci Heap analysis, Amortization | |
| 6. Thursday Nov 1 | Disjoint Sets |
Hw 3 due |
| 7. Tuesday Nov 6 | Midterm | |
| 7. Thursday Nov 8 | Decision Problems, Encodings,Polynomial Reductions | |
| 8. Tuesday Nov 13 | Examples of Reductions | |
| 8. Thursday Nov 15 | The classes NP and co-NP, NP-completeness | Hw 4 assigned |
| 9. Tuesday Nov 20 | Dynamic Programming, Matrix Mult. Order, LCS, Floyd-Warshall O-1 Knapsack, Pseudo-Polynomial, |
Hw 5 assigned |
| 9. Thursday Nov 22 | HOLIDAY | |
| 10. Tuesday Nov 27 | Greedy Knapsack, Activity Selection, Minimum Spanning Trees | Hw 4 due |
| 10. Thursday Nov 29 | Matroids, Scheduling | |
| Monday December 3 | Hw 5 due at 4:30pm in BE317B | |
| Wednesday Dec 5 | FINAL EXAM 8-11am |