Discrete Mathematics for Computer Science: What, How Much, Who, When

Talk Outline

• Sources of information

• Areas of widespread agreement regarding discrete mathematics

• Some open issues

• Approaches for including discrete mathematics in the mathematics curriculum

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 3-6, 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/IEEE-CS 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 mid-October/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 Co-Chair
• 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

• 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

• 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?
  • "All politics is local"

Approaches for Including Discrete Mathematics in the Mathematics Curriculum

• 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

1. Integrate continuous and discrete mathematics in a common [2-year] sequence
2. Offer independent/disjoint courses in continuous mathematics, statistics, and discrete mathematics
3. 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

• 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 2-year sequence works well for many disciplines
  • Topics can be introduced "just-in-time" 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

• In precalculus, provide a different context for existing topics (in much the same way as a slow-paced 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

• Sometimes calculus II is a prerequisite for calculus III, but the above approach resolves some scheduling problems for non-CS majors
  • Potential physics and engineering students take calculus I and all courses underneath it.
  • Potential biology, economics, and other social-science 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 non-CS majors
  • Social and biological science folks take 2-3 courses, skipping calculus II
  • Physics and engineering folks take 4-5 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

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 upper-level 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/discrete-math-iowa.html

created October 7, 2002 last revised October 9, 2002
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.