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!
| Date(s) | Assignment | Reading | Lecture Subject | |
|---|---|---|---|---|
| 23 Jan | Administrivia, ``what is this course about?'' | |||
| 28 Jan | 1 | Proofs and proof techniques | ||
| 30 Jan | 2 | Problems vs. instances, average vs. worst case, etc. | ||
| 4 Feb | skim 12.1--12.4 | Lower bounds and proof techniques | ||
| 6 Feb | HW1 | 3 | Asymptotic notation | |
| 7 Feb | Last day to add courses | |||
| 11 Feb | 4.1--4.5 | Analyzing basic control structures | ||
| 13 Feb | 4.6 | Amortized analysis | ||
| 18 Feb | 4.7 | Recurrence relations | ||
| 20 Feb | HW1 due | 5.1--5.5 | Basic data structures | |
| 21 Feb | Last day to drop courses | |||
| 25 Feb | 5.6 | Associative tables & hashing | ||
| 27 Feb | 5.7--5.8 | Heaps | ||
| 4 Mar | 5.9 | Disjoint sets and union/find data structures | ||
| 6 Mar | Catch up and review for midterm | |||
| 11 Mar | Midterm exam | |||
| 13 Mar | 6.1--6.4 | Greedy algorithms | ||
| 18 Mar | 6.5--6.6 | Knapsack and scheduling algorithms | ||
| 20 Mar | HW2 | Discuss midterm | ||
| 21 Mar | Last day to withdraw from classes | |||
| 25--27 Mar | Spring break --- no classes | |||
| 1 Apr | 7.1--7.4 | Divide-and-conquer, sorting | ||
| 3 Apr | 7.5 | Selection and medians | ||
| 8 Apr | 7.6--7.8 | Matrix multiplication, exponentiation | ||
| 10 Apr | HW2 due | 7.8 | Cryptography | |
| 15 Apr | 8.1--8.4 | Dynamic programming | ||
| 17 Apr | HW3 | 8.5--8.8 | Applications of dynamic programming | |
| 22 Apr | Passover --- no classes | |||
| 24 Apr | 9.1--9.4 | Graphs and trees | ||
| 29 Apr | 9.5--9.6 | Breadth-first search and Backtracking | ||
| 1 May | 11.1--11.4 | Parallel computation | ||
| 6 May | I may be at a conference | |||
| 8 May | HW3 due | reread 12.1--12.4 | Catch up and review for final | |
| 15 May | 10:30--12:30, Final Exam | |||
| 18 May | Commencement | |||