Why Math ?

Why Math?∗
Kim B. Bruce† Williams College Robert L. Scot Drysdale Dartmouth College Allen Tucker Bowdoin College April 29, 2002
Math requirements! Those words are enough to send chills down the spines of a good share of new Computer Science majors every year. Bring the same topic up with practitioners and a good share will rant about how much time and effort they wasted on college mathematicsthat they have never used. Why is it that we force this material on unwilling students, especially when so many practitioners claim it is unnecessary? Some might claim that mathematics is simply used as a filter – to weed out those too weak to survive – or even just to cut down the hordes of students to a more manageable size. Others might argue that it is just another sign that faculty in theirivory towers have no clue what practitioners really do or what they need. While surely there are subscribers to each of these views, we argue here that the right kind of mathematics is essential to the understanding and practice of computer science. What is the right kind of mathematics? For computer science qua computer science, the core need is discrete mathematics. For applications of computerscience, the appropriate mathematics is whatever is needed to model the application discipline. Software solutions to most problems (e.g. banking, on-line commerce, airline reservations, etc.) consist of constructing a (mathematical) model of the real (physical) domain and implementing it in software. Mathematics can be helpful in all stages of software development: design, specification, coding,verifying security and correctness of the final implementation. In many cases, particular topics in mathematics are not as important as a high level of mathematical sophistication. Just as athletes cross-train by running and lifting weights, exposure to challenging mathematics courses can help computer science students in their ability to abstract away from details and be more creative in theirapproaches to problems. What is discrete mathematics? Here is the list of topics in discrete mathematics considered core in Curriculum 2001 [oCC02]: DS1. Functions, relations, and sets. DS2. Basic logic. DS3. Proof techniques (including mathematical induction and proof by contradiction).
Bruce’s research was partially supported by NSF grant CCR-9988210. Corresponding author: Kim B. Bruce, Department ofComputer Science, Williams College, Williamstown, MA 01267. kim@cs.williams.edu,(413) 597-2273, FAX: (413) 597-4250.
† ∗

Charles Kelemen Swarthmore College

1

DS4. Basics of counting. DS5. Graphs and trees. DS6. Discrete probability. As a warm up for our presentation of the use of discrete mathematics, let’s start with a very simple problem. Vectors are supported in standard libraries ofC++ and Java. From the outside a vector looks very much like an extendable array. That is, while a vector is created with a given initial size, if something is added at an index beyond its extent, the vector automatically grows to be large enough to hold a value at that index. A vector may be implemented in many ways, for example as a linked list, but the most common implementation uses an arrayto hold the values. With this implementation, if an element is inserted beyond its extent, the data structure creates a new array that is large enough to include that index, copies the elements from the old array to the new array, and then adds the new element at the proper index. That’s pretty straightforward, but how much should the array be extended each time it runs out of space? Forsimplicity, let’s suppose that the array is being filled in increasing order, so each time it runs out of space, it only actually needs to be extended by one cell. There are two strategies for increasing the size of the array. One is always to increase it in size by the same fixed amount, F . The other is to always increase it in size by a fixed percentage, P %. A simple analysis using discrete mathematics...