Date 
Assignment 
Reading 
Subject 
Jan 25 


Introduction; problems and algorithms 
Jan 27 

Preface, 1.1 
Sample problems; pseudocode, analysis, and proofs 
Jan 30 

1.2, exercises 
More sample problems 
Feb 01 
HW1 
2.12.2 
Efficiency, scaling, worstcase, bestcase, averagecase,
asymptotic notation 
Feb 03 

2.32.4 
Implementation, data structures, common running
times 
Feb 06 

2.5, exercises 
Priority queues and heaps 
Feb 07 
Last day to add classes 
Feb 08 

3.13.2 
Graphs 
Feb 10 

3.13.2 
Graphs 
Feb 13 

3.13.2 
Graphs 
Feb 15 
HW1 due 
3.13.3 
Graphs, BFS 
Feb 17 
HW2 
3.33.4 
BFS, DFS, and bipartiteness 
Feb 20 

3.53.6, exercises 
Connectedness, DAGs, topological sorting 
Feb 21 
Last day to drop classes 
Feb 22 

4.14.2 
Return & discuss homework; Greedy algorithms; interval scheduling; proving optimality 
Feb 24 

4.24.4 
Proving optimality; shortest paths 
Feb 27 

4.5 
Minimum spanning trees 
Mar 01 

4.5 
Prim's algorithm for minimum spanning trees 
Mar 03 
HW2 due 
4.5 
Analyzing Prim's & Kruskal's algorithms 
Mar 06 

4.6, exercises 
Union/Find data structure 
Mar 08 
HW3 
5.15.2 
Mergesort and recurrences 
Mar 10 


The Master Method for solving recurrences 
Mar 13 


Discuss homework 
Mar 15 

5.55.6, exercises 
Integer multiplication; student presentations 
Mar 17 
HW3 due 

Student presentations 
Mar 20 

6.16.2 
Student presentations; Dynamic programming & memoization 
Mar 22 

6.36.4 
Multiway choices, extra parameter 
Mar 24 


Discuss homework, primes, factoring, ... 
Mar 27 

7.17.3 
Max flow, min cut 
Mar 29 
HW4 
7.5 (skim 7.77.12) 
An application: Bipartite matching 
Mar 31 

12.112.2 
Local search and simulated annealing 
Mar 31 
Last day to withdraw from classes 
Apr 03 

13.1 
Randomization 
Apr 05 

13.5 
Randomized median and quicksort 
Apr 07 

13.6 
Hashing 
Apr 10 
Spring break 
Apr 12 
Apr 14 
Apr 17 


Problems and programs again; an impossible problem 
Apr 19 
HW4 due 

Recursive, r.e., cor.e., completeness 
Apr 21 


Several homework problem presentations 
Apr 24 
HW5 
8.18.3 
Polynomial reducibility, SAT, and NP 
Apr 26 

8.48.5 
Example NPcomplete problems 
Apr 28 

8.68.8 
More example NPcomplete problems 
May 1 

8.98.10, exercises 
Complexity theory 
May 3 

9.19.2 
PSPACE 
May 5 


Parallel complexity 
May 08 
HW5 due 

Catch up & review 
May 10 
Emergency/Study Day 
May 17 
344 final exam, 10:3012:30 