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.