This class meets every Tuesday and Thursday from 9:25 to 10:40 AM,
except on University holidays or if I cancel class.
All dates in the following schedule are tentative, except those fixed
by the University; if some topic listed here as taking one lecture in
fact takes two lectures to cover adequately, or *vice versa*,
the schedule will shift.

I expect you to have read the reading assignments
*before* the lecture that deals with that topic; this way I can
concentrate my time on answering questions and clarifying subtle or
difficult points in the textbook, rather than on reading the textbook
to you, which will bore both of us. **Please read ahead!**

Note (Jan. 28): I've slowed down the schedule somewhat, omitting a few sections that are really interesting but not essential, and I'm leaning towards more (and smaller) homework assignments.

Date(s) | Assignment | Reading | Lecture Subject | |
---|---|---|---|---|

23 Jan | Administrivia, ``what is this course about?'' | |||

28 Jan | 1 | Multiplication algorithms; intro to mathematical proofs | ||

30 Jan | 1 | Logical notation and proof techniques | ||

4 Feb | HW1 | 1 | Mathematical induction, combinatorics, and probability | |

6 Feb | 2 | Problems vs. instances, average vs. worst case, etc. | ||

7 Feb | Last day to add courses | |||

11 Feb | skim 12.1--12.4; start ch. 3 | Lower bounds and proof techniques | ||

13 Feb | HW1 due | 3 | Asymptotic notation | |

18 Feb | About this homework... | |||

20 Feb | More about proofs | |||

21 Feb | HW2 | Last day to drop courses | ||

25 Feb | 3 | Again with the asymptotic notation... | ||

27 Feb | 4.1--4.5 | Analyzing basic control structures | ||

4 Mar | 4.6 | Amortized analysis | ||

6 Mar | 4.7 | Recurrence relations | ||

11 Mar | Midterm exam | |||

13 Mar | Discuss midterm | |||

18 Mar | 4.7 | More recurrence relations | ||

20 Mar | HW2 due | 5.1--5.5 | Basic data structures | |

21 Mar | Last day to withdraw from classes | |||

25--27 Mar | Spring break --- no classes | |||

1 Apr | Discuss homework | |||

3 Apr | HW3 | 5.1--5.5 | Basic data structures | |

8 Apr | 5.1--5.5 | Basic data structures | ||

10 Apr | 5.1--5.5 | Basic data structures | ||

15 Apr | 5.6 | Associative tables & hashing | ||

17 Apr | HW3 due; HW4 | 5.7--5.8 | Heaps | |

22 Apr | Passover --- no classes | |||

24 Apr | 6.1--6.4 | Greedy algorithms | ||

29 Apr | 6.5--6.6 | Knapsack and scheduling algorithms | ||

1 May | HW4 due | 7.1--7.4 | Divide-and-conquer, sorting | |

6 May | I'll be at a conference | |||

8 May | Catch up and review for final | |||

15 May | 10:30--12:30, Final Exam | |||

18 May | Commencement |

You are visitor number to this and related pages since Feb. 13, 1997.