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.
Dr. Stephen Bloch