Red-Green-Code

Deliberate practice techniques for software developers

  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter

What is Discrete Mathematics?

By Duncan Smith Feb 16 0

Discrete math books

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.

Categories: Discrete Math

Prev
Next

Stay in the Know

I'm trying out the latest learning techniques on software development concepts, and writing about what works best. Sound interesting? Subscribe to my free newsletter to keep up to date. Learn More
Unsubscribing is easy, and I'll keep your email address private.

Getting Started

Are you new here? Check out my review posts for a tour of the archives:

  • Lessons from the 2020 LeetCode Monthly Challenges
  • 2019 in Review
  • Competitive Programming Frequently Asked Questions: 2018 In Review
  • What I Learned Working On Time Tortoise in 2017
  • 2016 in Review
  • 2015 in Review
  • 2015 Summer Review

Archives

Recent Posts

  • LeetCode 1288: Remove Covered Intervals January 20, 2021
  • LeetCode 227: Basic Calculator II January 13, 2021
  • A Project for 2021 January 6, 2021
  • Lessons from the 2020 LeetCode Monthly Challenges December 30, 2020
  • Quora: Are Math Courses Useful for Competitive Programming? December 23, 2020
  • Quora: Are Take-Home Assignments a Good Interview Technique? December 17, 2020
  • Quora: Why Don’t Coding Interviews Test Job Skills? December 9, 2020
  • Quora: How Much Time Should it Take to Solve a LeetCode Hard Problem? December 2, 2020
  • Quora: Quantity vs. Quality on LeetCode November 25, 2020
  • Quora: LeetCode Research November 18, 2020
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2021 Duncan Smith