By Allen Tucker
Curriculum development has been an obsession for the computer science education community during the last four decades, due to the enormous and rapid rate of evolution that has occurred in the discipline itself. During this period, the Association for Computing Machinery (ACM) has developed various curriculum standards for undergraduate programs, first in 1968, and then again in 1978 and 1991. A new standard was published in December 2001 (see http://www.acm.org/sigcse/cc2001/ for more information).
Central to each of these curriculum efforts is the important discussion of the role and flavor of mathematics within the computer science curriculum. Recently, the undergraduate mathematics curriculum committees (CUPM and CRAFTY) reached out to computer science educators and raised the central question, "what mathematics is needed for an undergraduate major in computer science, and how should it be taught?"
In response to this question, an eight-member panel of computer science educators gathered for the first of a series of Curriculum Foundations Workshops, which took place at Bowdoin College on October 28-31, 1999. The group included Owen Astrachan (Duke University), Doug Baldwin (SUNY Geneseo), Kim Bruce (Williams College), Peter Henderson (Butler University), Charles F. Kelemen (Swarthmore College), Dale Skrien (Colby College), Allen Tucker (Bowdoin College), and Charles Van Loan (Cornell University).
After a vigorous discussion, the panel developed a report that it believes reflects current thinking about the role of mathematics in the computer science curriculum. To provide a sense of the panel's findings, we summarize in this article the essential ideas in that report. The full report can be obtained at http://academic.bowdoin.edu/faculty/B/barker/dissemination/Curriculum_Foundations/.
In the first two years of a computer science major, students should be comfortable with abstract thinking and with mathematical notation and its meaning. They should be able to both generalize from examples and create examples from generalizations. To estimate the complexity of algorithms, they should understand functions that represent different rates of growth (e.g., logarithmic, polynomial, exponential). To reason effectively about the complexity and correctness of programs, they should gain facility with formal proofs, especially induction proofs. The same kind of clear and careful thinking and expression needed for a coherent mathematical argument is needed for the effective design of a computer program.
For mathematical problem solving skills, students should be able to represent "real-world" problem situations using discrete structures such as arrays, linked lists, trees, finite graphs, other multi-linked structures, and matrices. They should be able to develop and analyze algorithms that operate on these structures. They should understand what a mathematical model is and be able to relate mathematical models to real problem domains. General problem solving strategies such as divide-and-conquer and backtracking strategies are also essential.
For specific topics, students should master the following in their first two years: logical reasoning (propositions, DeMorgan's laws, including negation with quantifiers), functions, relations (equivalence relations and partitions), sets, notation for functions and for set operations, mathematical induction (structural, strong, weak), combinatorics, finite probability, asymptotic notation (e.g., O(n2) and O(2n)), recurrence/difference equations, graphs, trees, and number systems.
Later in their undergraduate careers, students should gain experience in the following topics in order to master additional intermediate and advanced computer science coursework:
differential and integral calculus, multidimensional calculus, and linear algebra, for scientific and numerical computing courses.
linear algebra (matrix algebra, change of coordinates), 3-dimensional calculus, and topics from geometry, for computer graphics courses.
induction and diagonalization proofs, the use of counterexamples and proof by contradiction, for algorithms and theory of computation courses.
speech understanding and synthesis algorithms use transforms.
compression algorithms use wavelets
encryption algorithms use group and ring theory
The panel's general conclusion is that undergraduate computer science majors need to acquire mathematical maturity and skills, especially in discrete mathematics, early in their college education. The following topics are likely to be used in the first three courses of a computer science major: logical reasoning, functions, relations, sets, mathematical induction, combinatorics, finite probability, asymptotic notation, recurrence/difference equations, graphs, trees, and number systems. Ultimately, calculus, linear algebra, and statistics topics are also used, but none of these is needed earlier than discrete mathematics. Thus, a discrete mathematics course should ideally be offered in the first semester of college, and its prerequisites and conceptual level should be the same as the Calculus I course.
Allen Tucker is Bass Professor of Natural Science at Bowdoin College. He was the local organizer for the Curriculum Foundations Workshop in Computer Science, held at Bowdoin College in October 1999.
This is one of a series of articles on Curriculum Foundations, a project of CRAFTY, the MAA Committee on Calculus Reform and the First Two Years. Earlier articles have described the project as a whole (FOCUS, November 2000) and the workshop on the mathematics courses needed by physics students (FOCUS, March 2001 and also online). Future articles will focus on other client disciplines. CRAFTY is a subcommittee of CUPM, the Committee on the Undergraduate Program in Mathematics, which is undertaking a review of the whole undergraduate curriculum.