CSC 343 Calendar

Fall 2012

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