CS 312 Schedule
Spring 2002
The notes linked below 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. 22 |
Course overview and
background on ML |
| Rec. 1 |
23 |
Introduction
to SML syntax |
| Lec. 2 |
24 |
Recursive functions
and qualified names in SML |
| Rec. 2 |
28 |
Tuples,
records, datatypes, and pattern matching |
| Lec. 3 |
29 |
Recursive datatypes
and lists |
| Rec. 3 |
30 |
Higher-order
functions and datatype constructors |
| Lec. 4 |
31 |
Polymorphism and
parameterized types |
| Rec. 4 |
Feb. 4 |
Side
effects, datatype pitfalls, and polymorphism |
| Lec. 5 |
5 |
Modules and ADTs |
| Rec. 5 |
6 |
Folding,
currying, mapping, and exceptions |
| Lec. 6 |
7 |
Specifying
functions and signatures |
| Rec. 6 |
11 |
Writing
stacks and queues in functional style |
| Rec. 7 |
13 |
Association
lists |
| Lec. 7 |
14 |
Documenting
implementations |
| Rec. 8 |
18 |
Programming
with rep invariants |
| Lec. 8 |
19 |
Asymptotic analysis |
| Rec. 9 |
20 |
Proving
running times with induction |
| Lec. 9 |
21 |
Reasoning about
correctness and complexity |
| Rec. 10 |
25 |
Binary
search trees, functors |
| Lec. 10 |
26 |
Implementing sets
efficiently: red/black trees |
| Rec. 11 |
27 |
Mutable
data structures: refs and arrays |
| Lec. 11 |
28 |
Hash tables |
| Rec. 12 |
Mar. 4 |
PS4: Tries and Lempel-Ziv
compression |
| Lec. 12 |
5 |
Testing |
| Rec. 13 |
6 |
Prelim I review
|
| Lec. 13 |
7 |
Prelim I review |
| March 7 |
Preliminary Exam 1, Hollister
B14, 7:30–9:00PM |
| Rec. 14 |
11 |
Prelim I recap |
| Lec. 14 |
12 |
Substitution model |
| Rec. 15 |
13 |
Substitution model examples |
| Lec. 15 |
14 |
Substitution model:
definitional interpreter |
| Spring Break |
| Rec. 16 |
25 |
Introduction
to environment model |
| Lec. 16 |
26 |
Environment model:
refs, closures, and recursion [PDF] |
| Rec. 17 |
27 |
Environment model examples,
PS5 |
| Lec. 17 |
28 |
Type checking |
| Rec. 18 |
April 1 |
Subtyping, objects, and PS5 |
| Lec. 18 |
2 |
Type
inference and unification |
| Rec. 19 |
3 |
Graph
representations and traversal |
| Lec. 19 |
4 |
Heaps, priority
queues, Huffman coding |
| Rec. 20 |
8 |
PS6
overview |
| Lec. 20 |
9 |
Dijkstra's shortest path algorithm |
| Rec. 21 |
10 |
Minimax
search and alpha-beta pruning |
| Lec. 21 |
11 |
Lazy
evaluation, thunks, and streams |
| Rec. 22 |
15 |
Prelim II review |
PS6
design reviews
April 15–19 |
| Lec. 22 |
16 |
Prelim II review |
| April 16 |
Preliminary Exam 2, Hollister B14, 7:30–9:00PM |
| Rec. 23 |
17 |
Prelim II recap |
| Lec. 23 |
18 |
Memory management |
| Rec. 24 |
22 |
Copying
garbage collection |
| Lec. 24 |
23 |
Ordered collections: treaps |
| Rec. 25 |
24 |
Locality: splay trees
and B-trees |
| Lec. 25 |
25 |
String matching |
| Rec. 26 |
29 |
Regular expressions |
| Lec. 26 |
30 |
Concurrency |
| Rec. 27 |
May 1 |
Y-combinator and self-reference |
| Lec. 27 |
2 |
Continuations |
| May 14 |
Final Exam, Kimball B11,
3:00-5:30PM |