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 |