All dates for topics and homeworks are rough predictions; if we actually take more or less time on a topic than I've predicted, the schedule will shift accordingly.
| Date | Assignment | Reading | Subject | |
|---|---|---|---|---|
| Aug 28 | HW1 | Introduction, administrivia, math pre-test, why are we studying this stuff? What's a "good" program? Exploring problems | ||
| Aug 30 | 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 02 | Labor day; no classes | |||
| Sep 04 | Shaffer 2-2.5 | Mathematical preliminaries | ||
| Sep 06 | Shaffer 2.6-2.7 | Proof techniques, particularly induction | ||
| Sep 09 | Shaffer 3-3.4 | Asymptotic analysis of algorithms | ||
| Sep 10 | Last day to add classes | |||
| Sep 11 | CLRS 3 | O(), θ(), Ω() notation | ||
| Sep 13 | Shaffer 3.5-3.11 | More issues of algorithm analysis | ||
| Sep 16 | CLRS 2 | Case studies in algorithm analysis; pseudocode, proofs of correctness, etc. | ||
| Sep 18 | HW2 | Shaffer 4.1, on-line materials | Lists and their ADT's; implementations | |
| Sep 20 | CLRS 10.2; handout | The Visitor pattern; traversing a list; discuss HW1 | ||
| Sep 23 | HW1 due | Student presentations | ||
| Sep 25 | Student presentations | |||
| Sep 25 | Last day to drop classes, change grading option, switch sections, add independent study | |||
| Sep 27 | Student presentations | |||
| Sep 30 | Shaffer 4.2-4.4, CLRS 10.1 | Stacks, queues, and dictionaries | ||
| Oct 02 | on-line materials | Stacks, queues, and dictionaries | ||
| Oct 04 | Shaffer 5-5.3, CLRS 10.4 | Binary trees | ||
| Oct 07 | Different implementations; Visitors for binary trees | |||
| Oct 09 | Shaffer 5.4, CLRS 12 | Binary search trees | ||
| Oct 11 | I'm out of town; work on homework | |||
| Oct 14 | Binary search trees; discuss HW2 | |||
| Oct 16 | HW2 due | Student presentations | ||
| Oct 18 | HW3 | Student presentations | ||
| Oct 21 | Student presentations | |||
| Oct 23 | Shaffer 5.5, CLRS 6 | Heaps and heapsort | ||
| Oct 25 | Shaffer 5.6 | An application: Huffman coding | ||
| Oct 28 | CLRS 13-13.3 | Red-black trees | ||
| Oct 30 | CLRS 13.4 | Deletion in red-black trees | ||
| Oct 30 | Last day to withdraw from classes | |||
| Nov 01 | C++ help: how to manage header files, write classes, get polymorphic behavior, declare and use pointer and reference variables, etc. | |||
| Nov 04 | Discuss homework (especially visitors) | |||
| Nov 06 | HW3 due | Student presentations | ||
| Nov 08 | HW4 | Student presentations | ||
| Nov 11 | Student presentations | |||
| Nov 13 | Student presentations | |||
| Nov 15 | I'm away at a conference | |||
| Nov 18 | CLRS 13-13.3 | Red-black trees | ||
| Nov 20 | CLRS 13.4 | Deletion in red-black trees | ||
| Nov 22 | Shaffer 6, 8 | Non-binary trees; file I/O | ||
| Nov 25 | Shaffer 8 | Files and external sorting; start on hashing | ||
| Nov 27 | Thanksgiving: no classes | |||
| Nov 29 | Thanksgiving: no classes | |||
| Dec 02 | Shaffer 9.1-9.4, on-line materials, CLRS 11 | Hashing | ||
| Dec 04 | Shaffer 10.1-10.4 | Indexing; 2-3-trees; discuss homework | ||
| Dec 06 | HW4 due | Student presentations | ||
| Dec 09 | Student presentations | |||
| Dec 11 | Student presentations | |||
| Dec 18 | CSC 343 Final Exam, 10:30-12:30 | |||