Course Notes
The course notes have changed and are not the same as Fall 2024, or previous years. Older course material may appear similar but many details are different this term. If in doubt, ask us.
Course notes will appear here 1-3 weeks in advance of lectures.
| Slides | Description | |
|---|---|---|
| L00 | Welcome | Overview of the course, tools, assignments and grading. |
| L01 | Values and expressions | Prefix notation, exact numbers, Boolean expressions, constants |
| L02 | Functions | Function definitions, inexact numbers, substitution rules, comments |
| L03 | Conditional expressions | Expressions with cond and else, symbols, testing, contracts |
| L04 | Recursion | Recursion on a natural number, names, scope |
| L05 | Lists | List values and expressions, composite data, data definitions |
| L06 | Recursion on lists | Recursion on a list, consuming lists, predicates over lists |
| L07 | Producing lists | Filtering lists, transforming list, ordered lists |
| L08 | Big-O notation | Mathematical background, list abbreviations, measuring efficiency |
| L09 | Efficiency | Linear, quadratic, and exponential functions |
| L10 | Finalizing the rules | Indexing, recursion on two lists, accumulators |
| L11 | Lists of lists | Polygons, tables, subsets |
| L12 | Strings | Characters, string processing, dictionaries, association lists |
| L13 | Binary trees | Trees as a data abstraction, paths, binary search trees |
| L14 | General recursion | Euclid, Fibonacci, Collatz, setting limits, mutual recursion, merge sort |
| L15 | General trees | Arbitrarily nested lists, expression trees, atoms, quote notation |
| L16 | Local definitions | Heron's formula, benefits of local definitions, merge sort (again) |
| L17 | First-class functions | Producing and consuming functions, functions in lists, contracts |
| L18 | Lambda | Anonymous functions, substitution rules, stable sorting |