Part I: Procedural Abstraction

Computer scientists study the processing of information. In this first part of the book, we will focus our attention on specifying the nature of that processing, rather than on the nature of the information being processed. (The latter is the focus of Parts II and III.) For this part of the book, we will look at procedures for processing only a few simple kinds of data, such as numbers and images; in the final chapter of Part I, we will look at procedures for processing other procedures.

We'll examine procedures from several different viewpoints, focusing on the connection between the form of the procedure and the form of the process that results from carrying it out. We'll see how to design procedures so that they have a desired effect and how to prove that they indeed have that effect. We'll see various ways to make procedures generate ``expansible'' processes that can grow to accommodate arbitrarily large instances of a general problem and see how the form of the procedure and process influences the efficiency of this growth. We'll look at techniques for capturing common processing strategies in general form, for example, by writing procedures that can write any of a family of similar procedures for us.

Chapter 1: Computer Science and Programming

We open with a definition of computational processes and a list of questions that computer scientists ask about them. We then introduce procedures both as a way of abstracting these processes and also as a way of making them happen. In particular, we show how to write simple, non-recursive procedures in Scheme. Chapter 1 ends with a graphics application involving quilting, where students make a variety of quilt patterns.

Chapter 2: Recursion and Induction

All of the procedures in chapter 1 generated processes of a fixed size. Chapter 2 introduces students to recursion as a way of generating processes of varying sizes. Along with recursion, we introduce induction both as a way of proving that recursive procedures work and as an aid to designing recursive procedures. The application section extends the one from the first chapter, with the students being asked to construct quilts of varying sizes.

Chapter 3: Iteration and Invariants

We introduce iteration as an alternative to recursion, and show how an iterative process uses less memory than a recursive one. We illustrate how invariants can be used as a fundamental part of designing iterative procedures, show an example of iterative improvement of an approximation, and end with an application that uses iteration to model some historic killings that occurred nearly two thousand years ago, following the fall of Jotapata in 67 CE.

Chapter 4: Orders of Growth and Tree Recursion

In chapter 4, we begin to consider the time-complexity of procedures. We introduce the idea of asymptotics by having students physically sort sets of 4, 8, 16, and 32 cards using the selection sort and merge sort algorithms. In addition to examining the empirical data from this experiment, we use a priori analyses of these algorithms to motivate the precise definition of big-theta notation. Next, using the problem of cryptographic authentication as motivation, we write various procedures for modular exponentiation, and analyze their time and space complexity, until we have an iterative procedure that takes logarithmic time. The chapter ends with an application involving fractal curves.

Chapter 5: Higher-Order Procedures

We introduce higher-order programming first by considering procedures taking procedural parameters, then later by writing procedures that return procedures (procedure factories). We point out the limits to computability by giving Turing's argument on the uncomputability of the halting problem. The application section illustrates higher-order programming by having the students write a procedure that generates procedures for checking the validity of various self-verifying identifying numbers, such as ISBN, credit card, and UPC numbers.
This is a portion of the annotated table of contents for the textbook Concrete Abstractions: An Introduction to Computer Science Using Scheme, by Max Hailperin, Barbara Kaiser, and Karl Knight. Free access to the full text in PDF form and supporting materials are also available.