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.12.2 
Efficiency, scaling, worstcase, bestcase, averagecase, asymptotic
notation 
Feb 02 

2.32.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.13.2 
Graphs 
Feb 09 

3.13.2 
Graphs 
Feb 12 

3.33.4 
BFS, DFS, and bipartiteness 
Feb 14 

3.33.4 
BFS, DFS, and bipartiteness 
Feb 16 

3.53.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.64.7, exercises 
Union/Find data structure, Clustering 
Mar 12 


Discuss homework; student presentations 
Mar 14 


Discuss homework; student presentations 
Mar 16 
HW2 due 
5.15.2 
Mergesort and recurrences 
Mar 19 
HW3 
5.35.4 
Two more applications of divide & conquer 
Mar 21 

5.55.6 
Multiplication & FFT 
Mar 23 

6.16.2 
Dynamic programming & memoization 
Mar 26 

6.36.4 
Multiway choices, extra parameter 
Mar 27 
Last day to withdraw from classes 

Mar 28 

6.56.6 
Dynamic programming over intervals 
Mar 30 
HW4 
6.86.9, exercises 
Shortest paths again 
Apr 02 
Spring break 
Apr 04 
Apr 06 
Apr 09 
HW3 due 

Student presentations 
Apr 11 

7.17.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., cor.e., reducibility, completeness 
May 02 

8.18.3 
Polynomial reducibility, NP and SAT 
May 04 

8.48.5 
Example NPcomplete problems 
May 07 
HW5 due 

Student presentations; catch up and review 
May 09 
Emergency/Study Day 

May 11 
344 final exam, 10:3012:30 
