| Week | Topic | Assignments |
| 1 Jan. 10 - 14 |
Computational Complexity: Selection, Insertion and Shell Sorts Complexity of sorting in general |
|
| 2 - 3 Jan. 17 - 27 |
Solving Difference Equations: First Order Recurrences Higher Order Linear Recurrences Solution to Binary Search Recurrence Solution to MergeSort Recurrence |
hw - 1 |
| 4 - 5 Jan. 31 - Feb. 11 |
Generating Functions: OGF and EGF Solution to QuickSort Recurrence OGF in combinatorics |
hw - 2 |
| 6 - 8 Feb. 14 - Mar. 04 |
Divide-and-Conquer: Multiplication (Karatsuba, Toom-Cook) Exponentiation Matrix Multiplication (Strassen) Shamir's Algorithm for n! Polynomial Multiplication (using the FFT) |
hw - 3 write-up |
| Spring Break | ||
| 9 - 10 Mar. 14 - 25 |
Probabilistic Algorithms: Complexity of QuickSort Hashing |
|
| 11 - 12 Mar. 28 - Apr. 08 |
Dynamic Programming: 0-1 Knapsack Problem Chain Matrix Multiplication Floyd's Algorithm Approximate String Matching |
hw - 4 write-up |
| 13 - 14 Apr. 11 - 22 |
Greedy Algorithms: Matrix Multiplication Shortest Paths Minimum Spanning Tree Network Flows |
write-up |
| 15 Apr. 25 - 29 |
Final Project: Undirected SSSP in Linear Time |
|
Victor
S. Adamchik,
Computer Science Department, Carnegie Mellon University, Pittsburgh, PA. |