|
The notes linked below are required reading, but
they are not a substitute for attending lecture and recitation. |
| Meeting |
Date |
Topic
|
| L1 |
08/26 |
Course overview and
background on SML |
| R1 |
08/30 |
Introduction
to SML |
| L2 |
08/31 |
SML Basics |
| R2 |
09/01 |
More SML |
| L3 |
09/02 |
Tuples. Records. Lists. Recursive Datatypes. Pattern Matching |
| R3 |
09/06 |
Lists and List Operators |
| L4 |
09/07 |
Parameterized Types and Polymorphism. Binary Trees. Map and Fold |
| R4 |
09/08 |
Binary Tree Traversals. Deep Pattern Matching. Fold and Map |
| L5 |
09/09 |
Identifiers, Scope, Binding. Evaluation and Substitution |
| R5 |
09/13 |
Logical Operators, Binding, Scope, Shadowing, Substitution, Printing, Sequencing |
| L6 |
09/14 |
Eager vs. Lazy Evaluation. Higher-Order Functions |
| R6 |
09/15 |
Tail Recursion, Composition, Informal Substitution Model |
| L7 |
09/16 |
The Substitution Model |
| Lx |
- |
A Substitution-Based ML Interpreter |
| R7 |
09/20 |
PS2 Review and Functional Datastructures |
| L8 |
09/21 |
Recursive Functions, Tail Recursion, and Laziness in the Substitution Model |
| R8 |
09/22 |
Lazy/Eager evaluation, thunks |
| L9 |
09/23 |
Proofs of Program Correctness |
| R9 |
09/27 |
Induction |
| L10 |
09/28 |
Graphs. Trees. Binary Search Trees |
| R10 |
09/29 |
Deletion in binary search trees; Boolean AST |
| L11 |
09/30 |
Balanced BSTs. Red-Black Trees |
| L12 |
10/05 |
Deletion from Red-Black Trees |
| R12 |
10/06 |
Prelim Review |
| L13 |
10/07 |
Splay Trees |
| Lxx |
- |
Binomial Heaps |
| R13 |
10/08 |
Common problems on homework and exam |
| L14 |
10/14 |
Graph Representations. Graph Traversals |
| R14 |
10/18 |
Finished up homework review from R13; finished Graph Traversals from
L14. |
| L15 |
10/19 |
Topological Sort |
| R15 |
10/20 |
Tree Traversal |
| L16 |
10/21 |
Introduction to asymptotic analysis |
| R16 |
10/25 |
More asymptotic analysis |
| L17 |
10/26 |
Side Effects. References. |
| R17 |
10/27 |
Circular Datastructures, Memoization. |
| L18 |
10/28 |
Streams |
| R18 |
11/01 |
More streams examples |
| L19 |
11/02 |
Streams with Side Effects |
| R19 |
11/01 |
Vector, Array, and Array2. Introductory Comparison of Environment and Substitution Models |
| L20 |
11/04 |
More on the Semantics of References |
| Lxx |
- |
Search Strategies under Adversarial Conditions: Min-Max and Alpha-Beta |
| R20 |
11/08 |
Environment Model Examples |
| L21 |
11/09 |
The Environment Model (1) |
| R21 |
11/10 |
Let Expressions & The Environment Model |
| L22 |
11/11 |
The Environment Model (2) |
| R22 |
11/15 |
Covered lecture notes: Environemnt model -- recursion using references Lecture 21-22 |
| L23 |
11/16 |
Memory Organization and Garbage Collection |
| R23 |
11/17 |
Prelim review |
| L24 |
11/18 |
An ML Interpreter: Putting Everything Together |
| R24 |
11/22 |
Memory organization (lecture 23). MiniML interpreter |
| L25 |
11/23 |
Language Semantics and Interpreter Structure. Type Checking. Special Forms |
| R25 |
11/29 |
Special forms in MiniML (lecture 25). Typechecking in MiniML |
| L26 |
11/30 |
Modular Programming. Interfaces. Specifications. Refactoring |
| R26 |
12/01 |
Regular Expressions and Deterministic Finite Automata (handout) |
| Lxx |
12/07 |
List of Suggested Problems with Solutions to Selected Problems |