Revised December 11, 2013

CS 145: Designing Functional Programs (advanced version)

(Emphasized text represents additional material not found in CS 135.)

General description

This course introduces students to key concepts in the field of Computer Science, prepares students to complete the CS portion of their Math core requirements and, if desired, continue on to second-year core courses in CS, provides top students with appropriate challenges and enrichment, and explores topics in greater depth than is possible in CS 135.

Logistics

Audience

• 1A students in the Faculty of Mathematics

Normally available

• Fall

Related courses

• Successors: CS 146, CS 136, CS 116
• Conflicts: CS 135, CS 137

For official details, see the UW calendar.

Software/hardware used

• Racket (dialect of Scheme)

Typical reference(s)

• M. Felleisen, R. Findler, M. Flatt, S. Krishnamurthi, How To Design Programs, MIT Press

Required preparation

At the start of the course, students should be able to

• Demonstrate an aptitude in mathematics with a mark of 80 or higher in the Euclid contest, or demonstrate an aptitude in CS through being placed in Group 2 or higher in the senior Canadian Computing Contest, or provide the instructor with sufficient evidence of suitability to gain consent to enroll
• Demonstrate above-average communication skills (listening, reading, writing) due to the lack of textbook support for much of the enrichment material

Learning objectives

At the end of the course, students should be able 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 code in a functional programming language to solve the problem or complete the task
• Use elementary data structures, such as lists and trees, in programs
• Use higher-order functions to improve readability and efficiency of programs
• Analyze the worst-case running time of 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  
• Substitution model  
• Types in Scheme  
• Conditional expressions  
• Structures  
• Lists  
• Types of recursion: structural, accumulative, generative  
• Recursion on lists and integers 
• Unary representation of integers
• Proving properties of programs
• Algorithm analysis
• Representations of sets

Functional abstraction

• Functions as values  
• Anonymous functions  
• Higher-order functions  
• Local definitions  
• Lexical scope  
• Simplifying the language  

Data abstraction

• Braun trees  
• Binary representation of integers
• Mutual recursion  
• Immutable abstract data types  
• Map ADT  
• Association lists  
• Binary trees and binary search trees  
• Leaf-labelled and node-labelled trees  
• S-expressions  
• Interpreters  
• Limits to computation  

Accumulative and generative recursion

• Termination arguments  
• Efficiency  
• Invariants  

Purely-functional data structures

• Priority Queue ADT and Braun heaps  
• Efficient maps: treaps, red-black trees, AA trees