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