Discrete Mathematics and Theoretical Computer Science

TITLE: "Discrete Mathematics in the Schools"

EDITORS: Joseph G. Rosenstein, Deborah S. Franzblau and Fred S. Roberts. Published by the American Mathematical Society and the National Council of Teachers of Mathematics

A PostScript version of this document

As noted in the
**Preface**, this volume makes the case that
discrete mathematics should be included in K--12 classrooms and
curricula, and provides practical assistance and guidance on how this
can be accomplished. The organization of this volume parallels these
two goals. After the **Introduction**
the articles are arranged in
the following eight clusters:

- Section 1. The Value of Discrete Mathematics: Views from the Classroom
- Section 2. The Value of Discrete Mathematics: Achieving Broader Goals
- Section 3. What is Discrete Mathematics: Two Perspectives
- Section 4. Integrating Discrete Mathematics into Existing Mathematics Curricula, Grades K--8
- Section 5. Integrating Discrete Mathematics into Existing Mathematics Curricula, Grades 9--12
- Section 6. High School Courses on Discrete Mathematics
- Section 7. Discrete Mathematics and Computer Science
- Section 8. Resources for Teachers

Everyone's first question is of course, ``What is discrete
mathematics?'' Everyone's second question is, ``Why should I use
discrete mathematics?'' Explicit discussion of the first question is
delayed until Section 3, and the focus of the
**Introduction** and
Sections 1--2 is the second question. These sections make the
case for discrete mathematics --- from the perspective of teachers in
the classroom, and from the perspective of researchers involved in
improving mathematics education. These articles encompass a variety
of agendas --- implementing the four NCTM process standards
(problem-solving, reasoning, communicating mathematical ideas, and
making connections), improving the public's perception of mathematics,
conveying the usefulness of mathematics, and providing a new start for
students, teachers, and curricula.

Everyone's third question is, ``How can I use discrete mathematics in my classroom?'' This question is addressed in Sections 4--7. One set of responses involves incorporating discrete mathematics into existing curricula; these responses appear in Sections 4 and 5, arranged by grade level. Another set of responses involves introducing new courses, typically at the high school level, and these are addressed in Section 6. Section 7 addresses the role of computer science in the high school curriculum, as well as the role of discrete mathematics in the teaching of computer science.

Section 8 describes resources available to teachers who decide to enrich their classrooms with discrete mathematics.

Following are abstracts of the articles in this volume, prepared by the editors. The abstracts are arranged by section, and within each section are presented alphabetically, as are the articles in the volume.

Joseph G. Rosenstein's article **Discrete Mathematics in the
Schools: An Opportunity to Revitalize School Mathematics** serves as an
introduction to this volume and describes why discrete mathematics can
be a useful vehicle for improving mathematics education and
revitalizing school mathematics. He provides rationales for
introducing discrete mathematics in the schools, noting that discrete
mathematics is applicable, accessible, attractive, and appropriate,
and argues that discrete mathematics offers a ``new start'' in
mathematics for students. This article is based on a concept document
distributed to participants prior to the October 1992 conference, and
on the opening presentation of the conference.

Views from the Classroom

Bro. Patrick Carney's article **The Impact of Discrete
Mathematics in My Classroom** describes anecdotally how the author
aroused in his students an interest in mathematics, and developed in
his students a more ``positive attitude toward mathematics and their
ability to do it''.

Nancy Casey's article **Three for the Money: An Hour in the
Classroom** describes the excitement generated in a class of high
school students, participating in a special summer program, when they
are presented with an unsolved mathematical problem, and the
mathematical journeys that they take to learn what the problem is and
to try to solve it. It also provides a vivid description of how the
teacher's role in the classroom changes when the class embarks on an
uncharted adventure of mathematical discovery.

Janice C. Kowalczyk's article **Fibonacci Reflections: It's
Elementary!** is an account of her experiences giving a workshop on the
Fibonacci sequence (1, 1, 2, 3, 5, 8, ...) to a fourth-grade class.
She gives a detailed description of the workshop activities, including
student investigations of the classical rabbit population problem that
leads to the sequence, and spiral-counting in pinecones, sunflowers,
shells, and other objects whose growth patterns exhibit the sequence.
The article illustrates how using a topic with a strong visual appeal,
along with a focus on student exploration, can bring out the strengths
in many students who have had difficulties in the traditional
elementary mathematics curriculum.

