CS 312 Schedule Spring 2008The notes linked below are required reading, but they are not a substitute for attending lecture and recitation. The lectures and recitation sections are tightly coupled: Lectures will assume knowledge from previous sections, and vice-versa. These notes should be read sequentially (Monday's section, Tuesday's lecture, Wednesday's section, Thursday's lecture, etc.). Note: due dates of unreleased assignments are tentative. |
||
| Meeting | Date |
Topic |
|---|---|---|
| Introduction to functional programming | ||
| Lec. 1 | Jan. 22 | Course overview and background on ML (slides) (PS1 issued) |
| Rec. 1 | 23 | Introduction to SML syntax |
| Lec. 2 | 24 | Functions, scope, and evaluation |
| Jan. 24 | SML demo, 7–8pm, Upson B7 | |
| Rec. 2 | 28 | Tuples, records, datatypes, and pattern matching |
| Lec. 3 | 29 | Lists and other recursive datatypes |
| Rec. 3 | 30 | Higher-order
and anonymous functions, currying, printing, side effects, and exceptions |
| Lec. 4 | 31 | Polymorphism and parameterized types (PS1 due, PS2 issued) |
| Rec. 4 | Feb. 4 | Datatype pitfalls, polymorphism and lists |
| Lec. 5 | 5 | Substitution model of evaluation |
| Rec. 5 | 6 | Folding and tail recursion |
| Writing and using specifications | ||
| Lec. 6 | 7 | Specifications |
| Rec. 6 | 11 | Functional examples, structures and signatures |
| Lec. 7 | 12 | Modules and data abstractions |
| Rec. 7 | 13 | Functional stacks and queues (PS2 due) |
| Lec. 8 | 14 | Documenting implementations of data abstractions (PS3 issued) |
| Rec. 8 | 18 | Dictionaries and association lists |
| Lec. 9 | 19 | Representation invariants |
| Rec. 9 | 20 | Set and map interfaces |
| Reasoning about correctness | ||
| Lec. 10 | 21 | Testing |
| Rec. 10 | 25 | More testing |
| Lec. 11 | 26 | Logic for verification |
| Rec. 11 | 27 | More inductive correctness proofs (PS3 due, PS4 issued) |
| Lec. 12 | 28 | Predicate logic |
| Rec. 12 | Mar. 3 | Using predicate logic, induction |
| Lec. 13 | 4 | Verification conditions |
| Rec. 13 | 5 | Prelim I review |
| Lec. 14 | 6 | Prelim I review (optional) |
| March 6 | Preliminary Exam I, 7:30–9:00pm, Thurston 205 (Closed-book. Covers material through Recitation 12 and PS3.) | |
| Rec. 14 | 10 | Verification conditions, using specs to write recursive functions |
| Lec. 15 | 11 | Modular verification |
| Rec. 15 | 12 | Mutable data structures: refs and arrays |
| Lec. 16 | 13 | Specifying imperative abstractions |
| March 15–23: Spring Break | ||
| Reasoning about performance | ||
| Rec. 16 | 24 | Asymptotic complexity and binary search trees |
| Lec. 17 | 25 | Recurrences |
| Rec. 17 | 26 | Solving recurrences |
| Lec. 18 | 27 | Substitution and master methods (PS4 due, PS5 issued) |
| Rec. 18 | 31 | PS5 overview |
| Data structures and algorithms | ||
| Lec. 19 | Apr. 1 | Red-black trees |
| Rec. 19 | 2 | Representing and traversing graphs, source code control |
| Lec. 20 | 3 | Hash tables and amortized complexity |
| Rec. 20 | 7 | Concurrency and monitors |
| Lec. 21 | 8 | Amortized analysis, hash functions |
| Rec. 21 | 9 | Amortized analysis examples |
| Lec. 22 | 10 | Memoization (PS5 due, PS6 issued) |
| Rec. 22 | 14 | Prelim II review |
| Lec. 23 | 15 | (No lecture) |
| April 15 | Preliminary Exam II, 7:30–9:00pm, Phillips 219 (Closed-book. Covers though Lecture 21 and PS5.) |
|
| Rec. 23 | 16 | PS6 overview |
| Below the SML abstraction | ||
| Lec. 24 | 17 | Locality |
| Rec. 24 | 21 | Garbage collection |
| Lec. 25 | 22 | Splay trees |
| Rec. 25 | 23 | B-trees |
| Programming paradigms | ||
| Lec. 26 | 24 | Concurrency and message passing |
| Rec. 26 | 28 | Lambda calculus |
| Lec. 27 | 29 | Streams and other laziness |
| Rec. 27 | 30 | Type inference |
| Lec. 28 | May 1 | Logic programming and pattern matching for Java [ JMatch web site ] (PS6 due) |
| May 6 | CS 312 Tournament, Upson B17, 7:30–9:30pm (pizza provided) | |
| May 12 | Final review, 2:30-4pm, Upson 109 | |
| May 13 | Final Exam, 7-9:30pm,
Phillips 203 (Open-book. Covers all course material.) | |