S016 · Discrete Math — Sets, Logic, Combinatorics, Graphs

Module M02: Math Foundations · Session 16 of 130 · Track: Math 🔢

What you'll be able to do after this session

• Explain Discrete Math — Sets, Logic, Combinatorics, Graphs to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S015 — Big-O Notation — Reasoning About Scale

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · What Is Discrete Mathematics? — TrevTutor — a friendly one-shot overview.
• 🎥 Deep dive (30–60 min) · MIT 6.042J — Mathematics for Computer Science, Lecture 1 — the gold-standard course, first lecture.
• 🎥 Hands-on demo (10–20 min) · Combinations and Permutations — Khan Academy — the counting fundamentals in 15 min.
• 📖 Canonical article · MIT 6.042J — Mathematics for Computer Science (OCW) — full textbook + notes, free.
• 📖 Book chapter / tutorial · Discrete Mathematics: An Open Introduction — Oscar Levin — free online textbook; chapters 0-3 cover everything below.
• 📖 Engineering blog · Facebook Engineering — Fighting spam with graphs — graph reasoning in production at billion-node scale.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: The vocabulary of CS.

Discrete math is the math of things you can count on your fingers: whole numbers, yes/no truths, unique objects, connections between them. It's the opposite of continuous math (calculus), which deals with smooth-flowing quantities. Every computer works on discrete things — bits, memory addresses, users, edges in a network — so discrete math is the native language of software.

Four ideas cover 90% of what you need: Sets (collections of unique things and the operations union/intersection/difference), Logic (AND/OR/NOT and how to prove things follow from other things), Combinatorics (counting how many ways things can happen — the math of probability and passwords), and Graphs (dots connected by lines — the math of social networks, routing, dependencies).

The forever-gotcha: most "hard" CS problems become easy once you name them in discrete-math vocabulary. "Find friends of friends" is graph BFS. "How many possible API keys?" is combinatorics. "Are these two queries equivalent?" is logic. Learn the vocabulary and half the intimidation vanishes.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Sets — collections of unique items. Notation and Python equivalents:

Logic — truth tables you must own:

Two laws you'll use forever:

• De Morgan: ¬(p ∧ q) = ¬p ∨ ¬q — negating an AND flips to OR. This is why not (a and b) equals not a or not b.
• Contrapositive: p → q is equivalent to ¬q → ¬p. Used every time you write "if the file didn't exist we wouldn't be here, so the file exists".

Combinatorics — three rules to memorise (n = total, k = chosen):

Graphs — G = (V, E). Vertices (nodes) + edges (connections).

• Degree of a node = how many edges touch it. Node D has degree 3.
• Path = a sequence of edges A→B→D→E.
• Cycle = a path that returns to its start (A→B→D→C→A).
• Directed vs undirected: Twitter follows are directed (→), Facebook friendship is undirected (—).
• DAG (directed acyclic graph) = directed with no cycles. Task dependencies, git commit history, build systems.

Worked example — the pigeonhole principle (a discrete-math classic): if you put n+1 pigeons in n holes, some hole has ≥2 pigeons. Application: in any group of 366 people, at least two share a birthday (365 possible birthdays = holes). This is why hash collisions are inevitable when hash-space < input-space.

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

"""Discrete-math primitives in Python: sets, combinations, and a tiny graph BFS."""
from itertools import combinations, permutations, product
from math import comb, perm, factorial
from collections import deque, defaultdict
 
# ---- 1. SETS: mutual friends between two users ---------------------
alice_friends = {"bob", "carol", "dave", "eve"}
frank_friends = {"carol", "dave", "gina", "hank"}
 
print("union       :", alice_friends | frank_friends)
print("intersection:", alice_friends & frank_friends)
print("only alice  :", alice_friends - frank_friends)
print("jaccard sim :", len(alice_friends & frank_friends) / len(alice_friends | frank_friends))
 
# ---- 2. COMBINATORICS: how many ways to form teams -----------------
n_players = 12
team_size = 5
print(f"\n{n_players} players, teams of {team_size}:")
print(f"  ordered lineups (permutations): {perm(n_players, team_size):,}")
print(f"  unordered teams (combinations): {comb(n_players, team_size):,}")
 
# 8-char password from letters+digits
alphabet = 26 + 10           # a-z + 0-9
print(f"  8-char passwords: {alphabet**8:,}  (~{alphabet**8/1e9:.1f} billion)")
 
# ---- 3. LOGIC via truth table generation ---------------------------
print("\nDe Morgan proof: ¬(p ∧ q) ≡ ¬p ∨ ¬q")
print("  p  q | lhs rhs | equal?")
for p, q in product([False, True], repeat=2):
    lhs = not (p and q)
    rhs = (not p) or (not q)
    print(f"  {p!s:5} {q!s:5} | {lhs!s:5} {rhs!s:5} | {lhs == rhs}")
 
