Anyone who has taught a course in discrete mathematics knows that it can be a problem to motivate students and keep them interested in the material. Almost everyone agrees that the solution is not to use a “lemma-theorem-proof-corollary” approach, but rather to motivate the material, using examples that have direct relevance to computer science. This paper describes a novel way to introduce such examples.
Most instructors of discrete mathematics (including me) present an area of discrete mathematics, investigate some of its properties, and then apply that area to topics in computer science. For example, after we study combinatorics, we show the student how to apply counting arguments in a variety of situations, some of which are closely tied to computer science. The author of this paper advocates a twist on this idea: start with a problem, let the students try to solve the problem until they are stumped, and then introduce and apply the relevant area of discrete mathematics.
The paper is organized by the major topics of discrete mathematics: sets and relations, functions, propositional logic, predicate logic, proof techniques, counting, graphs and trees, and discrete probability.
The author’s school combines discrete mathematics with data structures and analysis of algorithms in a two-semester sequence. At my school, discrete mathematics and data structures are distinct courses, and we often discuss the same topic from two points of view. For example, we may look at graph traversal methods from a data structures point of view and from a discrete mathematics point of view. It would seem that each approach has its advantages and disadvantages.
This paper addresses a problem that many of us face, and it suggests an interesting way to try to solve it.