Susan H. Picker's article **Using Discrete Mathematics to Give
Remedial Students a Second Chance** is an account of her experiences
introducing discrete mathematics to a class of remedial tenth-grade
students in Manhattan, and their success in solving complex
graph-coloring problems. More than that, it is an account of the
impact that this course had on the students' perceptions of
mathematics and their own abilities, as well as on their subsequent
school careers. The author learned from this experience the extent to
which students' dislike of arithmetic serves as an obstacle to their
progress and success in mathematics.

Reuben J. Settergren's article **``What We've Got Here is a
Failure to Cooperate''** describes a cooperative game, based on the
classical Prisoner's Dilemma, that the author played with
twelve-year-old students in a summer program. The game gave students
insight into why individuals are sometimes motivated to behave in a
way that harms the larger community, providing an opportunity to
discuss moral and social issues in a mathematics class.

Achieving Broader Goals

Nancy Casey and Michael R. Fellows' article **Implementing the
Standards: Let's Focus on the First Four** argues that in order to
properly address the NCTM process standards --- reasoning,
problem-solving, communications, and connections --- in the
elementary school classroom, new content must be introduced into the
K--4 mathematics curriculum. The authors show by example how
elementary versions of problem situations that arise in computer
science and discrete mathematics make it possible to realize the goals
of the process standards. They describe their approach to teaching
mathematics as parallel to the ``whole language'' approach to teaching
reading.

Margaret B. Cozzens' article **Discrete Mathematics: A Vehicle for
Problem Solving and Excitement** provides examples of discrete
mathematics activities from several curriculum development projects
funded by the NSF division that the author heads. The author argues
that discrete mathematics can motivate students to think
mathematically, to become better problem solvers, and to increase
their interest in mathematics.

Susanna S. Epp's article **Logic and Discrete Mathematics in the
Schools** argues that logical reasoning should be a component of the
discrete mathematics that is discussed at all grade levels. Students
should not have to wait until they are college students to explore the
reasoning involved in ``and'', ``or'', and ``if-then'' statements, or to
understand how quantifiers are used. This need not be done formally
(e.g., through truth tables) but through concrete activities which
ultimately will support the students' transition to abstract
mathematical thinking. The author illustrates the value of explicit
discussion of logic with experiences from a discrete mathematics
course she has taught at DePaul University.

Rochelle Leibowitz' article **Writing Discrete(ly)** argues that
discrete mathematics serves as an excellent vehicle for teaching
students to communicate mathematically. Through describing carefully
simple proofs and algorithms (e.g., instructions for building a Lego
model), students acquire technical writing skills that will be useful
in a variety of career and life situations.

Joseph Malkevitch's article **Discrete Mathematics and Public
Perceptions of Mathematics** contrasts the kinds of problems typically
discussed in high school mathematics classes, usually involving
extensive manipulation of symbols, with the kinds of problems that
manifest the ways in which mathematics influences daily life.
Malkevitch argues that the negative perceptions that the general
public has about mathematics arise in part from an unbalanced
mathematical diet --- too much of the former, too little of the
latter --- and notes that problems from discrete mathematics can play
an important role in changing these perceptions.

Henry O. Pollak's article **Mathematical Modeling and Discrete
Mathematics** discusses mathematical modeling in general, noting that
``applied mathematics'', ``problem solving'', and ``word problems'' all
start with an idealized version of a real world problem, and so
normally omit the initial and final parts of the modeling process.
The author notes that in discrete mathematics situations, however, it
is often possible to introduce the entire mathematical modeling
process into the classroom; he provides five examples of modeling
situations which lead to discrete mathematics and which can be made
accessible to high school students.

Fred S. Roberts' article **The Role of Applications in Teaching
Discrete Mathematics** notes that ``one of the major reasons for the great
increase in interest in discrete mathematics is its importance in
solving practical problems.'' The author introduces several ``rules of
thumb'' about the role of applications in teaching discrete
mathematics, and illustrates those by providing many applications of
the Traveling Salesman Problem, graph coloring, and Euler paths.