# ---- 4. GRAPH: BFS shortest path in a social network ---------------
edges = [("A","B"), ("A","C"), ("B","D"), ("C","D"), ("D","E"), ("E","F")]
graph: dict[str, list[str]] = defaultdict(list)
for u, v in edges:
    graph[u].append(v); graph[v].append(u)   # undirected
 
def bfs_shortest(start: str, target: str) -> list[str]:
    q = deque([(start, [start])])
    seen = {start}
    while q:
        node, path = q.popleft()
        if node == target:
            return path
        for nbr in graph[node]:
            if nbr not in seen:
                seen.add(nbr); q.append((nbr, path + [nbr]))
    return []
 
print("\nshortest A→F:", bfs_shortest("A", "F"))

Observe when you run:

1. Jaccard similarity ≈ 0.33 — two of six unique names overlap.
2. Permutations of 12-choose-5 is 95 040; combinations is 792 (order matters ↔ 120× fewer when it doesn't). That factor is 5! = 120.
3. 8-char alphanumeric passwords ≈ 2.8 trillion — still crackable on a GPU in hours. That's why we salt+hash.
4. The truth table prints True in every "equal?" row — De Morgan verified.
5. BFS returns ['A','C','D','E','F'] (length 4). Change deque to a stack (list + pop) and you get DFS — same graph, different path, not necessarily shortest.

Try this modification: add a weighted edge (("D", "F", 1) direct) and switch to Dijkstra's algorithm (heapq priority queue). Verify shortest A→F is now [A,C,D,F] length 3.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Discrete math shows up in production more often than any other math. Three examples from top teams:

Facebook's social graph has ~3 billion nodes (people) and ~500 billion edges (friendships / follows). Feed ranking, People You May Know, and spam detection are all graph algorithms — BFS to find friends-of-friends, PageRank-style centrality to spot fake account clusters, community detection to break up echo chambers. Their engineering blog on graph-based spam fighting is a masterclass in applied graph theory.

Google's PageRank, the algorithm that made Google Google, is literally a discrete-math object: the stationary distribution of a random walk on the web graph. Netflix uses graph similarity to recommend movies ("people who watched X also watched Y" = a bipartite graph). Uber uses shortest-path (Dijkstra + A*) to route drivers, computed millions of times per minute.

Combinatorics in security: a UUID v4 has 122 random bits → 2¹²² ≈ 5.3 × 10³⁶ possible values. That's why "will two UUIDs collide?" is effectively "no" — the birthday-paradox threshold sits at ~2⁶¹ generated UUIDs before collision becomes 50/50. Same reasoning for hash outputs (SHA-256: 2¹²⁸ collision resistance) and TLS session keys.

Logic in databases: every SQL WHERE clause is a boolean formula. Query optimisers use De Morgan and distributive laws to rewrite NOT (a AND b) into NOT a OR NOT b because the second form may be able to use indexes. When you see EXPLAIN show a predicate has been "pushed down" — that's discrete-math rewriting in action.

Gotchas:

• Set operations on large data: set(a) & set(b) is O(min(|a|, |b|)) — great. But building the set of a 1B-row column blows up memory. In Spark/SQL use INTERSECT or a hash join instead.
• Off-by-one in combinatorics: combinations(range(n), k) yields C(n,k) items — easy to double-count if you also iterate outer.
• Directed vs undirected confusion: assuming a friendship is symmetric when the data is actually a "follow" relationship (Twitter, TikTok). This bug ships regularly.
• Cycles in a graph you assumed was a DAG kill topological sort. nx.is_directed_acyclic_graph(G) before you topological_sort — always.

(e) Quiz + exercise · 10 min

1. State De Morgan's laws in your own words. Give a code example where each helps you simplify a condition.
2. What's the difference between a permutation and a combination? When would you use each?
3. In a group of n people how large must n be for the probability that two share a birthday to exceed 50%? (Roughly — you don't need the exact formula.)
4. What is a DAG, and give three real-world examples.
5. Explain BFS vs DFS in one sentence each. Which one guarantees shortest path in an unweighted graph, and why?

Stretch (connects to S015 Big-O): what is the time complexity of BFS on a graph with V vertices and E edges? Prove it by counting the work per node. How does that compare to naive_shortest_path that tries every path?

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Discrete Math — Sets, Logic, Combinatorics, Graphs? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S017): Linear Algebra I — Vectors, Dot Product, Geometry
• Previous (S015): Big-O Notation — Reasoning About Scale
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.