4
$\begingroup$

Is there an accepted core set of concepts that is discrete mathematics as it applies to the study of Computer Science? The math department in my school is thinking about creating a course, they asked for our input, and I wasn't sure what to point them to.

$\endgroup$
  • $\begingroup$ See this for english A-level (level-3, below 1st year undergrad) spec. It has some modules that it calls decision maths. This spec has been superseded the new one does not seem to have these modules. $\endgroup$ – ctrl-alt-delor Feb 4 '18 at 9:27
  • $\begingroup$ @ctrl-alt-delor Are you missing a link from this comment? $\endgroup$ – Ben I. Feb 4 '18 at 17:40
  • $\begingroup$ sorry here is the link aqa.org.uk/subjects/mathematics/as-and-a-level/mathematics-6360 (I also not I said English A-level. Which as what I meant the Maths A-level in England. However in England “English A-level” means an A-level in literature and/or language, in the native language of English. $\endgroup$ – ctrl-alt-delor Feb 4 '18 at 21:59
  • $\begingroup$ I self-studied two modules (well, one and a half, because I couldn't find any materials for the other half) of "discrete maths" as part of Further Maths A-level, and some "discrete maths" in the first year of undergraduate CS. They were about completely unrelated topics. Given the ambiguity of the word "school", which of the two courses would be relevant to this question? $\endgroup$ – Peter Taylor Feb 5 '18 at 9:26
  • 1
    $\begingroup$ Let me note here that MathEducators has several questions on discrete mathematics, some of which are relevant here: matheducators.stackexchange.com/questions/tagged/discrete-math. MathEducators in general overlaps with this site on all similar questions. Check it out. $\endgroup$ – Buffy Mar 21 '18 at 16:39
5
$\begingroup$

In the search for a "core set of concepts that is discrete mathematics as it applies to the study of Computer Science," I kept finding nebulous ideas, without concrete parameters. There seems to be a general consensus that there is the need for a firm foundation in discrete mathematics when studying CS. There is also a broad agreement that "graph theory, and other topics" is part of that foundation. Unfortunately the other topics portion of the requirements are seldom well specified, and seemingly never delineated with any specificity.

I recognize that the question is in a high school (USA ages ~ 15-18) context. Be that as it may I've settled on a source from the university context for a solid, definitive, and delineated set of "core discrete mathematics material" to set as a touchstone.

Williams College requires that students who select "Computer Science" as their major demonstrate a proficiency in discrete mathematics. This requirement is usually met with a "C", or better, grade in their MATH 200 course. In Spring 2017, the Computer Science department added an alternate method of satisfying the requirement: A "Discrete Mathematics Proficiency Exam."

Williams is classified as "most selective" by U.S. News & World Report, admitting less than 20% of the applicants each year. As such it is expected that they have set standards, in all areas, rather high. However, I prefer to avoid the dangers alluded to by Michelangelo (disputed): The greatest danger for most of us is not that our aim is too high and we miss it, but that it is too low and we reach it. If I were to choose a target, aiming "high" has the advantage that I might reach the target. If I fail to reach the target, I will know how high I can go. If the aim is low, however, and I reach that target, I still will not know if I could have reached higher. Therefore, using the materials from Williams College as a guide for a high school course seems worthwhile.

All that being said, here is the "short list" of their subject areas, (taken from their Preparing for the exam web page.)

  • Sets, Relations, and Functions
  • Basic Logic
  • Proof Techniques
  • Basics of Counting
  • Discrete Probability
  • Measuring Algorithm Complexity
  • Graphs and Trees

There is, most assuredly, a lot of ground to cover there, and it does not look any "easier" with a full breakdown. The referenced web page (ibid.) lists a breakdown of the topics followed by the learning outcomes. I think the learning outcomes likely to be more significant in answering the OP's instant question, and have reproduced them with their subjects below.


TL;DNR

The seven areas above have following learning outcomes listed in the cited materials:

Sets, Relations, and Functions

Learning Outcomes:

  • Define, as well as explain with examples, the basic terminology of functions, relations, and sets.
    • Perform the operations associated with sets, functions, and relations.
    • Relate practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context.

Basic Logic

Learning Outcomes:

  • Convert logical statements from informal language to propositional (and quantified) logic expressions.
    • Apply formal methods of symbolic propositional logic, such as calculating validity of formulae and computing normal forms.
    • Use the rules of inference to construct proofs in propositional logic.

Proof Techniques

Learning Outcomes:

  • Identify the proof technique used in a given proof.
    • Outline the basic structure of each proof technique described in this unit.
    • Apply each of the proof techniques correctly in the construction of a sound argument.
    • Determine which type of proof is best for a given problem.
    • Explain the parallel between ideas of mathematical induction to recursion and recursively defined sequences.
    • Explain the relationship between weak and strong induction and give examples of the appropriate use of each.
    • State the well-ordering principle and its relationship to mathematical induction.

Basics of Counting

Learning Outcomes:

  • Apply counting arguments, including sum and product rules, inclusion-exclusion principle and arithmetic/geometric progressions.
    • Apply the pigeonhole principle in the context of a formal proof.
    • Compute permutations and combinations of a set, and interpret the meaning in the context of the particular application.
    • Map real-world applications to appropriate counting formalisms, such as determining the number of ways to arrange people around a table, subject to constraints on the seating arrangement, or the number of ways to determine certain hands in cards (e.g., a full house).
    • Solve a variety of basic recurrence relations.
    • Analyze a problem to determine underlying recurrence relations.
    • Perform computations involving modular arithmetic.

Discrete Probability

Learning Outcomes:

  • Calculate probabilities of events for elementary problems such as games of chance.
    • Differentiate between dependent and independent events.
    • Make a probabilistic inference in a real-world problem using Bayes’ theorem to determine the probability of a hypothesis given evidence.

Measuring Algorithm Complexity

Learning Outcomes:

  • Be able to meaningfully compare the asymptotic growths of pairs of functions.

Graphs and Trees

Learning Outcomes:

  • Illustrate by example the basic terminology of graph theory, and some of the properties and special cases of each type of graph/tree.
    • Be able to prove elementary results about graphs and trees, such as:
    • In any graph, the sum of the degrees of the vertices equals twice the number of edges.
    • In any tree, the number of edges is one less than the number of vertices.
    • Model a variety of real-world problems in computer science using appropriate forms of graphs and trees, such as representing a network topology or the organization of a hierarchical file system.

Source: Discrete Mathematics Preparation from Williams College Computer Science Department

$\endgroup$
3
$\begingroup$

I'd say graph theory lies right in the sweet spot of the intersection of Discrete Math and CS - in fact, at my own university, the idea of graphs are introduced in CS courses before it goes into more depth in later math courses (in an intro to combinatorics course). There are some intuitive ways to provide motivation for the topics (e.g. path finding and taxonomy intuitively feel like they should be modeled with graphs and trees respectively), and then there are some problems which at first glance don't feel like they have anything to do with graphs, but one can interpret the problem as a graph - scheduling problems and graph colourings, or a node representing the state of a puzzle/game and edges representing actions being done in this puzzle/game, connecting to the node representing the state after the action is done.

With the puzzles example, for appropriate puzzles, this representation could be used to "brute force" a solution to said puzzle, e.g. a Rubik's cube or sudoku. The "actions" for a Rubik's would be the possible rotations of the cube. The "actions" for a sudoku might be to fill in one of the empty boxes with some number. An important distinction between these two examples is that in a Rubik's cube, we can return to a state we previously had - the graph formed has cycles in it, so we have to take that into account. In the sudoku example, because we ALWAYS fill in a box with a number, the number of empty spaces always decreases by 1 for each "action" (we never erase a number), thus our graph representing the Sudoku puzzle's possible solutions is acyclic. In both, we'd like to stop our actions once the puzzle has been "solved", which we'd have to check for. Also, note that both graphs are directed graphs.

There's a bunch more to be said about applications of graphs... What's important is, as the other answer points out, not just learning about graphs, but actually programming some algorithms with them.

You may also want to cover some basic propositional logic and (finite) set theory. Reasoning about abstract logical statements as well as sets is fundamental to computer science just as it is mathematics. Unfortunately it may feel too abstract for some students... I had to take a CS course in Logic, and for part of this course, we used the proof assistant Coq (https://en.wikipedia.org/wiki/Coq). Unlike writing mathematical proofs by hand, writing in Coq feels more like writing a program (which is because Coq is (in a sense) also a programming language), and this might be a way to cater it to CS students - proving is programming.

Might add more stuff here if I can think of it... Thinking of linear algebra, which some mysteriously classify as discrete math. My high school used to do this, though I'll admit it has a discrete "feeling" to it versus Calculus or Analysis, and it also can be truly discrete with finite fields, or finite modules over a (discrete) ring. Maybe transformation matrixes being used in computer graphics, with 2D and/or 3D focus depending on the class's maturity. Not sure if this is the right fit for what you want though...

$\endgroup$
3
$\begingroup$

This question is hard to answer and especially hard to provide a complete answer. There are a lot of things that are good to know if you work with computers, though not everyone will use everything on anyone's list of favorites.

However, some sorts of discrete/finite math are especially useful as they are useful for building models, independent of computers. The models can be programmed to solve useful problems in the world. I'll mention a few here.

The basic idea here is that the more ways you have to approach a problem, the more likely it is that you can provide a solution. Even an approximate solution is often enough, especially in situations of uncertainty or when there are many variables and many constraints.

Markov Chains and Markov Processing. These describe dynamic systems in which changes depend on only the current state and not a history.

Linear Programing, and especially Integral Linear Programming where solutions must be integers. These are used for all sorts of optimization problems where constraints must be observed.

Discrete Probability and Combinatorics which has entries to many related fields (Graph Theory, Coding Theory, ...)

Decision Theory and Decision Trees, often used in algorithm design. Modeling under uncertainty.

Set Theory and, more generally, Mathematical Logic, used ubiquitously in programming and in Theoretical CS.

Vectors and Matrices (not strictly discrete, of course) but often used in proofs and models, especially models of physical systems.

Game Theory, again used in modeling and in predicting outcomes in complex situations.

Number Theory used in many things, especially cryptology.


Often such courses are, indeed, best taught by mathematicians. But it is also possible for a CS department to negotiate with the Math department on content. Even more radical, is a collaborative course, taught jointly by a mathematician and a computer scientist in which programming is used to enhance the material and make it more concrete. It is also possible for it to be team-project course in which different teams work on different problems, each emphasizing some different sort of mathematical modeling. A joint wrap up (science fair) can be very valuable.

Also note that any of these topics could be a full course (or more). Some small subset of topics from several of these areas is enough to make up a course.

$\endgroup$
1
$\begingroup$

The one thing I would not do is create a separate Math course oriented towards computer programming. A purely-math course with no programming is probably the best way to kill interest in one or the other.

Introduce the math where it naturally fits in as you teach algorithmic concepts for real situations -- actual projects in your courses. Most programmers think no more about 'math' as a subject than Chefs think about Thermodynamics: they don't have to!

$\endgroup$
  • $\begingroup$ I think your answer has validity, but I also note that most university curricula do, actually, have a discrete math course that is required of CS majors. It may be taught either by mathematicians (less programming) or by computer scientists (hopefully, more). In a similar vein, some university programs require at least some Calculus, usually from the math department. There are tradeoffs, of course. At a minimum, courses from the math department may give an alternate way of looking at problems - a good thing. $\endgroup$ – Buffy Feb 7 '18 at 15:17
  • $\begingroup$ Welcome to Computer Science Educators! Your answer is quite interesting; If you could expand just a bit more upon your answer, it would surely be of higher quality. $\endgroup$ – ItamarG3 Feb 7 '18 at 16:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.