Mathematics and Computing Curricula 2001
Connections
Peter B. Henderson, Butler University, phenders@butler.edu
The final version of CC 2001
was published December 15, 2001 (http://www.acm.org/sigcse/cc2001/).
CC 2001 is the first computing
curriculum recommendation to require discrete mathematics in its core. It encourages the introduction of
computer-based mathematics early and emphasizes the importance of mathematics
throughout the curriculum. The connections
between CC 2001 and the goals of the math thinking group are detailed here
through explicit highlighting and explanatory comment links. The key sections of CC 2001 quoted below
are:
Section 9.1.1 Mathematical rigor
Section 7.4 Integrating
discrete mathematics into the introductory curriculum
Section 5.2 Discrete Structures topics
I hope you find this
document useful and would appreciate receiving your comments, thoughts and
feedback.
Mathematics techniques and formal mathematical reasoning are integral to most areas of computer science. The Computing Curricula 1991 report identified theory as one of the three primary foundations of computer science, and we believe strongly that the same principle holds true today. Computer science depends on mathematics for many of its fundamental definitions, axioms, theorems, and proof techniques. In addition, mathematics provides a language for working with ideas relevant to computer science, specific tools for analysis and verification, and a theoretical framework for understanding important computing ideas. For example, functional programming and problem solving draw directly upon the mathematical concepts and notations for functions; algorithmic analysis depends heavily on the mathematical topics of counting, permutations and combinations, and probability; discussions of concurrency and deadlock draw heavily from graph theory; and both program verification and computability build upon formal logic and deduction. Thus, it is critical for computer science programs to include enough mathematics so that students understand the theoretical underpinnings of the discipline.
Given the pervasive role of
mathematics within computer science, the CS curriculum must include
mathematical concepts early and often. Basic mathematical concepts should be
introduced early within a student's course work, and later courses should use
these concepts regularly. While different colleges
and universities will need to adjust their prerequisite structure to reflect
local needs and opportunities, it is important for upper-level computer science courses to
make use of the mathematical content developed in earlier courses. This dependency, moreover, should be reflected in the
formal prerequisite structure.
In developing these recommendations, the CC2001 Task Force has
concluded that computer science programs must take responsibility for ensuring
that students get the mathematics they need,
especially in terms of discrete mathematics. To this end, the CC2001 report defines a new knowledge
area consisting of the discrete mathematics required for an undergraduate
program. That area -- Discrete Structures (DS)
-- specifies the units and topics that we believe are essential to every
undergraduate program. The material on discrete structures can be presented in
separate courses or integrated more directly into the curriculum by presenting
the mathematical material together with the computer science topics that depend
on it. In either case, it is essential
to make sure that the curriculum emphasizes the use of discrete mathematical
techniques throughout the undergraduate curriculum.
The CC2001 Task Force makes the following recommendations with respect to the mathematical content of the computer science curriculum:
· Discrete mathematics. All
students need exposure to the tools of discrete mathematics. When possible, it
is best for students to take more than one course in this area, but all programs
should include enough exposure to this area to cover the core topics in the DS
area. Strategies for integrating discrete mathematics into the introductory
curriculum are discussed in section 7.4.
· Additional mathematics.
Students should take additional mathematics to develop their sophistication in
this area. That mathematics might consist of courses in any number of areas
including statistics, calculus, linear algebra, numerical methods, number
theory, geometry, or symbolic logic. The choice should depend on program
objectives, institutional requirements, and the needs of the individual
student.
Section 9.1.1 Explanatory
Comments:
Mathematics techniques and formal mathematical reasoning are integral to most areas of computer science.
Peter Henderson: Mathematical
reasoning encourages clarity of thinking.
Mathematics techniques provide the foundations required for modeling and
reasoning about computer-based problems and systems. All problems can be viewed from a mathematical perspective to
gain a better understanding of the problem and identify potential
solutions. An algorithm or computer
program is simply a mathematical model for solving a problem. Accordingly, reasoning about an algorithm
or computer system is analogous to reasoning about a mathematical object. Students who are able to think
mathematically have a powerful tool for understanding and problem-solving.
Illustration: Mathematical reasoning reinforces abstraction
techniques which are important for computer based problem solving
mathematics provides a language for working with ideas relevant to computer science, specific tools for analysis and verification, and a theoretical framework for understanding important computing ideas.
Peter Henderson:
Mathematics is a language, a language whose attributes are fundamental to the
study of computer science. For example,
there are strong connections between mathematical symbols and
identifiers/variables, mathematical structures and data structures, logical
reasoning and computer-based problem-solving, and much more. Mathematics is a language for representing
and thinking about abstract ideas computer software is inherently abstract by
nature. Solving computer-based
problems often requires the precise, rigorous and logical thinking embodied by
mathematics. The language of
mathematics complements and enhances the language of computers. It provides an important tool for understanding.
Illustration: Students learn the fundamental concepts of
iteration but fail to understand the important connections between iteration,
mathematical induction, mathematical logic, iteration invariants and recursion.
Mathematical thinking can be used to
develop, reason about and debug iterative and recursive constructs.
Given the pervasive role of mathematics within computer science, the CS curriculum must include mathematical concepts early and often. Basic mathematical concepts should be introduced early within a student's course work, and later courses should use these concepts regularly.
Peter Henderson:
The important connections between mathematics and computer science are often
made too late, or weakly at best in CS curricula. By introducing mathematics early and continually reinforcing the
concepts students not only gain an appreciation for mathematics but also learn
to use it as an effective tool for thinking, abstraction and problem
solving.
Illustration: Logic, be it formal or informal, is required
for reasoning about algorithms and software systems. Formal mathematical logic
provides a powerful tool for reasoning when less formal or seat of the pants approaches
will not suffice. Without exposure to formal mathematical
thinking, students are lacking important cognitive tools for reasoning precisely
about problems and their solutions, applying formal techniques for modeling, specification,
design and testing, and thinking about
problems from different perspectives.
it is important for upper-level computer science courses to make use of the mathematical content developed in earlier courses.
Peter Henderson:
There are several threads of thought here: What mathematical content should be
introduced early? How is it introduced early?
How is this mathematics used and reinforced in upper-level courses? A closer look at upper-level courses will
reveal the important mathematical content each requires as a prerequisite, to
be reinforced in that course, and new mathematical content to be
introduced. Looking back from this perspective the CC 2001 mathematics core provides
an excellent foundation. Our goal as
educators is to not only to find more effective ways to teach these foundations,
but also to integrate, reinforce and introduce mathematical content into all
computer science courses for majors.
Illustration: Relational
algebra, introduced in a database course, builds on the concept of mathematical
relations and introduces new, useful modes of applying mathematical thinking.
students get the mathematics they need, especially in terms of discrete mathematics.
Peter Henderson:
Computer science and software engineering curricula today downplay mathematics
or place disproportionate emphasis on continuous mathematics (e.g., calculus,
differential equations, multivariable calculus, etc). There is a mismatch
between the mathematics and the computer science taught. This leads students to question the role
mathematics plays in their CS education.
Even curricula emphasizing discrete mathematics have difficulty making
the relevant connections. Mathematics,
logical thinking and rigor are not carried over to the computer science
courses. Students naturally ask Why is
mathematics required?
Illustration: Most of the discrete math topics in the CC
2001 core are required foundations for specification languages such as Z and
Larch. Logic is fundamental to
understanding digital logic circuits. Mathematical
relations enhance understanding of database systems. Probability and counting are needed for the analysis of algorithms
and systems. Graphs and trees are used for
modeling and problem solving. And proof
techniques for increasing our confidence in and understanding of all software
systems.
it is essential to make sure that the curriculum emphasizes the use of discrete mathematical techniques throughout the undergraduate curriculum.
Peter Henderson:
Discrete mathematics needs to be
integrated throughout the curriculum to reinforce mathematical concepts, and to
make the important connections between mathematics and computer science. Too often mathematics and computer science
courses are taught isolated from one another and students fail to make connections
between the required mathematics courses and computer studies. This is due
partly to the immaturity of the discipline and partly to slow maturation of undergraduate
education in discrete mathematics.
Illustration: In
engineering curriculum mathematical foundations are introduced first and subsequent
courses use and build upon this foundations.
For example, a computer scientist should understand the discrete
mathematical principles underlying an iteration in the same way that an
electrical engineer understands the continuous mathematical principles
underlying a simple resistor capacitor circuit.
As we discuss in Chapter
9 , the CC2001 Task Force believes it is important for computer science
students to study discrete mathematics early in their academic program,
preferably in the first year. There are at least two workable strategies for
accomplishing this goal:
Peter Henderson: A third
strategy is to introduce discrete mathematics prior to the introductory sequence. This is the model used by most engineering
curricula in which students take calculus before rigorous engineering courses
(e.g., circuits, mechanics, etc.).
This approach has been used at the State University of New York at Stony
Brook and Butler University. It works
well when relevant connections are made between mathematics, problem-solving
and computer science in subsequent computer science and math courses. Also, the MAA
CUPM committee computer science report recommends calculus and discrete
mathematics being on an equal footing upon entry to college, and eventually
discrete mathematics being covered prior to college as an advanced placement
topic.
Discrete Structures (DS) {
Discrete Mathematics } [CC 2001 core concepts]
·
DS1.
Functions, relations, and sets
Discrete structures is
foundational material for computer science. By foundational we mean that
relatively few computer scientists will be working primarily on discrete
structures, but that many other areas of computer science require the ability
to work with concepts from discrete structures. Discrete structures includes
important material from such areas as set theory, logic, graph theory, and
combinatorics. The notion of formal, mathematical proof is a unifying theme
throughout the area.
The material in discrete
structures is pervasive in the areas of data structures and algorithms but
appears elsewhere in computer science as well. For example, an ability to
create and understand a formal proof is essential in formal specification, in
verification, and in cryptography. Graph theory concepts are used in networks,
operating systems, and compilers. Set theory concepts are used in software
engineering and in databases.
As the field of computer science
matures, more and more sophisticated analysis techniques are being brought to
bear on practical problems. To understand the computational techniques of the
future, today's students will need a strong background in discrete structures.
Finally, we note that while
areas often have somewhat fuzzy boundaries, this is especially true for
discrete structures. We have gathered together here a body of material of a
mathematical nature that computer science education must include, and that computer
science educators know well enough to specify in great detail. However, the
decision about where to draw the line between this area and the Algorithms and
Complexity area on the one hand, and topics left only as supporting mathematics
on the other hand, was inevitably somewhat arbitrary. We remind readers that
there are vital topics from those two areas that some schools will include in
courses with titles like discrete structures.