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