CS 312 Schedule
Spring 2005
The notes linked below are required reading, but
they are not a substitute for attending lecture and recitation. |
| Meeting |
Date |
Topic
|
| Lec. 1 |
January 25 |
Course overview |
| Rec. 1 |
26 |
Basic types
and expressions |
| Lec. 2 |
27 |
SML syntax and program
evaluation |
| Rec. 2 |
31 |
Tuples,
records, datatypes, and pattern matching |
| Lec. 3 |
February 1 |
Recursive datatypes: modeling
integers and lists |
| Rec. 3 |
2 |
Higher-order
and anonymous functions, currying
|
| Lec. 4 |
3 |
Polymorphism and
parameterized types |
| Rec. 4 |
7 |
Datatype
pitfalls, polymorphism and lists |
| Lec. 5 |
8 |
Scope, evaluation with
substitutions |
| Rec. 5 |
9 |
Folding
and tail recursion |
| Lec. 6 |
10 |
Functional specifications
|
| Rec. 6 |
14 |
Structures and
signatures |
| Lec. 7 |
15 |
Modules and data abstractions
|
| Rec. 7 |
16 |
Functional
stacks and queues |
| Lec. 8 |
17 |
Documenting
implementations |
| Rec. 8 |
21 |
More
data abstractions |
| Lec. 9 |
22 |
Programming with
rep invariants |
| Rec. 9 |
23 |
Sets and Maps |
| Lec. 10 |
24 |
Program
Testing
|
| Rec. 10 |
28 |
Functors |
| Lec. 11 |
March 1 |
Debugging Techniques |
| Rec. 11 |
2 |
Induction and
program correctness |
| Lec. 12 |
3 |
More inductive correctness proofs
|
| Rec. 12 |
7 |
Asymptotic complexity
|
| Lec. 13 |
8 |
Reasoning about complexity |
| Rec. 13 |
9 |
Proving running times with induction
|
| Lec. 14 |
10 |
Prelim I review |
| March 10 |
Preliminary
Exam I, 7:30–9:00pm, Upson B17 |
| Rec. 14 |
14 |
Mutable
data structures: refs and arrays |
| Lec. 15 |
15 |
Red-black trees |
| Rec. 15 |
16 |
Implementing ordered sets |
| Lec. 16 |
17 |
Hash
Tables |
| March 20-28: Spring Break |
| Rec. 16 |
28 |
Substitution
model and refs |
| Lec. 17 |
29 |
An ML interpreter |
| Rec. 17 |
30 |
Problem
Set 5 Overview |
| Lec. 18 |
31 |
The
Environment Model |
| Rec. 18 |
April 4 |
Environment model:
recursion, lists, refs |
| Lec. 19 |
5 |
Memory management |
| Rec. 19 |
6 |
Representing
and traversing graphs |
| Lec. 20 |
7 |
Garbage collection |
| Rec. 20 |
11 |
Copying
collection |
| Lec. 21 |
12 |
Type checking |
| Rec. 21 |
13 |
More type-checking |
| Lec. 22 |
14 |
Type inference and
unification |
| Rec. 22 |
18 |
Let-polymorphism |
| Lec. 23 |
19 |
Prelim II review |
| April 19 |
Preliminary
Exam II, 7:30–9:00pm, Phillips 101 |
| Rec. 23 |
20 |
Problem
Set 6 Overview |
| Lec. 24 |
21 |
Data
locality and B-trees |
| Rec. 24 |
25 |
Prelim
II recap |
| Lec. 25 |
26 |
Splay
trees and amortized analysis |
| Rec. 25 |
27 |
Priority
queues and binary heaps |
| Lec. 26 |
28 |
Graph
search algorithms (lecturer: Lucja Kot) |
| Rec. 26 |
May 2 |
Huffman coding |
| Lec. 27 |
3 |
Concurrency |
| Rec. 27 |
4 |
State
machines and regular expressions
|
| Lec. 28 |
5 |
Continuations; Slides from class (lecturer: Lucja Kot) |
| May 17 |
Final Exam, 9:00–11:30am,
Ives 105 |