tification must be properly framed in an introductory course
like DMFP. We can do this by writing algorithms that solve
a problem that is subtly quantified, such as testing whether
every integer in a list has its opposite (or additive inverse)
also in the list.
The exercises in the propositional calculus are but a warm-up for writing full-fledged mathematical proofs, which we do
in the fourth unit. Most proofs the students write are about
sets, with a few proofs about integers thrown in for variety.
The intersection of math and programming are less explicit at
this point, but still there. The students’ work on earlier programming assignments pays off, since those assignments by
now have helped students master set operations and, more
importantly, reason about quantified propositions. Additionally, a special topic in this unit traces how one can develop
algorithms from theorems, for example deriving the Division
Algorithm from the Quotient-Remainder Theorem. In that
case, a recursive implementation of the Division Algorithm is
a recurrent application of the theorem. See Figure 3.
That unit on proof-writing is the hinge of the course. The
remaining units introduce more things about which to write
proofs. The fifth unit, which presents relations, contains several points where programming supports the mathematical
concepts and proofs. There is more than one way to interpret
relations, and each way can be reflected in an approach to
representing relations as a data type. A (binary) relation is a
set of ordered pairs, so we represent it with a list of tuples.
Alternately, one can think of a relation as a two-place predi-
cate that is true for two items so related; thus, a relation can
be implemented as a function. But algorithmic thinking also
helps many students work through the mathematical defini-
tions. A concept like the transitive closure of a relation is a
challenge for students to wrap their minds around, but an ex-
ercise in computing the transitive closure of a given relation
operations like intersection and difference on two sets repre-
sented as lists. Moreover, this unit introduces powersets, which
students explore by writing a function to compute a powerset
from a given set—see Figure 2.
The third unit is on symbolic logic. As students learn the
propositional calculus, introducing boolean values and operators and conditional expressions is a pedagogical “gimme.” It
may be surprising that students will have been programming
for three weeks at this point, including recursive list-processing, without using any booleans, but ML’s pattern-matching
allows for making decisions without explicit conditionals.
Booleans and conditionals, of course, open a richer range of
problems they are now able to work on. While students are
simplifying propositional forms and verifying the validity of
arguments in their pencil-and-paper assignments, they are
also applying these ideas in writing algorithms. But I give
special attention to the topic of quantification, since I have
often observed in more advanced courses that the hardest
parts of the hardest proofs and programming problems come
down to how the proposition or problem is quantified. Quan-
I give special attention to the topic
of quantification, since I have
often observed in more advanced
courses that the hardest parts of
the hardest proofs and programming
problems come down to how the
proposition or problem is quantified.
Figure 3: Sample problems for proofs and relations