| Jan 24 |
|
|
Introduction; problems and algorithms |
| Jan 26 |
|
Preface, 1.1 |
Sample problems; pseudocode, analysis, and proofs |
| Jan 29 |
|
1.2, exercises |
More sample problems |
| Jan 31 |
HW1 |
2.1-2.2 |
Efficiency, scaling, worst-case, best-case, average-case, asymptotic
notation |
| Feb 02 |
|
2.3-2.4 |
Implementation, data structures, common running times |
| Feb 05 |
|
2.5, exercises |
Priority queues and heaps |
| Feb 06 |
Last day to add classes |
|
| Feb 07 |
|
3.1-3.2 |
Graphs |
| Feb 09 |
|
3.1-3.2 |
Graphs |
| Feb 12 |
|
3.3-3.4 |
BFS, DFS, and bipartiteness |
| Feb 14 |
|
3.3-3.4 |
BFS, DFS, and bipartiteness |
| Feb 16 |
|
3.5-3.6, exercises |
Student presentations |
| Feb 19 |
HW1 due |
|
Dr. Bloch out sick |
| Feb 20 |
Last day to drop classes |
|
| Feb 21 |
|
|
Student presentations |
| Feb 23 |
|
|
Dr. Bloch out sick |
| Feb 26 |
HW2 |
|
Review graph theory; student presentations |
| Feb 28 |
|
4.1 |
Greedy algorithms; interval scheduling |
| Mar 02 |
|
4.2 |
Proving optimality |
| Mar 05 |
|
4.4 |
Shortest paths |
| Mar 07 |
|
4.5 |
Minimum spanning trees |
| Mar 09 |
|
4.6-4.7, exercises |
Union/Find data structure, Clustering |
| Mar 12 |
|
|
Discuss homework; student presentations |
| Mar 14 |
|
|
Discuss homework; student presentations |
| Mar 16 |
HW2 due |
5.1-5.2 |
Mergesort and recurrences |
| Mar 19 |
HW3 |
5.3-5.4 |
Two more applications of divide & conquer |
| Mar 21 |
|
5.5-5.6 |
Multiplication & FFT |
| Mar 23 |
|
6.1-6.2 |
Dynamic programming & memoization |
| Mar 26 |
|
6.3-6.4 |
Multiway choices, extra parameter |
| Mar 27 |
Last day to withdraw from classes |
|
| Mar 28 |
|
6.5-6.6 |
Dynamic programming over intervals |
| Mar 30 |
HW4 |
6.8-6.9, exercises |
Shortest paths again |
| Apr 02 |
Spring break |
| Apr 04 |
| Apr 06 |
| Apr 09 |
HW3 due |
|
Student presentations |
| Apr 11 |
|
7.1-7.3 |
Max flow, min cut |
| Apr 13 |
|
7.5 |
Bipartite matching |
| Apr 16 |
|
13.1 |
Randomization |
| Apr 18 |
|
13.5 |
Randomized median and quicksort |
| Apr 20 |
I'm out of town at a conference |
|
| Apr 23 |
|
13.6 |
Hashing |
| Apr 25 |
HW4 due; HW5 |
|
Student presentations |
| Apr 27 |
|
|
Problems and programs again; impossibility |
| Apr 30 |
|
|
Recursive, r.e., co-r.e., reducibility, completeness |
| May 02 |
|
8.1-8.3 |
Polynomial reducibility, NP and SAT |
| May 04 |
|
8.4-8.5 |
Example NP-complete problems |
| May 07 |
HW5 due |
|
Student presentations; catch up and review |
| May 09 |
Emergency/Study Day |
|
| May 11 |
344 final exam, 10:30-12:30 |
|