Skip to content

Discrete math and probability

~12 min

In short

Discrete math is the mathematics of countable things: logic, sets, functions, graphs, induction, and counting. Probability gives you a way to reason about uncertainty and randomness. Both give you tools for proofs about algorithms and for the analysis of programs that use randomness. This page sets out what to learn, in what order, and what to leave for later.

What the subject is about

Discrete math is the language of precise statements. You learn to write a claim with quantifiers ("for every n, there exists m"), to test whether an argument is valid, and to prove it. Sets and relations describe collections and connections. Functions map inputs to outputs. Graphs model networks and dependencies.

Proof by induction is the central technique for this course. You show a base case, then show that if a statement holds for n it holds for n + 1. It is the reason you can trust a recursive function or a loop invariant.

Counting asks how many ways something can happen. Probability asks how likely it is. Together they explain why a hash table has few collisions on average, why a randomised algorithm is fast in expectation, and how to read a claim such as "a test is 99 percent accurate".

What to learn first

  1. Propositions, and, or, not, and truth tables.
  2. Implication and the contrapositive.
  3. Sets: union, intersection, complement, and subsets.
  4. Functions: domain, codomain, one-to-one, onto.
  5. Mathematical induction, with simple sums first.
  6. Relations and their basic properties.
  7. Basic graph terms: vertices, edges, paths, and cycles.
  8. Counting: permutations, combinations, and the pigeonhole principle.
  9. Probability on finite sample spaces, and conditional probability.
  10. Bayes' theorem and expected value.

The Python course's ../../python/02-decisions-and-loops/01-booleans-and-comparisons.md is a practical start on logical operators. Write the truth table for each Python operator and check it in code.

What you can skip at first

  • Abstract algebra, group theory, and topology.
  • Measure-theoretic probability and continuous distributions beyond the basics.
  • Long formal proofs of graph theorems. Read a few and learn the technique.
  • Advanced combinatorics such as generating functions.
  • Statistical software packages. Learn the mathematics first.

How it connects to the other subjects

Induction proves that recursive algorithms and loop invariants are correct. See programming fundamentals for the loops and recursion this proves.

Graph theory underlies many algorithms in data structures and algorithms, and counting gives the bounds used in complexity analysis.

Probability appears in hashing, randomised load balancing in networks, and failure analysis in operating systems. See computer networks and operating systems.

Relational algebra in databases is built from sets and relations. See databases.

Free resources

  • MIT 6.042J, Mathematics for Computer Science (https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/). Lectures and notes from MIT OpenCourseWare built around proofs and discrete structures. It suits a student who wants a complete course with problem sets.
  • Mathematics for Computer Science, Lehman, Leighton, and Meyer (https://courses.csail.mit.edu/6.042/spring18/mcs.pdf). The free course text as a PDF. It suits a student who wants a single reference to read at their own pace.
  • MIT 6.041SC, Probabilistic Systems Analysis and Applied Probability (https://ocw.mit.edu/courses/6-041sc-probabilistic-systems-analysis-and-applied-probability-fall-2013/). An MIT OpenCourseWare course on probability from the basics. It suits anyone who wants probability taught with applications in mind.
  • Khan Academy, Computer Science (https://www.khanacademy.org/computing/computer-science). Short videos and exercises on many basics, including logic and some algorithms. It suits a student who needs a gentle first pass before the MIT material.

Practice

  1. Write a truth table for (p and q) or not r. Check it in Python by looping over all eight combinations of True and False.
  2. Prove by induction that the sum of the first n odd numbers equals n squared. Write the base case and the inductive step separately.
  3. Count the number of different 4-letter passwords using only the letters a to z, with no repeats. Then count the same case allowing repeats, and explain the difference.
  4. A bag has 3 red and 2 blue balls. Two balls are drawn without replacement. Find the probability that both are red, then check your answer with a short simulation.
  5. A disease affects 1 in 1000 people. A test is 99 percent accurate in both directions. Use Bayes' theorem to find the probability that a person with a positive test has the disease, then explain why the answer is small.

Sources

  • MIT OpenCourseWare, 6.042J Mathematics for Computer Science, https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/
  • Lehman, Leighton, and Meyer, Mathematics for Computer Science, PDF, https://courses.csail.mit.edu/6.042/spring18/mcs.pdf
  • MIT OpenCourseWare, 6.041SC Probabilistic Systems Analysis and Applied Probability, https://ocw.mit.edu/courses/6-041sc-probabilistic-systems-analysis-and-applied-probability-fall-2013/
  • Khan Academy, Computer science, https://www.khanacademy.org/computing/computer-science