At my institution, Grand Valley State University (GVSU), if you go straight out the door of the Department of Mathematics,
and go all the way to the other end of the long hallway that you’re in,
then you’ll reach my department, Computing and Information Systems:
Thus — from one end of that hallway to the other — there’s sort of a face-off between Mathematics and Computer Science:
 |
 |
| Carl Friedrich Gauss | Dennis M. Ritchie |
Along this vein, if a student majors in Mathematics during college but then switches to Computer Science for graduate school, as I did, then a perspective I’ve heard from Mathematics faculty is that the student has ‘gone over to the dark side’. (;-)
While I am in the field of Computer Science, I love Mathematics, so one course I teach is “Discrete Structures: Computer Science [1]“. Now, some notes regarding this course are as follows:
- A catalog description of such a course is as follows: “This course covers the mathematical foundations of Computer Science. Topics include propositional and predicate logic, set theory, counting techniques, relations and functions, and mathematical induction.”
- Computer Science Curricula 2013 presents “Discrete Structures” as a Knowledge Area, saying the following:
Discrete structures are 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. [...] 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 proof—either a formal symbolic proof or a less formal but still mathematically rigorous argument—is important in virtually every area of computer science, including (to name just a few) formal specification, verification, databases, and cryptography. Graph theory concepts are used in networks, operating systems, and compilers. Set theory concepts are used in software engineering and in databases. Probability theory is used in intelligent systems, networking, and a number of computing applications.
What might be more attention-grabbing is that CS Curricula 2013 allocates 37 Core-Tier1 hours plus 4 Core-Tier2 hours totaling 41 Core hours for “Discrete Structures”, an amount which is a close second after the Knowledge Area “Software Development Fundamentals” which is allocated 43 Core-Tier1 hours, and a significantly greater amount than other Knowledge Areas (the next largest amount is 28).
- The most popular textbook for such a course is Discrete Mathematics and Its Applications, by Kenneth Rosen. Other introductory textbook authors include Susanna S. Epp, Richard Johnsonbaugh, Judith L. Gersting, and Alfred V. Aho and Jeffrey D. Ullman. The cover of the textbook by Aho & Ullman (which is dated 1994) is as follows:
This book’s Preface says the following:“About the Cover”
It is a tradition for computer science texts to have a cover with a cartoon or drawing symbolizing the content of the book. Here, we have drawn on the myth of the world as the back of a turtle, but our world is populated with representatives of some of the other, more advanced texts in computer science that this book is intended to support. They are:- the teddy bear: R. Sethi, Programming Languages: Concepts and Constructs
- the baseball player: J. D. Ullman, Principles of Database and Knowledge-Base Systems
- the column: J. L. Hennessy and D. A. Patterson, Computer Architecture: a Quantitative Approach
- the dragon: A. V. Aho, R. Sethi, and J. D. Ullman, Compiler Design: Principles, Techniques, and Tools
- the triceratops: J. L. Peterson and A. Silberschatz, Operating Systems Concepts
For a long time, I bought into those perspectives that introductory discrete mathematics is “foundational” for Computer Science. So when I’ve taught this course, I’ve made students fill truth tables, use quantifiers, write proofs by induction, and so on. In fact I even developed some software for constructing proofs, and I made students learn how to use it.
And I was happy. But… I nonetheless kept feeling a need to tinker with this course. So, at different times I tried different textbooks; or I spent a lot of class time on the number theory which is the basis for RSA encryption as a motivating example; or I tried to change things up other ways. And while one might say that symbolic logic and doing proofs can be a unifying theme for this material, I realized that what I was teaching was actually various disconnected topics — and students weren’t using them much in their subsequent college courses or jobs. How often does any CS student in college write a universal quantifier “∀” outside of this course or maybe a theorem-proving segment in an Artificial Intelligence course? When does any CS student in college ever check whether a function is “into” or “onto”? Does a current course on networking really involve proofs, or rather packets and protocols and settings? Is this material really foundational for Computer Science, in the sense of all of it being really necessary to be able to do CS? Or is this material just some background theory of the field for which it’s nice that it’s there, but it’s simply not useful for day-to-day actvities — just as, for an analogy, it’s good that the theory of common physics has been worked out (F = ma and all that rot ;-), but we don’t actually use any of that theory when we do real activities such as playing catch or deciding when to apply brakes while driving — not even when teaching people how to drive, by the way.
In considering this question, I started focusing on what material can be covered in this course that could be useful for subsequent college courses. And at first I was disappointed because it seemed to still be a disconnected collection of notation and jargon. But then I realized that that’s exactly what’s useful: notation and jargon! It’s typical for a field to use its own notation and jargon. For theater, consider the adjective “stage left” and the verb “upstage”. For organic chemistry which is a requirement for medicine, I’ve heard that it’s necessary to memorize a bunch of notation and terminology. For Computer Science, consider the following notation and terminology which this introductory course could present: binary, hexadecimal, ASCII/Unicode, bitwise operations, boolean algebra, symbolic logic, set operations, recursive definitions, O(), finite-state machines, regular expressions, and more. Proofs may be considered as claims’ explanations/justifications written in this mathematical language for Computer Science. For example the best way to explain the N*log(N) time complexity of mergesort is to prove it. And is this material foundational in the sense that it’s all necessary for day-to-day practice of Computer Science, i.e. writing computer programs? No! Or is this material all really strongly interconnected? No! But is this material useful like introducing a foreign language to someone, providing them with a variety of words — for “hello”, “please”, “bus”, “water”, “hostel”, “one”, “two”, and so on — so they may be able to understand and use some of the terminology in different situations they may encounter? Yes!! Well, that’s what this course can be about. “Bonjour, étudiants! Bienvenus à ce cours, où vous allez apprendre du langage mathématique pour l’informatique….” (“Hello, students! Welcome to this course, where you’ll learn some mathematical language for Computer Science….”) After this course, say titled “Introduction to Discrete Structures for Computer Science”, a later course can present theory of Computer Science: varieties of automata, equivalence with categories of formal languages, Turing machines, decidability, reducibility, complexity, P vs. NP, etc.
Qu’est-ce-que tu penses de ce sujet? (What do you think about this subject? 
