Course Outline

Description

How do you design a computer program to build a world when you don’t know in advance how big that world will get? A snake eats and grows longer, segment by segment. A fleet of alien invaders fills the screen, each one tracking its own position and trajectory. A dictionary contains a quarter of a million words, and your program needs to search through all of them. This course teaches you to design programs that work correctly no matter how much data shows up.

Starting from the design skills you developed in CS1, you’ll tackle a major interactive project in Racket chosen by the class. You might build a Snake game where the worm grows with every meal and dies if it collides with itself. Or a simplified Tetris where blocks drop, stack, and clear completed rows. Or a full version of Spacewar! where both ships fire volleys of torpedoes, dodge each other’s shots, and spiral around a star’s gravity well. Whichever you choose, you’ll learn to process real-world data at scale, from game elements to music libraries to natural language.

The second half of the course turns to abstraction: the art of recognizing when two programs are almost the same and collapsing them into one. You’ll discover that functions can consume other functions, a deceptively simple idea that eliminates enormous amounts of repetition and is one of the most powerful tools in all of programming. These ideas appear in every serious programming language and form the conceptual backbone of modern software design. CS1: Spacewar!, or equivalent, is a prerequisite for this course.

Learning Objectives

1. Design self-referential data definitions to represent information of arbitrary size, and use the revised design recipe to write functions that process such data.
2. Build interactive programs of increasing complexity through iterative refinement, adding features one at a time while keeping the program working at every stage.
3. Decompose complex problems using wish lists and design by composition, breaking large programs into small, independently testable functions.
4. Abstract over similar functions by introducing parameters, including parameters that are themselves functions.
5. Use existing abstractions such as map, filter, and fold to write concise programs that process lists without explicit recursion.
6. Work with local definitions and lambda expressions to organize programs and express abstractions cleanly.
7. Process real-world data, including dictionaries and structured records, applying the design method to problems of practical scale.