In their first 13 or so years of school, students cover a standardized math curriculum. Last week, I covered how Khan Academy approaches that curriculum. Notably absent from that list are many topics in discrete mathematics. But what is discrete mathematics, anyway? I’ll answer that in two ways: with a definition, and with a curriculum.
Discrete Mathematics
Unpacking the term itself, discrete mathematics refers to the mathematical study of discrete (distinct) objects, as opposed to connected ones. For example, integers are discrete objects because there are no integers between the integer $n$ and the next integer, $n+1$. In contrast, given any two real numbers, you can always find another real number between them. So the real numbers form a continuous line, while the integers consist of discrete points.
The textbook I’m using this year, Rosen’s Discrete Mathematics and its Applications, defines discrete mathematics in a “To the Student” section. Rosen writes that discrete mathematics deals with countable sets (which the integers are, but the reals are not). He also points out that computers see data discretely, which makes discrete math especially applicable to computer science.
The lead paragraph of the Wikipedia article on discrete mathematics claims:
[T]here is no exact definition of the term “discrete mathematics.” Indeed, discrete mathematics is described less by what is included than by what is excluded: continuously varying quantities and related notions.
I’ll use the opposite approach and discuss what is included. Specifically, which topics Rosen includes in his introductory textbook.
Discrete Mathematics and its Applications
The latest edition (8th Edition, Copyright 2019) of Rosen has the following thirteen chapters.
Chapter 1: The Foundations: Logic and Proofs
Proofs become more important the farther you go in math. Rosen covers the theory of mathematical proof from the ground up, by describing propositional logic, a system for making and evaluating formal arguments.
Chapter 2: Basic Structures: Sets, Functions, Sequences, Sums, and Matrics
K-12 math classes cover sets, functions, sequences, sums, and matrices in varying levels of detail. So this chapter is mainly a review of previous math courses. But it also formalizes notation that will appear in subsequent chapters, and covers a few advanced topics like the cardinality of infinite sets.
Chapter 3: Algorithms
This is a short chapter that introduces a few of the topics explained in much more depth in an algorithms textbook like CLRS or Sedgewick: the definition of an algorithm, examples of well-known algorithms, and how to evaluate the time and space complexity of algorithms.
Chapter 4: Number Theory and Cryptography
Rosen wrote another textbook called Elementary Number Theory and its Applications. This chapter introduces the key aspects of number theory he covers in that book, and concludes with an introduction to cryptography.
Chapter 5: Induction and Recursion
According to the introduction to this chapter, “Understanding how to read and construct proofs by mathematical induction is a key goal of learning discrete mathematics.” The chapter begins the process of accomplishing that goal, and also demonstrates how to use induction to prove that algorithms correctly solve the problems they are designed to solve.
Chapter 6: Counting
Counting problems are popular as puzzles and interview questions. For example, you can generate anagrams using counting techniques. Fermi problems, which used to be popular in interviews, require a type of counting. This chapter covers the basics of counting and enumeration, permutations and combinations, and binomial coefficients. These topics appear in precalculus and other K-12 classes, so this is another chapter that works as a review and formalization of previous math experience.
Chapter 7: Discrete Probability
Discrete probability concerns phenomena modeled by discrete random variables, those that take one of a countable number of values. For example, you could model dice rolls using discrete probability theory, since each roll of a die produces an integer result (e.g., an integer from 1 to 6). Actual dice have a finite number of faces, but discrete probability can also handle results from countably infinite sets. In contrast, continuous probability theory deals with random variables that can take values in a continuous range (e.g., any real number).
Topics in discrete probability often come up in primary school. This chapter expands on those topics, and includes sections on Bayes’ Theorem and the expected value and variance of a random variable.
Chapter 8: Advanced Counting Techniques
This chapter expands on the counting techniques from Chapter 6. It has several sections dealing with recurrence relations, and also covers generating functions and the inclusion-exclusion principle for counting the number of elements in the union of $n$ sets.
Chapter 9: Relations
A relation is simple to describe. It’s an association between a member of set $A$ and a member of set $B$, or between members of $n$ sets. For the first type, a binary relation, this chapter suggest the example of a person and their phone number. For the second type, a $n$-ary relation, it uses the scenario of airline flights (airline, flight number, origin, destination, departure time, and arrival time).
From this simple starting point, the chapter considers properties and applications of binary and $n$-ary relations; how to represent relations using matrices and digraphs; equivalence relations; and partial orderings.
Chapter 10: Graphs
Programming contests and algorithms classes commonly use graphs. This chapter considers graphs from a mathematical perspective, without getting into implementation details. So although there’s a section on representing graphs using lists or matrices, translating those representations into code is left to the reader. And although the chapter includes famous graph algorithms (like Dijkstra’s and Floyd’s), they appear in pseudocode, not a programming language.
Chapter 11: Trees
Like the previous chapter, this one takes a mathematical approach and includes several pseudocode algorithms. For this chapter, the topic is the special type of graph called a tree, a connected graph with no simple circuits.
Chapter 12: Boolean Algebra
This chapter covers concepts relevant to designing digital circuits.
Chapter 13: Modeling Computation
The book ends with this chapter on grammars, finite-state machines, and Turing machines, basic concepts in theory of computation.
I’m writing about discrete math and competitive programming this year. For an introduction, see A Project for 2019. To read the whole series, see my Discrete Math category page.