Discrete Mathematics for Computer Science: What, How Much, Who, When
Notes by Henry M. Walker
Department of Mathematics and Computer Science
Grinnell College
Presentation to Iowa Undergraduate Computer Science Consortium
Saturday, October 12, 2002
Talk Outline
Sources of Information/Reports
Conferences/Workshops

Curricular Foundations Project:
disciplinary workshops, sponsored by the MAA Committee on the Undergraduate
Program in Mathematics (CUPM) and its Subcommittee on Calculus Reform and
the First Two Years (CRAFTY)

series of disciplinary workshops to identify mathematics needs in the first
two years

11 workshops held October 1999 through 2001, producing 17 reports
(Tom Moore coordinated the Statistics workshop here at Grinnell in October 2000)

Workshop Report for Computer Science

Meeting of the Liberal Arts Computer Science
Consortium, August 2002 at Grinnell College

Curricular Foundations Workshop, sponsored by the West Point Military
Academy and Project INTERMATH, October 36, 2002
Reports

Report of Group 2: Supporting Courses, Draft 5.2, July 7, 2000 of
Pedagogy Focus Group 2, Supporting Courses, of Computing Curricula
2001

Computing Curricula 2001: Computer Science Volume, ACM/IEEECS
Computing Curricula 2001 Task Force, December 15, 2001

Core Mathematics Curriculum Reform at Harvey Mudd College

Draft CRAFTY Report: A Collective Vision: Voices of the Partner
Disciplines: Summary of Recommendations, to be released in
midOctober/November 2002

Draft CUPM Report: Undergraduate Programs and Courses in the Mathematical
Sciences: A CUPM Curricular Guide, to be released in January 2003
Correspondence/Dialog with Groups and Individuals

Mathematical Thinking Group

Liberal Arts Computer Science Consortium
and its Subgroup on Discrete Mathematics

Pedagogy Focus Group 2: Supporting Courses (PFG2) of Computing Curricula 2001

William Barker, Bowdoin College and CRAFTY CoChair

Kim Bruce, Williams College, PFG2 member, and member of the LACS
Subgroup on Discrete Mathematics

Scot Drysdale, Dartmouth College and member of the LACS Subgroup on
Discrete Mathematics

Susanna Epp, DePaul University, member CUPM, and member CRAFTY

Peter Henderson, Butler University and Leader, Mathematical Thinking Group
within the Computer Science Community

Charles Keleman, Swarthmore
College, LACS Member, participant in CRAFTY Curricular Foundations
Project in CS and in West Point Workshop

William Marion, Valparaiso University, member of the Mathematical Thinking
Group, and PFG2 member

Harriet Pollatsek, Mt. Holyoke College and CUPM Chair

Allen Tucker,
Bowdoin College, LACS member, participant in CRAFTY Curricular Foundations
Project in CS and in West Point Workshop
Areas of Widespread Agreement
Goals of a Mathematics Curriculum
The work of CRAFTY/CUPM with client disciplines has led to a nice statement
of goals for undergraduate mathematics.

Draft Vision, October 6, 2002

It is interesting how various independent groups at the recent West Point
Workshop came to consistent conclusions
Importance of Discrete Mathematics in the First Two Years

Clear need for substantive coverage of discrete mathematics for computer science as a client
discipline (Computing Curricula 2001, CUPM Draft Report, CRAFTY Draft
Vision Statement)

Need for a year sequence in discrete mathematics  likely in the first two
years (CUPM Draft Report, Pedagogy Focus Group 2 Draft Report, LACS Meeting
in Summer 2002 and subsequent discussions)
Topics Desired in the Discrete Mathematics Sequence (at least for CS)

Topics from Pedagogy Focus Group 2

Course notes:

NOT remedial in level or scope

Need to emphasize proofs and proof techniques

Need to integrate theory and applications

Consistent with Curriculum Foundations Project Report for Computer
Science

Largely consistent with LACS discussions

Watered down somewhat in Computing Curricula 2001, but same general
approach
Need for Computer Science Students to Take an Additional Semester of Math

Mathematical maturity needed beyond 2 semesters

Subject of third semester depends on student interests/demands of later
computer science courses:

students interested in graphics might take linear algebra

students interested in operating systems might take probability and
statistics

students interested in simulation might take calculus

students interested in applications might take mathematical modeling
Issues
Several questions arise in considering discrete mathematics in the
mathematics curriculum. Some basic questions are:

To what extent do mathematicians believe discrete mathematics is important
for mathematics majors?

Do faculty in client disciplines mean the same thing as mathematicians in
identifying topics?

Example: for computer scientists, induction on structures and
substructures is more common and important than induction on the integers

How does discrete mathematics fit within the mathematics curriculum through
the first two years?
Approaches for Including Discrete Mathematics in the Mathematics Curriculum
The basic problem is that mathematicians and various client disciplines
have diverse needs.

Potential physics and engineering majors: differentiation and
integration of functions of 1 variable, applications, techniques of
integration, sequences and series, vectors and vector motion, partial
differentiation, multiple integration, linear algebra, differential
equations

Potential biology, economics, other(?) majors: differentiation and
integration of functions of 1 variable, applications, statistics, partial
differentiation, multiple integration, [possibly linear algebra]

