In the following schedule, I sometimes give a "main reading assignment", followed by a "supplementary reading assignment" in parentheses. This indicates that both textbooks cover basically the same topic, but if you don't entirely understand one author's treatment, you might benefit from reading the other's. Only the "main" reading assignment is required.
| Date | Assignment | Reading | Subject | |
|---|---|---|---|---|
| Aug 30 | Introduction, administrivia, math pre-test, why are we studying this stuff?
What's a "good" program? Exploring problems |
|||
| Sep 04 | HW1 | Shaffer 1, CLRS 1, How to get hired at Google |
What's an algorithm? What's a data structure?
Tradeoffs, design patterns, problems vs. algorithms vs. programs; instances, constraints |
|
| Sep 06 | Shaffer 2-2.5 | Mathematical preliminaries | ||
| Sep 11 | Shaffer 2.6-2.7 | Proof techniques, particularly induction | ||
| Sep 11 | Last day to add classes | |||
| Sep 13 | Shaffer 3-3.4 (CLRS 3) | Asymptotic analysis of algorithms | ||
| Sep 18 | Shaffer 3.5-3.11 | More issues of algorithm analysis | ||
| Sep 20 | HW1 due | Shaffer 3-3.4 (CLRS 3) | O(), θ(), and Ω() notation | |
| Sep 25 | HW2 | CLRS 3 | Comparing growth rates by limit of ratios; finding run-time functions of specific algorithms | |
| Sep 26 | Last day to drop classes, change grading option, switch sections, add independent study | |||
| Sep 27 | I missed class | |||
| Oct 02 | Worked through geometry problem; practice proving correctness | |||
| Oct 04 | CLRS 2 | Merge-sort and bubble-sort | ||
| Oct 09 | HW2 due | CLRS 4 (use 3rd edition, not 2nd) | Solving recurrences | |
| Oct 11 | Shaffer 4.1 | Lists and their ADT's; the Visitor pattern | ||
| Oct 16 | Shaffer 4.2 | Stacks | ||
| Oct 18 | Shaffer 4.3-4.4 (CLRS 10) | Queues and dictionaries | ||
| Oct 23 | Shaffer 5-5.3 | Binary trees | ||
| Oct 25 | Different implementations; visitors for binary trees | |||
| Oct 30 | Closed due to weather | |||
| Nov 01 | Closed due to weather | |||
| Nov 06 | Discussed HW2: agree on interface | |||
| Nov 07 | Last day to withdraw from classes | |||
| Nov 08 | Discussed HW2 | |||
| Nov 13 | Shaffer 5.4 (CLRS 12; use 3rd edition, not 2nd) |
binary search trees | ||
| Nov 15 | Shaffer 5.5 (CLRS 12; use 3rd edition, not 2nd) |
heaps and heapsort | ||
| Nov 20 | HW3 | Shaffer 6 | Non-binary trees | |
| Nov 22 | Thanksgiving: no classes | |||
| Nov 27 | CLRS 13-13.3 | Red-black trees | ||
| Nov 29 | CLRS 13.4 | Deletion in red-black trees | ||
| Dec 04 | Discuss homework | |||
| Dec 06 | Shaffer 9-9.3 | Searching and sets | ||
| Dec 11 | HW3 due | Shaffer 9.4 (CLRS 11) | Hashing | |
| Dec 13 | catch up and review for final | |||
| Dec 20 | CSC 343 final exam, 10:30-12:30 | |||