Stephen B. Maurer's article **``What is Discrete Mathematics?'' The
Many Answers** provides and discusses a variety of proposed definitions
and descriptions of discrete mathematics, along with several proposed
goals and benefits for including discrete mathematics in the schools.
The article concludes with a set of goals and topics for discrete
mathematics in the schools on which the author thinks there might be
general agreement.

Joseph G. Rosenstein's article **A Comprehensive View of Discrete
Mathematics: Chapter 14 of the New Jersey Mathematics Curriculum
Framework** contains a comprehensive discussion of topics of discrete
mathematics appropriate for each of the K--2, 3--4, 5--6, 7--8, and 9--12
grade levels. The author spearheaded the development of the Framework
in his role as Director of the New Jersey Mathematics Coalition.
Grade-level overviews are accompanied by several hundred activities
appropriate for the various grade levels. The material reflects the
experiences of teachers in the Leadership Program in Discrete
Mathematics, discussed in a separate article in Section 8.

Valerie A. DeBellis' article **Discrete Mathematics in K--2
Classrooms** describes the author's visits to several classrooms and
what she learned about the reasoning and problem-solving skills
exhibited by young children who are introduced to situations involving
discrete mathematics. It also describes how topics in discrete
mathematics can be reformulated for children at early elementary
levels.

Robert E. Jamison's article **Rhythm and Pattern: Discrete
Mathematics with an Artistic Connection for Elementary School
Teachers** describes the material that the author has used in programs
for both inservice and preservice elementary school teachers. It
focuses on how elementary school teachers can use geometric activities
involving drawing polygons and planar representations of
polyhedra, moving in geometric patterns, and using modular arithmetic
in movement and music --- to provide their students with foundational
experiences for future study of mathematics.

Evan Maletsky's article **Discrete Mathematics Activities in
Middle School** provides a wealth of activities that are appropriate at
the middle school level; these involve counting (e.g., finding the
triangular numbers when you count rectangles on a folded piece of
paper), graphs, and iteration (e.g., generating Sierpinski triangles).
The author discusses how these can be incorporated into the activities
that are already taking place in the classroom.

Robert L. Devaney's article **Putting Chaos into Calculus
Courses** describes how fundamental ideas of dynamical systems,
including iteration, attracting and repelling points, and chaos, can
be introduced in a beginning calculus class, through an in-depth
investigation of the behavior of Newton's Method, using a computer or
graphing calculator. The author's approach integrates discrete with
continuous mathematics and provides a connection from calculus to the
fascinating world of fractals and chaos.

John A. Dossey's article **Making a Difference with Difference
Equations** shows how difference equations can be used to model change
in a number of real-world settings. The author recommends the use of
difference equations to provide a unified development of standard
sequences studied in mathematics, such as arithmetic, geometric, and
Fibonacci sequences.

Eric W. Hart's article **Discrete Mathematical Modeling in the
Secondary Curriculum: Rationale and Examples from the Core-Plus
Mathematics Project (CPMP)** discusses the questions of what discrete
mathematics belongs in the secondary curriculum, and how it should be
incorporated, from the perspective of the curriculum developer. The
article presents examples adapted from CPMP materials which illustrate
the CPMP approach --- that discrete mathematics should be woven into
an overall integrated mathematics curriculum, and that the emphasis
should be on discrete mathematical modeling.

Bret Hoyer's article **A Discrete Mathematics Experience with
General Mathematics Students** describes how the author introduced
topics in discrete mathematics first into intermediate algebra and
geometry classes, and then, as a result of the students' positive
experiences, into other classes as well --- including general
mathematics and consumer mathematics courses. The article focuses on
the ``Street Networks'' unit on Euler paths and circuits that was woven
into these courses.

Philip G. Lewis' article **Algorithms, Algebra, and the Computer
Lab** describes how the author's high school students used the LOGO
computer environment to explore and develop concepts in linear
algebra. These explorations, which took place in a computer lab,
enabled students to view linear algebra algorithmically and to learn
how to construct and analyze algorithms.

Joan Reinthaler's article **Discrete Mathematics is Already in
the Classroom --- But It's Hiding** argues that many problems in high
school courses are discussed as problems with continuous domains when
a discrete perspective would be more realistic, and would lead to
different investigations and solutions. Several examples are given
involving standard textbook problems in algebra.