Potential computer science majors: introduction to logic and proofs
(with some emphasis on structural induction), Boolean algebra, functions,
relations, and sets, basic number theory and number systems, cardinality
and counting, introduction to graphs, basic properties of matrices,
basic order analysis, introduction to computability,
elementary probability and statistics

Potential mathematics majors: traditionally, same as potential
physics and engineering majors, although some options include statistics or
discrete mathematics
Three basic approaches
Realistically, there seem to be three curricular approaches to address the
needs of diverse audiences.

Integrate continuous and discrete mathematics in a common [2year] sequence

Offer independent/disjoint courses in continuous mathematics, statistics,
and discrete mathematics

Organize separate courses in continuous mathematics, statistics, and
discrete mathematics to take advantage of common approaches [and topics]
Each approach seems to have its own advantages and disadvantages.
An Integrated Continuous/Discrete Mathematics Sequence
Basic Idea: Combine continuous and discrete mathematics in a highly
integrated sequence (perhaps including some probability and statistics)

Reorganize calculus, linear algebra, and differential equations

Add some topics from discrete mathematics early

Example: Core Mathematics Curriculum Reform at Harvey Mudd
College
Example: West Point apparently trying a similar approach

Advantages:

The common 2year sequence works well for many disciplines

Topics can be introduced "justintime" for many disciplines

Since all students take the same sequence, advising is relatively easy

Disadvantages:

At both Harvey Mudd and West Point, computer science majors still must take
a fifth course in discrete mathematics (and maybe a sixth) to get the
proper background

Details of the Harvey Mudd core assume high school students will have
completed a full year of calculus before college
Variation: Add some discrete mathematics topics to
existing courses

In precalculus, provide a different context for existing topics (in much
the same way as a slowpaced calculus course)
(suggested by Shelly Gordon, SUNY at Farmingdale)

In calculus, provide modest coverage of a few topics (e.g., difference
equations)

Advantages:

Difference equations can help motivate differential equations

Experience with proofs may seem more natural when considering relatively
simple examples from discrete mathematics

Disadvantages:

All evidence suggests that this approach cannot cover enough discrete
mathematics to meet the needs of computer science, so CS students still
must take another course

If discrete mathematics covered in precalculus, then well prepared CS
students might have to take precalculus for the discrete mathematics 
even though they are ready for a more rigorous course
Independent and Disjoint Courses
This approach seems quite common in many colleges and universities.
Separate tracks of courses are offered for continuous mathematics,
statistics, and discrete mathematics. One such variation follows.

Sometimes calculus II is a prerequisite for calculus III, but the above approach
resolves some scheduling problems for nonCS majors

Potential physics and engineering students take calculus I and all courses
underneath it.

Potential biology, economics, and other socialscience majors take calculus
I, calculus III, statistics, and possibly linear algebra.

Potential mathematics take calculus and many of its following courses 
perhaps with a few options added.

Advantages: Structure is reasonably efficient for nonCS majors

Social and biological science folks take 23 courses, skipping calculus II

Physics and engineering folks take 45 courses

Mathematics folks have needed courses with or without prerequisites

Disadvantages:

Potential CS students must follow a different track than all others
[discrete mathematics]

Students unsure of their eventual major may begin in courses that are not
helpful

While taking the wrong sequence first might provide useful general
background, it takes time, may use a slot better devoted to another
subject, and delays learning of essential topics.
Separate Continuous/Discrete Courses With Some Sequencing
Difficulties in advising incoming students can be deferred if all students
begin with the same mathematics courses, but with possible branching in a
second year.
Approach 1: Tony Ralston et al in early 1980s

Proposal, largely from Conference on Discrete Mathematics in the
Mathematics Curriculum, Williams College, June 1982

1 semester: calculus with discrete mathematics
1 semester: discrete mathematics
2 semesters: calculus and linear algebra

early treatment of discrete mathematics added breadth and emphasis on
proofs

reaction to perceived dismal state of calculus (before calculus reform)

historically, calculus reform took a different approach

Observation: early coverage of discrete mathematics delayed calculus and
differential equations needed by physics, engineering, etc.

Result: this approach in wide disuse today
Approach 2: Currently in Use at Grinnell
Grinnell's current curriculum moves discrete mathematics to the second
semester of the sophomore year, with a calculus/linear algebra prerequisite.

Advantages:

Incoming students have a common mathematics track, regardless of potential
major

Discrete mathematics covered at a relatively sophisticated level

Students need not choose continuous or discrete math until their interests
have matured (at least somewhat)

Physics and CS majors can follow different tracks after linear algebra

Both differential equations and combinatorics satisfy some prerequisites
for various upperlevel mathematics courses.

Disadvantages:

CS students study discrete mathematics relatively late

CS students must take 3 semesters of mathematics before getting to the
topics most relevant to their interests

The lengthy prerequisite chain makes the addition of a second semester of
discrete mathematics difficult.

Students starting mathematics late have a difficult time catching up.
Conclusions

General agreement on the need for discrete mathematics for computer
science 
with mixed signals regarding the role of discrete mathematics for math
majors

Considerable agreement on much of the body of material within discrete
mathematics needed for computer science

Great difficulty in organizing a mathematics curriculum to meet the diverse
needs of math majors and client disciplines
the "7 into 4" problem

Some combination of an initial mathematics sequence followed by branching
may yield a acceptable compromise for mathematical background and for advising
This document is available on the World Wide Web as
http://www.walker.cs.grinnell.edu/curriculum/discretemathiowa.html