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