CS 312 Schedule Spring 2007The notes linked below are required reading, but they are not a substitute for attending lecture and recitation. Note: due dates of unreleased assignments are tentative. |
||
| Meeting | Date |
Topic |
|---|---|---|
| Lec. 1 | Jan. 23 | Course overview and background on ML (slides) (PS1 issued) |
| Rec. 1 | 24 | Introduction to SML syntax |
| Lec. 2 | 25 | Functions, scope, and evaluation |
| Rec. 2 | 29 | Tuples, records, datatypes, and pattern matching |
| Jan. 25 | SML/Emacs demo, 7–8pm, Upson B7 | |
| Lec. 3 | 30 | Lists and other recursive datatypes (Lecturer: Michael Clarkson) |
| Rec. 3 | 31 | Higher-order
and anonymous functions, currying, printing, side effects, and exceptions (PS1 due, PS2 issued) |
| Lec. 4 | Feb. 1 | Polymorphism and parameterized types |
| Rec. 4 | 5 | Datatype pitfalls, polymorphism and lists |
| Lec. 5 | 6 | Substitution model of evaluation |
| Rec. 5 | 7 | Folding and tail recursion |
| Lec. 6 | 8 | Specifications |
| Rec. 6 | 12 | Functional examples, structures and signatures (PS2 due, PS3 issued) |
| Lec. 7 | 13 | Modules and data abstractions |
| Rec. 7 | 14 | Functional stacks and queues |
| Lec. 8 | 15 | Documenting implementations of data abstractions |
| Rec. 8 | 19 | Dictionaries and association lists |
| Lec. 9 | 20 | Representation invariants |
| Rec. 9 | 21 | Set and map interfaces |
| Lec. 10 | 22 | Testing (PS3 due, PS4 issued) |
| Rec. 10 | 26 | Functors |
| Lec. 11 | 27 | Verification (Lecturer: Radu Rugina) |
| Rec. 11 | 28 | More inductive correctness proofs |
| Lec. 12 | Mar. 1 | Modular verification (lecturer: Eric Breck) |
| Rec. 12 | 5 | Asymptotic complexity |
| Lec. 13 | 6 | Reasoning about complexity |
| Rec. 13 | 7 | Proving running times with induction |
| Lec. 14 | 8 | Prelim I review (optional) |
| March 8 | Preliminary Exam I, 7:30–9:00pm, Upson B17 (covers through Lecture 12 and PS3) | |
| Rec. 14 | 12 | Mutable
data structures: refs and arrays Substitution model and refs |
| Lec. 15 | 13 | Balanced binary trees |
| Rec. 15 | 14 | Implementing ordered sets |
| Lec. 16 | 15 | Specifying imperative abstractions (PS4 due) |
| March 17–25: Spring Break | ||
| Rec. 16 | 26 | Overview of PS5 (PS5 issued) |
| Lec. 17 | 27 | Hash tables and amortized analysis |
| Rec. 17 | 28 | More amortized analysis |
| Lec. 18 | 29 | Environment model (Lecturer: Radu Rugina) |
| Rec. 18 | Apr. 2 | Environment model and recursion, PS5 |
| Lec. 19 | 3 | Managing memory heaps |
| Rec. 19 | 4 | Representing and traversing graphs |
| Lec. 20 | 5 | Garbage collection |
| Rec. 20 | 9 | Copying garbage collection |
| Lec. 21 | 10 | Incremental and generational garbage collection |
| Rec. 21 | 11 | Type-checking examples (PS5 due, PS6 issued) |
| Lec. 22 | 12 | Type checking |
| Rec. 22 | 16 | Prelim II review |
| Lec. 23 | 17 | (No lecture) |
| April 17 | Preliminary Exam II, 7:30–9:00pm, Phillips 219 (covers though Lecture 21 and PS5) |
|
| Rec. 23 | 18 | PS5 & PS6 |
| Lec. 24 | 19 | Locality and splay trees |
| Rec. 24 | 23 | B-trees and PS6 design review recap |
| Lec. 25 | 24 | Priority queues, binary heaps |
| Rec. 25 | 25 | Prelim II recap |
| Lec. 26 | 26 | Dijkstra's shortest path algorithm |
| Rec. 26 | 30 | A* search |
| Lec. 27 | May 1 | Concurrency |
| Rec. 27 | 2 | State machines and regular expressions |
| Lec. 28 | 3 | CML concurrency mechanisms. Pattern matching for Java (PS6 due) |
| May 8 | CS 312 Tournament, Upson B17, 7:30–9:30pm | |
| May 14 | Final Exam, 9:00–11:30am, Thurston 203 | |