James T. Sandefur's article **Integrating Discrete Mathematics into
the Curriculum: An Example** describes how he uses the handshake
problem to review with his precalculus class the notions of function,
domain and range, and graphing quadratic functions. The author argues
that ``this approach integrates discrete mathematics into the existing
curriculum, results in deeper student understanding, and can be
accomplished in about the same amount of time as is presently
devoted to these topics.''

Harold F. Bailey's article **The Status of Discrete Mathematics in
the High Schools** reports on a survey that the author did to ascertain
how many high schools offer courses in discrete mathematics, what
those courses contain, and the goals of the schools in offering such
courses.

L. Charles Biehl's article **Discrete Mathematics: A Fresh Start
for Secondary Students** describes a project-based discrete mathematics
course developed by the author for juniors and seniors of average
ability. The students explored a variety of mathematical topics in
real-world settings; moreover, since many topics in discrete
mathematics have few prerequisites, these students were able to become
successful problem solvers and to develop more positive attitudes to
mathematics. The article includes an outline of the course.

Nancy Crisler, Patience Fisher, and Gary Froelich's article
**A Discrete Mathematics Textbook for High Schools** describes the
textbook they have co-authored, providing a discussion of its origins
and development. The organization and content of the book is based on
the NCTM report, *Discrete Mathematics and the Secondary
Mathematics Curriculum*; it addresses five broad areas (social
decision making, graph theory, counting techniques, matrix models, and
the mathematics of iteration) and interweaves six unifying themes
(modeling, use of technology, algorithmic thinking, recursive
thinking, decision making, and mathematical induction). The article
includes summaries of and examples drawn from each chapter of the
book.

Peter B. Henderson's article **Computer Science, Problem Solving,
and Discrete Mathematics** addresses the role of discrete mathematics
in a first course in computer science, based on the author's
experience in developing a ``Fundamentals of Computer Science'' course
at SUNY Stony Brook. Although the course described was developed
originally for students planning a career in computer science, it has
drawn students with a wide variety of goals. The author notes that
``With its emphasis on logical reasoning and problem analysis and
solution, discrete mathematics provides a catalyst for general
thinking and problem-solving skills ...,'' making such a course
valuable for teaching computer science to high school students as
well.

Viera K. Proulx' article **The Role of Computer Science and
Discrete Mathematics in the High School Curriculum** identifies six key
themes in computer science that the author argues should be taught to
all high school students, and sketches activities for students to
explore these themes. The ideas in the article grew out of the
author's participation in the Association for Computing Machinery
(ACM) Task Force on the High School Curriculum, which produced a
``Model High School Computer Science Curriculum'' in 1993.

Nathaniel Dean and Yanxi Liu's article **Discrete
Mathematics Software for K--12 Education** describes two workshops
involving teachers and software developers in which teachers solved
problems using software developed for research, and shared their
reflections on the features that would make such software useful in
their classrooms. In the first workshop, teachers used NETPAD,
written by Dean when he was at Bellcore; in the second workshop,
teachers used Combinatorica, written by Steven Skiena of SUNY Stony
Brook. The article also provides an annotated list of other software
packages that are potentially useful to teachers.

Deborah S. Franzblau and Janice C. Kowalczyk's article
**Recommended Resources for Teaching Discrete Mathematics** identifies
outstanding resources, including books, modules, periodicals,
literature, Internet sites, software, and videos for the K--12
mathematics teacher or supervisor building a core resource library for
teaching topics in discrete mathematics. There are extensive reviews
of four popular textbooks; other resources are accompanied by briefer
descriptions. The list of resources, which is indexed by topic and
grade level, and which includes publisher information, was developed
from recommendations by participants and instructors in the DIMACS
Leadership Program in Discrete Mathematics.

Joseph G. Rosenstein and Valerie A. DeBellis' article **The
Leadership Program in Discrete Mathematics** describes the
DIMACS-sponsored programs for K--12 teachers that have taken place for
the past nine years at Rutgers University, the development and
implementation of the program's goals, and how the program is serving
as a continuous resource for the dissemination of discrete mathematics
to K--12 schools.

Mario Vassallo and Anthony Ralston's article **Computer Software
for the Teaching of Discrete Mathematics in the Schools** provides a
number of criteria for judging the suitability of computer software
for educational use, and then describes and evaluates three software
systems (Mathematica/Combinatorica, GraphPack, and SetPlayer) against
these criteria.