CS 135: Designing Functional Programs

Winter 2018 Calendar

This page contains information on the rough timing of topics, assignment due dates, exam dates, and other important milestones. The selection and ordering of topics is correct except possibly at the very end, where somewhat more or less might be covered depending on timing. Due dates are also precise. The exact timing of lecture topics will almost certainly vary from this, and readings (all from the textbook, "How To Design Programs") are linked to the timing of lectures. DrRacket implements a series of language subsets, and the changes from one level to the next are noted under the heading "Language Level".

Week 1 (Week of January 3 - 10)

Module 1: Prefix notation. Translating expressions. Defining functions and constants.

Readings: Preface, Sections 1, 2.

Language Level: Beginning Student.

Assignment 00: Due Tuesday, January 9, 9:00PM

Week 2 (Week of January 11 - 17)

Module 2: The design recipe: contract, purpose, examples, definition, tests. Comparisons and predicates. Boolean functions and special forms. Short circuiting. Symbols and strings. Equality testing. Conditional expressions. Writing and testing conditional functions. Helper functions.

Readings: Sections 3-5.

Assignment 01: Due Tuesday, January 16, 9:00PM

Week 3 (Week of January 18 - 24)

Module 3: The semantics of Beginning Student. Stepping.

Module 4: Compound data. posns. Defining structures. Stepping with structures. Data definitions. Templates. Consuming and producing compound data.

Readings: Intermezzo 1, Sections 6, 7.

Assignment 02: Due Tuesday, January 23, 9:00PM

Week 4 (Week of January 25 - 31)

Module 4: Mixed data and union types. Checked functions.

Module 5: Defining lists. Basic list constructs. Box-and-pointer visualization of lists. Extracting values from a list. Semantics of list functions. Functions on lists. Processing lists. Recursive data definitions. Recursive functions. Tracing recursive functions. Structural recursion. Templates and design recipes for recursive data definitions and recursive functions. Useful list functions. Producing lists. Nonempty lists. Strings and lists of characters.

Readings: Sections 9, 10.

Assignment 03: Due Tuesday, January 30, 9:00PM

Week 5 (Week of February 1 - 7)

Module 5: Lists of structures.

Module 6: Natural numbers and recursion. Subintervals of natural numbers. Recursion on integers. Insertion sort. List abbreviations. Quoting lists. Lists containing lists. Lists versus structures. Kinds of lists. Dictionaries. Association lists.

Readings: Sections 11, 12, Intermezzo 2.

Language Level: Beginning Student with List Abbreviations.

Assignment 04: Due Tuesday, February 6, 9:00PM

Week 6 (Week of February 8 - 14)

Module 6: Two-dimensional data. Processing two lists simultaneously. Merging sorted lists. Consuming a list and a number. List equality.

Module 7: The limits of structural recursion. Preview of accumulative and generative recursion.

Module 8: Trees.

Readings: Section 17.

Assignment 05: Due Thursday, February 15, 9:00PM

Week 7 (Week of February 15 - 17 and February 25 - 28)

Module 8: Binary arithmetic expressions. Tree terminology. Characteristics of trees. Mutual recursion. Binary search trees. General trees. General arithmetic expressions.

Readings: Sections 14-16.

Week of Feburary 18 - 24 (Reading Week)

Family Day Holiday: Monday, February 19

No consulting hours on Family Day; revised consulting hours the rest of the week.

No lectures, no tutorials, no assigment due.

Midterm Exam: Monday, February 26, 7:00 - 8:50PM

Week 8 (Week of March 1 - 7)

Module 8: Other uses of general trees. Nested lists as leaf-labelled trees. Flattening a nested list.

Module 9: Local definitions. Semantics of local. Naming common subexpressions. Using local for clarity. Encapsulation. Terminology associated with local.

Readings: Intermezzo 3.

Language Level: Intermediate Student.

Assignment 06: Due Tuesday, March 6, 9:00 PM.

Week 9 (Week of March 8 - 14)

Module 10: Functional abstraction. Consuming functions. Producing functions. Putting functions in lists. Contracts and types. Simulating structures. Scope. Producing anonymous functions. lambda.

Readings: Sections 19, 20.

Language Level: Intermediate Student with lambda.

Assignment 07: Due Tuesday, March 13, 9:00PM

Week 10 (Week of March 15 - 21)

Module 10: Syntax and semantics of Intermediate Student with Lambda. Contracts for abstract list functions. Parametric types. Built-in abstract list functions. Building an abstract list function. foldr. Higher-order functions.

Module 11: Generative recursion. Termination.

Readings: Sections 21-23, Intermezzo 4, 25-27.

Assignment 08: Due Tuesday, March 20, 9:00PM

Week 11 (Week of March 22 - 28)

Module 11: Quicksort. Processing strings. More higher-order functions. foldl.

Module 12: Directed graphs. Backtracking algorithms. Graph terminology. Representing graphs. Structural recursion on graphs. Finding routes. Termination of find-route. Termination for DAGs. Backtracking in implicit graphs.

Readings: Section 28.

Assignment 09: Due Tuesday, March 27, 9:00PM

Week 12 (Week of March 29 - April 4)

Module 12: Making find-route efficient.

Module 13: History of topics covered in the course.

Readings: Sections 30, 31, 32.

Good Friday Holiday: Friday, March 29: No consulting hours or tutorials (postponed to Wednesday, April 4)

Assignment 10: Due Tuesday, April 3, 9:00PM

Wednesday, April 4: Friday class schedule - the last CS 135 Tutorial will be held on this day

Last day of UW classes for term: Wednesday, April 4

Last modified on Friday, 27 April 2018, at 19:04 hours.