CS 312 Schedule Fall 2007
The notes linked below are required reading, but
they are not a substitute for attending lecture and recitation.
|
| Meeting |
Date |
Topic
|
| Lec. 1 |
August 23 |
Course overview (intro
slides) |
| Rec. 1 |
27 |
Basic types
and expressions |
| Lec. 2 |
28 |
SML syntax and program
evaluation |
| Rec. 2 |
29 |
Tuples,
records, datatypes, and pattern matching |
| Lec. 3 |
30 |
Recursive datatypes: modeling
integers and lists |
| Rec. 3 |
September 3 |
Higher-order
and anonymous functions, currying |
| Lec. 4 |
4 |
Polymorphism and
parameterized types |
| Rec. 4 |
5 |
Datatype
pitfalls, polymorphism and lists |
| Lec. 5 |
6 |
Folding and tail recursion
(Lecturer: Steve Chong) |
| Rec. 5 |
10 |
Scope,
evaluation with substitutions |
| Lec. 6 |
11 |
The substitution model |
| Rec. 6 |
12 |
Evaluation examples |
| Lec. 7 |
13 |
Modules and data abstraction |
| Rec. 7 |
17 |
Data abstraction example: polynomials |
| Lec. 8 |
18 |
Functional
structures and abstractions |
| Rec. 8 |
19 |
Dictionaries, stacks, functors |
| Lec. 9 |
20 |
Abstraction functions
and rep invariants |
| Rec. 9 |
24 |
Set and map interfaces in SML |
| Lec. 10 |
25 |
Documenting programs |
| Rec. 10 |
26 |
Specification
examples |
| Lec. 11 |
27 |
Program correctness |
| Rec. 11 |
October 1 |
Correctness proofs by induction |
| Lec. 12 |
2 |
Asymptotic complexity |
| Rec. 12 |
3 |
Proving running times by induction |
| Lec. 13 |
4 |
Reasoning about complexity |
| Fall
Break |
| Rec. 13 |
10 |
Binary
Search Trees |
| Lec. 14 |
11 |
AVL Trees |
| October
11: Preliminary Exam 1 |
| Rec. 14 |
15 |
References and arrays,
CVS |
| Lec. 15 |
16 |
Using references (Lecturer: Siggi Cherem) |
| Rec. 15 |
17 |
Arrays
and binary heaps |
| Lec. 16 |
18 |
Hash tables (Lecturer: Siggi Cherem) |
| Rec. 16 |
22 |
Graph
algorithms |
| Lec. 17 |
23 |
Red-black trees |
| Rec. 17 |
24 |
The
Environment Model |
| Lec. 18 |
25 |
Environment model diagrams |
| Rec. 18 |
29 |
Project 1 overview |
| Lec. 19 |
30 |
Garbage collection |
| Rec. 19 |
31 |
Copying collection |
| Lec. 20 |
November 1 |
Amortized analysis |
| Rec. 20 |
5 |
Splay trees and amortized analysis |
| Lec. 21 |
6 |
Schorr-Waite graph marking
algorithm (Lecturer: David Gries) |
| Rec. 21 |
7 |
Type
checking and inference |
| Lec. 22 |
8 |
Type inference and unifications |
| Rec. 22 |
12 |
Prelim 2 review |
| Lec. 23 |
13 |
Concurrency: shared-memory |
| November
13: Preliminary Exam 2 |
| Rec. 23 |
14 |
Prelim 2 comments |
| Lec. 24 |
15 |
Concurrency: shared-memory (cont.) |
| Rec. 24 |
19 |
Multi-threaded programming |
| Lec. 25 |
20 |
Concurrency: message-passing |
|
Thanksgiving Recess |
| Rec. 25 |
26 |
Data locality and B-trees |
| Lec. 26 |
27 |
Program testing |
| Rec. 26 |
28 |
Regular expressions and finite automata |
| Lec. 27 |
29 |
Debugging techniques |
| December 7 |
Tournament |