Date 
Assignment 
Reading 
Subject 
20Jan 
HW1 

Administrivia; problems, instances, algorithms, and
programs 
25Jan 

1.11.3 
Basic concepts 
27Jan 

1.4 
Review basic data structures 
28Jan 
Deadline
to add courses 
1Feb 

2.12.2 
Efficiency, resources, and what should affect them 
3Feb 
HW1 due; HW2 

Presentations & discussion on Euclid's game 
8Feb 


Discuss HW1 
10Feb 

2.32.4 
How to analyze an algorithm's efficiency 
15Feb 
Deadline to drop courses 
15Feb 

2.52.7 
Loops and recursion 
17Feb 

Appendix B 
Solving recurrence relations 
22Feb 
HW2 due 
4.14.3 
Selection (heap), Insertion (tree), and Mergesort 
24Feb 

4.2, 4.6 
Quicksort; some geometric examples 
1Mar 
HW3 

Homework, convex hulls, lower bounds... 
3Mar 

5.15.3 
DFS, BFS, topological sorting 
8Mar 

5.55.6 
More decreaseandconquer algorithms 
10Mar 

6.16.3 
Instance simplification 
15Mar 
HW3 due 
6.46.5 
Representation change 
17Mar 

6.6 
Problem reduction 
1927Mar 
Spring
break; no classes 
28Mar 
Deadline to withdraw from courses 
29Mar 

7.17.2 
Speed, for a price 
31Mar 

7.17.2 
String matching with preprocessing 
5Apr 

7.3 
Hashing 
7Apr 
HW4 
7.3, 8.18.2 
More hashing; start on dynamic programming 
12Apr 

8.38.4 
More examples of dynamic programming 
14Apr 

9.19.3 
Greedy algorithms 
19Apr 


Cryptography 
21Apr 

10.110.2 
Proving a problem is difficult 
26Apr 


Computability and uncomputability 
28Apr 

10.3 
Complexity, P and NP, NC and friends 
3May 
HW4 due 
2003 Final Exam 
Catch up and review 
12May 
Final
exam, 10:3012:30 