CS 312 Schedule Fall 2006
The notes linked below are required reading, but
they are not a substitute for attending lecture and recitation.
|
Meeting |
Date |
Topic
|
Lec. 1 |
August 24 |
Course overview
(slides)
|
Rec. 1 |
28 |
Basic types
and expressions |
Lec. 2 |
29 |
SML syntax and program
evaluation (lecturer: Siggi Cherem) |
Rec. 2 |
30 |
Tuples,
records, datatypes, and pattern matching |
Lec. 3 |
31 |
Recursive datatypes: modeling
integers and lists (lecturer: Andrew Myers) |
Rec. 3 |
September 4 |
Higher-order
and anonymous functions, currying
|
Lec. 4 |
5 |
Polymorphism and
parameterized types |
Rec. 4 |
6 |
Datatype
pitfalls, polymorphism and lists |
Lec. 5 |
7 |
Folding and tail recursion |
Rec. 5 |
11 |
Scope,
evaluation with substitutions |
Lec. 6 |
12 |
The substitution model |
Rec. 6 |
13 |
Evaluation examples |
Lec. 7 |
14 |
Modules and data abstraction |
Rec. 7 |
18 |
Data abstraction for polynomials |
Lec. 8 |
19 |
Data abstractions and invariants |
Rec. 8 |
20 |
Beyond signatures: functors |
Lec. 9 |
21 |
Documenting programs |
Rec. 9 |
25 |
SML I/O, PS3 overview |
Lec. 10 |
26 |
Reasoning about program correctness |
Rec. 10 |
27 |
Correctness proofs by induction |
Lec. 11 |
28 |
Asymptotic complexity |
Rec. 11 |
October 2 |
Proving running times by induction |
Lec. 12 |
3 |
Reasoning about complexity |
Rec. 12 |
4 |
Binary
Search Trees |
Lec. 13 |
5 |
AVL Trees |
Fall
Break |
Rec. 13 |
11 |
References and Arrays,
CVS |
Lec. 14 |
12 |
Hash Tables |
October
12: Preliminary Exam 1 |
Rec. 14 |
16 |
Arrays and binary heaps |
Lec. 15 |
17 |
Using references |
Rec. 15 |
18 |
The
environment model |
Lec. 16 |
19 |
Red-black trees |
Rec. 16 |
23 |
The
environment model (cont.) |
Lec. 17 |
24 |
Environment model
diagrams |
Rec. 17 |
25 |
Graph
algorithms |
Lec. 18 |
26 |
Memory management |
Rec. 18 |
30 |
Project 1 overview |
Lec. 19 |
31 |
Garbage collection |
Rec. 19 |
November 1 |
Copying collection |
Lec. 20 |
2 |
Amortized Analysis |
Rec. 20 |
6 |
Splay Trees and Amortized Analysis |
Lec. 21 |
7 |
Types, type checking, type
inference |
Rec. 21 |
8 |
Type
inference |
Lec. 22 |
9 |
Type inference and Unifications |
Rec. 22 |
13 |
Prelim 2 review |
Lec. 23 |
14 |
Concurrency: shared-memory |
November
14: Preliminary Exam 2 |
Rec. 23 |
15 |
Prelim 2 comments |
Lec. 24 |
16 |
Program correctness and invariants
(invited lecturer: David Gries) |
Rec. 24 |
20 |
Concurrency: message-passing |
Lec. 25 |
21 |
Program testing |
Rec. 25 |
27 |
Data locality and B-trees |
Lec. 26 |
28 |
Debugging techniques |
Rec. 26 |
29 |
Regular expressions and finite automata |
Lec. 27 |
30 |
|
December 13 |
Lambda-Craft Tournament |