Revised April 28, 2011
CS 145: Designing Functional Programs (advanced version)
(Emphasized text represents additional material not found in
CS 135.)
Goals
- To familiarize students with key concepts in introductory computer science;
- To prepare students to complete the CS portion of their Math
core requirements and, if desired, to continue on to second-year
core courses in CS;
- To provide top students with appropriate challenges and enrichment
and to explore topics in greater depth than possible in CS 135.
Logistics
Intended for 1A students in the Faculty of Mathematics.
Normally available Fall.
Related courses (see calendar for official details)
-
Successors: CS 146, 136, 116.
-
Conflicts: CS 115, 135, 137, 138.
Software used: Racket (dialect of Scheme).
Typical Reference(s)
M. Felleisen, R. Findler, M. Flatt, S. Krishnamurthi, How To
Design Programs.
Required preparation
The main prerequisites for CS 145 are aptitude and
enthusiasm. Prior experience is not required. Instructor consent is
required unless the student has achieved a mark of 80 in the Euclid
contest, or Honourable Mention or above on the senior Canadian
Computing Contest. Because of the lack of textbook support for much of
the enrichment material, listening comprehension skills are more
important than in CS 135 or the advanced Math courses.
Learning objectives
At the end of the course, students should have the ability to:
- given a clear and concise statement of
a problem or task, write a program from scratch of up to a hundred lines of
properly-formatted and documented Scheme code to solve the problem or carry
out the task;
- use elementary data structures such as lists and trees in such programs;
- use higher-order functions to improve readability and
efficiency of such programs;
- analyze the worst-case running time of such programs and describe
examples of data that demonstrate that the analysis cannot be improved;
- demonstrate their understanding of the implementation of
functional programming language features by coding small interpreters for
Scheme-like languages.
Typical syllabus
An introduction to functional programming
Function application and definition. Formal grammar and syntax. The
substitution model. Types in Scheme. Conditional
expressions. Structures. Lists. Types of recursion: structural,
accumulative, generative. Recursion on lists and integers. Algorithm
analysis.
Data abstraction
Immutable abstract data types. The table ADT. Association lists.
Binary trees and binary search trees. Braun trees. Mutual
recursion. Leaf-labelled and node-labelled
trees. S-expressions. Simple interpreters.
Functional abstraction
Functions as values. Anonymous functions. Higher-order
functions. Local definitions. Lexical scope. Interpreter
implementations.
Accumulative and generative recursion
Termination arguments. Efficiency. Invariants. String
processing. Graph algorithms.
Purely-functional data structures
Queues and deques. Braun heaps. Treaps.
Advanced programming
I/O in Scheme. Macros. Domain-specific
languages. Continuations. Continuation-passing style.
Last modified: Wednesday, 15-Feb-2012 10:21:29 EST
