CS 312 Schedule Spring 2003The notes linked below are required reading, but they are not a substitute for attending lecture and recitation. If the notes for a particular lecture or recitation are not posted, please do not email us about it. |
||
| Meeting | Date |
Topic |
|---|---|---|
| Lec. 1 | Jan. 21 | Course overview and background on ML (PS1 issued) |
| Rec. 1 | 22 | Introduction to SML syntax |
| Lec. 2 | 23 | Functions, scope, and evaluation |
| Rec. 2 | 27 | Tuples, records, datatypes, and pattern matching |
| Lec. 3 | 28 | Lists and other recursive datatypes (PS1 due) |
| Rec. 3 | 29 | Higher-order
and anonymous functions, currying, printing, side effects, and exceptions (PS2 issued) |
| Lec. 4 | 30 | Polymorphism and parameterized types |
| Rec. 4 | Feb. 3 | Datatype pitfalls, polymorphism and lists |
| Lec. 5 | 4 | Identifiers, substitution and scope |
| Rec. 5 | 5 | Folding and tail recursion |
| Lec. 6 | 6 | Specifications |
| Rec. 6 | 10 | Functional examples, structures and signatures (PS2 due) |
| Lec. 7 | 11 | Modules and data abstractions (PS3 issued) |
| Rec. 7 | 12 | Functional stacks and queues |
| Lec. 8 | 13 | Connecting specs and implementations |
| Rec. 8 | 17 | Dictionaries and association lists |
| Lec. 9 | 18 | Programming with rep invariants |
| Rec. 9 | 19 | Set and map interfaces |
| Lec. 10 | 20 | Testing |
| Rec. 10 | 24 | Functors |
| Lec. 11 | 25 | Proving implementations correct (PS3 due) |
| Rec. 11 | 26 | More inductive correctness proofs (PS4 issued) |
| Lec. 12 | 27 | Asymptotic analysis |
| Rec. 12 | Mar. 3 | Proving running times with induction |
| Lec. 13 | 4 | Reasoning about complexity |
| Rec. 13 | 5 | Binary search trees, Prelim I review |
| Lec. 14 | 6 | Prelim I review |
| March 6 | Preliminary Exam 1, 7:30–9:00PM, Upson B17 | |
| Rec. 14 | 10 | Mutable data structures: refs and arrays |
| Lec. 15 | 11 | Red-black trees |
| Rec. 15 | 12 | Implementing ordered sets |
| Lec. 16 | 13 | Specifying imperative abstractions (PS4 due) |
| March 15-23: Spring Break | ||
| Rec. 16 | 24 | Substitution model and refs |
| Lec. 17 | 25 | An ML interpreter (PS5 issued) |
| Rec. 17 | 26 | Overview of PS5 |
| Lec. 18 | 27 | Environment model (slides, handout) |
| Rec. 18 | 31 | Environment model and recursion, PS5 |
| Lec. 19 | April 1 | Managing memory heaps |
| Rec. 19 | 2 | Representing and traversing graphs |
| Lec. 20 | 3 | Garbage collection |
| Rec. 20 | 7 | Copying garbage collection |
| Lec. 21 | 8 | Type checking |
| Rec. 21 | 9 | Type-checking examples |
| Lec. 22 | 10 | Type inference and unification (PS5 due) |
| Rec. 22 | 14 | Prelim II review |
| Lec. 23 | 15 | Prelim II review (PS6 issued) |
| April 15 | Preliminary Exam 2, 7:30–9:00PM, Ives 305 | |
| Rec. 23 | 16 | PS5 & PS6 |
| Lec. 24 | 17 | Prelim II recap |
| Rec. 24 | 21 | Locality and B-trees |
| Lec. 25 | 22 | Priority queues and Dijkstra's shortest path algorithm |
| Rec. 25 | 23 | Splay trees |
| Lec. 26 | 24 | Treaps |
| Rec. 26 | 28 | Huffman coding |
| Lec. 27 | 29 | String matching and regular expressions |
| Rec. 27 | 30 | Finite automata |
| Lec. 28 | May 1 | Lazy evaluation, thunks, and streams (PS6 due May 2) |
| May 5 | λ-Ball tournament, Upson B17, 7:30PM–9:30PM | |
| May 15 | Final Exam, Phillips 101, 3:00-5:30PM | |