CS 312 Schedule Spring 2003

The notes linked below are required reading, but they 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. 21 Course overview and background on ML (PS1 issued)
Rec. 1 22 Introduction to SML syntax
Lec. 2 23 Functions, scope, and evaluation
Rec. 2 27 Tuples, records, datatypes, and pattern matching
Lec. 3 28 Lists and other recursive datatypes (PS1 due)
Rec. 3 29 Higher-order and anonymous functions, currying,
printing, side effects, and exceptions
(PS2 issued)
Lec. 4 30 Polymorphism and parameterized types
Rec. 4 Feb. 3 Datatype pitfalls, polymorphism and lists
Lec. 5 4 Identifiers, substitution and scope
Rec. 5 5 Folding and tail recursion
Lec. 6 6 Specifications
Rec. 6 10 Functional examples, structures and signatures (PS2 due)
Lec. 7 11 Modules and data abstractions (PS3 issued)
Rec. 7 12 Functional stacks and queues
Lec. 8 13 Connecting specs and implementations
Rec. 8 17 Dictionaries and association lists
Lec. 9 18 Programming with rep invariants
Rec. 9 19 Set and map interfaces
Lec. 10 20 Testing
Rec. 10 24 Functors
Lec. 11 25 Proving implementations correct (PS3 due)
Rec. 11 26 More inductive correctness proofs (PS4 issued)
Lec. 12 27 Asymptotic analysis
Rec. 12 Mar. 3 Proving running times with induction
Lec. 13 4 Reasoning about complexity
Rec. 13 5 Binary search trees, Prelim I review
Lec. 14 6 Prelim I review
March 6 Preliminary Exam 1, 7:309:00PM, Upson B17
Rec. 14 10 Mutable data structures: refs and arrays
Lec. 15 11 Red-black trees
Rec. 15 12 Implementing ordered sets
Lec. 16 13 Specifying imperative abstractions (PS4 due)
March 15-23: Spring Break
Rec. 16 24 Substitution model and refs 
Lec. 17 25 An ML interpreter (PS5 issued)
Rec. 17 26 Overview of PS5
Lec. 18 27 Environment model (slides, handout)
Rec. 18 31 Environment model and recursion, PS5
Lec. 19 April 1 Managing memory heaps
Rec. 19 2 Representing and traversing graphs
Lec. 20 3 Garbage collection
Rec. 20 7 Copying garbage collection
Lec. 21 8 Type checking
Rec. 21 9 Type-checking examples
Lec. 22 10 Type inference and unification (PS5 due)
Rec. 22 14 Prelim II review 
Lec. 23 15 Prelim II review (PS6 issued)
April 15 Preliminary Exam 2, 7:309:00PM, Ives 305
Rec. 23 16 PS5 & PS6
Lec. 24 17 Prelim II recap
Rec. 24 21 Locality and B-trees
Lec. 25 22 Priority queues and Dijkstra's shortest path algorithm
Rec. 25 23 Splay trees
Lec. 26 24 Treaps
Rec. 26 28 Huffman coding
Lec. 27 29 String matching and regular expressions
Rec. 27 30 Finite automata
Lec. 28 May 1 Lazy evaluation, thunks, and streams (PS6 due May 2)
May 5 λ-Ball tournament, Upson B17, 7:30PM–9:30PM
May 15 Final Exam, Phillips 101, 3:00-5:30PM