Discrete Math — Sets, Logic, Combinatorics, Graphs

Review boundary and corrected contracts

Pigeonhole guarantees some collisions, not infinitely many preimages in every bucket. SQL uses bag semantics and three-valued NULL logic; ordinary set/two-valued identities need that boundary. The demo stores consumer → prerequisite edges, so it reverses the topological order for execution; the output below now matches that code.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Fluently translate ‘programmer English’ into set / logic / graph notation, and back — enough to read a paper, a formal spec, or a database query plan without stalling.

Why this session exists

The interesting part of computer science lives in the discrete world: whole numbers, yes/no answers, choices, graphs, states. When you write WHERE a AND (b OR NOT c) you're doing propositional logic. When you index a dict you're using a partial function on a set. When you write a permission system you're doing set algebra. When you route packets you're walking a graph. Discrete math is the notation professionals use to think precisely about these things — and to write down algorithms in a way that other people (and mypy, and formal-verification tools) can actually verify.

You will be able to

• Read and write set-builder notation ({x ∈ S | P(x)}), and translate to Python comprehensions and SQL.

• Read a propositional-logic expression (¬, ∧, ∨, →, ⇔) fluently and simplify with De Morgan's laws.

• Count arrangements with permutation and combination formulas (nPr, nCr) — and know which one to use.

• Distinguish directed vs undirected, weighted vs unweighted graphs and pick the right representation.

• Recognise which of BFS, DFS, or topological sort applies to a given real-world problem.

Prerequisites

• S015 · Big-O — you'll count operations on sets and graphs.
• High-school algebra. That's it — no calculus.

Optional archived videos

These original learning links are retained as optional resources. Video identity, availability and duration were not reverified; the lesson and governing sources below stand independently of them.

• Discrete Math — Full Course
• Lec 1 | MIT 6.042J Mathematics for Computer Science, Fall 2010
• Graph Theory — In 100 Seconds

Pre-read · skim before the session (30 min total)

Further reading: Discrete Structures for Computer Science

Further reading: De Morgan's laws

Further reading: Introduction to A* pathfinding

(a) Intuition · 5 min

Four vocabularies for four kinds of question

Real: A city planner asks four completely different questions in a single meeting: "Which neighbourhoods have both schools and hospitals?" (sets) · "If we build a bridge, will the traffic-light logic still work?" (logic) · "How many bus routes are possible between five hubs?" (combinatorics) · "What's the shortest route from A to B?" (graphs). Same city, four vocabularies. You'll do the same in code. A search filter is a set. An access-control rule is logic. A pagination-key generator is combinatorics. A dependency resolver is a graph. Different problems, one language once you learn each dialect.

 
    The four sub-fields aren't optional — they're the alphabet of everything downstream. Relational algebra uses sets; SQL usually uses bags and NULL-aware logic. Logic also informs type systems, though a type checker is not a general proof checker. Machine-learning cost of a feature explosion is combinatorics. Every dependency graph, permission graph, social graph, model graph is graph theory.
    You don't need to become a mathematician. You need to be fluent enough to read when someone writes it down.
  

The four sub-fields, in one line each

Discrete math for programmers · the four dialects

• Sets — collections without order or duplicates. Union ∪, intersection ∩, difference ∖, subset ⊆.

• Logic — propositions and connectives. ¬ (not), ∧ (and), ∨ (or), → (implies), ⇔ (iff).

• Combinatorics — counting arrangements. Permutations P(n,r) = n!/(n-r)!, combinations C(n,r) = n!/(r!(n-r)!).

• Graphs — vertices connected by edges. Directed vs undirected, weighted vs unweighted, cyclic vs DAG.

The single most-forgotten fact in undergrad discrete math

Order matters in a permutation; order does not matter in a combination. "How many ways can 3 people finish a race?" is a permutation (gold ≠ silver ≠ bronze). "How many ways can I pick 3 people for a team?" is a combination (the team is a set, not a podium). Get this wrong once and you'll overcount by r!.

A quick history

Set theory (Cantor), algebraic logic (Boole), graph problems (Euler), computability (Turing), shortest-path algorithms (Dijkstra), and relational data (Codd) are different historical strands—not one invention. Their useful inheritance here is the distinction between membership, truth, reachability and computable procedures. The St Andrews set-theory history discusses the development of sets and infinity. The former timeline’s café anecdote, sole-inventor claims and claim that every routing system descends from one algorithm are not established by this lesson. Relational algebra is not identical to SQL: duplicate rows and NULL require explicit semantics.

(b) Membership, conditions, choices, and connections · 15 min

The four dialects become easier to separate when you ask what each one keeps track of. Start with membership in two sets, express that membership as a condition, count possible selections, then add relationships between the selected objects.

Sets: three operations, three Venn diagrams

Each panel names a different operation on the same two sets. Treat these as labels for the membership rules, not shaded Venn regions: the concrete elements below show exactly what each operation keeps.

Concrete: if A = {1,2,3} and B = {3,4,5} then A ∪ B = {1,2,3,4,5}, A ∩ B = {3}, A ∖ B = {1,2}.

Python translation:

For a finite universe S, set-builder notation selects exactly the elements satisfying a predicate. For example, S = {1, 2, 3, 4, 5} and P(x) = “x is even” give {2, 4}.

A, B = {1,2,3}, {3,4,5}
A | B      # union
A & B      # intersection
A - B      # difference
A ^ B      # symmetric difference  {1,2,4,5}
A <= B     # subset check

Logic: connectives and De Morgan's laws

For the same selection, Python is {x for x in S if x % 2 == 0} and SQL is SELECT DISTINCT x FROM numbers WHERE x % 2 = 0. DISTINCT removes duplicate rows; NULL comparisons yield UNKNOWN and WHERE keeps only TRUE. A SQL table is not automatically a mathematical set.

Quantifiers state the domain: “for every x in S, P(x)” is universal; “there exists x in S with P(x)” is existential. Their negations switch the quantifier and negate P. On an empty domain the universal is true and the existential false. For S = {1,2,3}, “every x is even” is false, witnessed by 1; “some x is even” is true, witnessed by 2.

Membership is itself a true-or-false statement. An intersection asks whether an element belongs to both sets; a union asks whether it belongs to at least one. Boolean connectives let you write those tests explicitly and combine them into larger filters.

Boolean connectives and their code equivalents

Name: ¬p — not p

Desc: Python: not p. SQL: NOT p. Circuit: NOT gate.

Name: p ∧ q — p and q

Desc: Both true. Python: p and q. SQL: p AND q. Python short-circuits left-to-right; SQL planners need not preserve evaluation order.

Name: p ∨ q — p or q

Desc: At least one true. Python: p or q. SQL: p OR q. Python short-circuits; do not rely on SQL short-circuiting to prevent an error.

Name: p → q — p implies q

Desc: Equivalent to ¬p ∨ q. False only when p is true and q is false. not p or q.

Name: p ⇔ q — p iff q

Desc: Same truth value. Python: p == q for booleans. Aliases: p ≡ q.

De Morgan's laws — two useful identities for Boolean predicates:

¬(p ∧ q)  ≡  ¬p ∨ ¬q      (NOT of AND = OR of NOTs)
¬(p ∨ q)  ≡  ¬p ∧ ¬q      (NOT of OR  = AND of NOTs)

How to simplify a nasty boolean condition

When you write if not (a and (b or not c)): and can't tell what you meant, apply De Morgan: if not a or not (b or not c): → if not a or (not b and c):. Read that last one aloud. Suddenly readable, provably equivalent.

Combinatorics decision tree

A filter decides which choices are allowed; combinatorics asks how many outcomes those choices can produce. Before reaching for a factorial, decide whether changing the order would create a genuinely different outcome.

Are you picking (choosing a subset) or arranging (choosing an order)?

Desc: Picking → combination. Arranging → permutation.

With or without replacement?

Desc: Without = each item used at most once (the usual case). With = same item can appear multiple times.

Does the whole population have to be used?

Desc: ‘Arrange all n people in a line’ is n!. ‘Arrange r of n people’ is P(n,r) = n!/(n-r)!.

Are items distinguishable?

Desc: If two items are identical, divide out the ways they could be permuted (multinomial coefficient).

Formulas cheat sheet:

Here n and r are integers. Without replacement assume 0 ≤ r ≤ n; for ordered replacement use n ≥ 0 and r ≥ 0, counting the empty sequence once. Unordered replacement uses n ≥ 1 and r ≥ 0. The multinomial formula assumes nonnegative multiplicities summing to n. To derive C(n,r), start with n·(n−1)···(n−r+1) ordered selections and divide by r!, the orders of each chosen subset. For stars-and-bars, arrange r identical marks and n−1 separators: choosing the r mark positions among n+r−1 positions gives C(n+r−1,r).

Name: Permutation P(n,r)

Tagline: Order matters

• Number of ways to arrange r of n distinct items

• P(n,r) = n! / (n-r)!

• P(5,3) = 60 — sprint-podium finishes for 5 runners

• Python: math.perm(5, 3)

Name: Combination C(n,r)

Tagline: Order doesn't matter

• Number of ways to CHOOSE r of n distinct items

• C(n,r) = n! / (r! (n-r)!) — the ‘binomial coefficient’

• C(52,5) = 2 598 960 — five-card poker hands

• Python: math.comb(52, 5)

Name: With replacement

Tagline: Same item reusable

• Ordered w/ repl: n^r — 10⁴ = 10 000 four-digit PINs

• Unordered w/ repl: C(n+r-1, r) — stars-and-bars

• Passwords, hash outputs, IP subnets

Name: Multiset perms

Tagline: Some items identical

• n! / (n₁! · n₂! · … · nk!)

• ‘MISSISSIPPI’ = 11! / (4!·4!·2!·1!) = 34 650 anagrams

• Rare in day-to-day code; useful in probability

Graph representations

An undirected edge joins two endpoints symmetrically; store each neighbour in both lists. A directed edge has an orientation. Unweighted edges count one hop each; weighted edges store a cost such as travel time. BFS minimizes hops, not arbitrary total cost. Dijkstra applies to nonnegative edge weights; negative weights need a different contract. The matrix below is a 0/1 directed adjacency matrix, not a weighted distance matrix.

Counting the objects is not enough when their connections determine what you can do. In this directed graph, follow the outgoing arrows from C: they reach D and E. Those same neighbours must appear in either storage representation below.

Two ways to store the same graph: C's adjacency-list entry names D and E directly; C's matrix row marks their columns with ones. The arrows stay the same—the representation changes which questions are cheap to answer.

# Adjacency list — O(V + E) space, best for sparse graphs
graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D", "E"],
    "D": ["E"],
    "E": [],
}
 
# Adjacency matrix — O(V^2) space, best for dense graphs / fast edge lookup
V = ["A", "B", "C", "D", "E"]
M = [[0,1,1,0,0],
     [0,0,0,1,0],
     [0,0,0,1,1],
     [0,0,0,0,1],
     [0,0,0,0,0]]

Choose the representation:

Name: Adjacency list

Tagline: Sparse graphs, most real graphs

• O(V+E) memory

• O(degree) to enumerate neighbours

• O(V+E) full traversal

• Web graph, social graph, roads

Name: Adjacency matrix

Tagline: Dense graphs, edge-lookup-heavy

• O(V²) memory

• O(1) ‘is A→B an edge?’

• O(V²) full traversal

• Small dense graphs, ML on graphs, image grids

These representations connect the notation to implementation, but they also expose assumptions: which values count as members, which truth values a filter admits, and how many distinct keys a finite hash can distinguish. The following cases show where those assumptions become operational problems.

Myth: "Discrete math is academic. Sets, logic, combinatorics, graphs — I use SQL and Python every day and never need any of it."

Truth: You use it constantly, unnamed. An inner join is a filtered Cartesian product with bag multiplicities, DISTINCT removes duplicate rows, GROUP BY partitions by grouping keys, a DAG scheduler is graph theory, and a SQL WHERE clause uses three-valued logic. Outer joins also add unmatched rows. Not knowing the names is what makes the failures look mysterious.

Why: Because the abstractions are genuinely good — they let you be productive without the theory, so the theory looks optional. It stops being optional at precisely the moments that cost the most. A NOT IN subquery that silently returns zero rows when the subquery contains one NULL is three-valued logic, and it is completely inexplicable under two-valued reasoning. A left join that produced more rows than the left table is a non-unique key breaking the function property you assumed. A pipeline that deadlocks is a cycle in a graph you believed was acyclic. Each of these looks like a database quirk and is in fact a theorem you didn't know you were relying on.

Test: Three-valued logic, in the wild. For ordinary SQL scalar equality, this WHERE predicate is never TRUE:

SELECT * FROM t WHERE t.id NOT IN (1, 2, NULL);
-- id <> 1 AND id <> 2 AND id <> NULL
-- A match makes it FALSE; otherwise the NULL term leaves UNKNOWN.

A correlated NOT EXISTS is not a magical identical replacement: decide what an outer NULL means. A non-NULL key policy is taught in the production example below. De Morgan's laws still hold for SQL's three truth values, but excluded middle (p OR NOT p) is UNKNOWN when p is UNKNOWN. Question: When does pigeonhole force a hash collision, and what must a general-purpose hash table do about it?

Premise: A hash function maps an input domain (all possible keys) to a finite codomain (buckets, or fixed-width hash values).

Because: the output must fit in a fixed number of bits to be usable as an index or a stored digest

Premise: The domain of possible keys is vastly larger than the codomain — unbounded, for strings — while the codomain has at most 2^k elements.

Because: keys are arbitrary-length data; hashes are fixed-length by construction

Premise: By pigeonhole, mapping more items than containers forces at least two items into some container. With an infinite domain and a finite codomain, at least one bucket has infinitely many preimages; not every bucket must.

Because: you cannot injectively map a larger set into a smaller one — this is arithmetic, not a property of the function

Premise: For a total function from a domain larger than its finite codomain, collisions are unavoidable. An injective/perfect hash can exist on a restricted domain no larger than the output space. A suitable randomized hashing scheme can control collision probabilities; it cannot abolish collisions on an oversized domain.

Because: the counting argument is independent of how the function computes its output

Premise: A general-purpose table accepting unrestricted keys needs collision resolution, such as chaining or open addressing. Expected O(1) elementary lookup work depends on the hashing model and load factor; it is not a worst-case guarantee or a claim that hashing an arbitrarily long key is constant-time.

Because: for a simple chained table with n colliding keys, a lookup can require a linear scan; other collision representations have different worst cases

Conclusion: Therefore "O(1) average" for hash tables carries a hidden assumption about key distribution, and that assumption is attackable. This is exactly the basis of hash-flooding denial-of-service attacks, and why Python randomises string hashing per process by default (PYTHONHASHSEED). And note what this predicts in data engineering: hash-partitioning a dataset on a skewed key cannot distribute it evenly, no matter how good the hash — if 40% of rows share one customer id, they share one hash and therefore one partition. Equal keys hash equally; this is a function property, not pigeonhole. Salting can spread a heavy key only if downstream work correctly recombines its partial results. For q independent uniform samples from m outputs, collision probability is 1 − ∏(1 − i/m), for i from 0 to q−1 (q ≤ m). For q much smaller than √m it is approximately q(q−1)/(2m); a constant-order collision probability appears when q is of order √m. Probability itself does not grow “with the square root of the space.”

Name: Sets, relations, graphs — the three shapes of data

Picture: Almost every data structure and query is one of three things. A set: unordered, no duplicates, membership is the only question. A mathematical relation is a set of tuples; a SQL table may contain duplicates and NULLs. Inner joins, filters and projections connect to relational operations but retain SQL-specific semantics. A graph: nodes and edges, which is what you have whenever things reference other things — dependencies, lineage, foreign keys, retries. Naming which one you are holding tells you immediately which properties you get for free and which you must prove. Sets give you dedup and commutative union. Relational algebra gives a useful model, not all of SQL’s bag, NULL and outer-join semantics. Graphs give you reachability and cycles — and the question "is this acyclic?" that scheduling depends on.

• An inner join is a Cartesian product with a filter (and SQL bag multiplicities). Row explosion is not a bug; it is the product doing exactly what it does when the join key isn't unique on the side you assumed.

• NULL is a marker for missing/unknown data. Ordinary NULL = NULL is UNKNOWN; a NULL in a NOT IN list prevents unmatched values from passing WHERE. GROUP BY and duplicate elimination use their own not-distinct grouping semantics, which group NULLs together.

• De Morgan's laws are how you rewrite a filter you can't reason about: NOT (A AND B) ≡ (NOT A) OR (NOT B). Query planners do this constantly, and so should you when a predicate stops making sense.

• Strict “must finish before” dependencies need a DAG for a one-pass schedule. A topological order may not be unique. Cyclic iterative computations can execute under a different convergence/iteration protocol; they are not one-pass prerequisite schedules.

Trigger: Fire this model the moment you see: a join that multiplied your row count · NOT IN returning nothing · a COUNT(*) and COUNT(col) disagreeing · a scheduler reporting a circular dependency · one partition taking 10× longer than the rest · a dedup that didn't dedup because the key had NULLs.

Decision: You need to test membership of billions of keys — "have I seen this id before?" Exact set, sorted structure, or a probabilistic filter?

Name: Exact hash set

Gain: zero error, O(1) average lookup, and trivially correct — no threshold to tune and no false-positive handling downstream

Cost: memory proportional to the number of and size of keys; at billions of keys this exceeds a single machine, forcing distribution and its coordination cost

Pick: the key set fits in memory with headroom, or a wrong answer is unacceptable — deduplicating financial transactions, enforcing uniqueness constraints

Name: Sorted structure / index

Gain: O(log n) comparisons in a balanced tree or sorted-array binary search; supports range queries. Disk indexes use pages, but an exact structure still stores O(n) keys, not constant total memory

Cost: slower per lookup than hashing, and you pay the sort or index-build up front; insertions are more expensive than into a hash table

Pick: the data exceeds memory, or you need ordering and range predicates too — which is why databases build B-trees rather than hash indexes by default

Name: Bloom filter

Gain: memory per key measured in a handful of bits rather than the key's own size, so billions of keys fit in a manageable footprint; no false negatives for inserted keys when the filter is correctly built, unchanged and queried with the same hashes — a negative result can skip the exact lookup

Cost: false positives at a rate you trade against space; no deletion in the basic form; and you cannot enumerate or retrieve what's in it, only query it

Pick: a false positive is merely expensive rather than wrong — the canonical use being a pre-filter that avoids a disk or network lookup, where a false positive costs one wasted read; if positives are used to drop records without exact verification, the result is incorrect

Verdict: The question that decides it is not "how much memory do I have" but "what does a wrong answer cost?" If a false positive triggers a cheap verification step, the probabilistic structure wins massively on memory. If a false positive silently drops a record, no space saving justifies it. The layered answer is the one production systems actually use: a Bloom filter in front of an exact store, so the filter can absorb most negative lookups at a suitably low false-positive rate for a few bits per key, and the exact structure resolves the small fraction that pass. Storage engines are built this way for precisely this reason.

(c) Hands-on · 25 min

You'll compute a small dependency graph, run BFS + DFS + topological sort on it, and turn boolean-condition simplification into a testable function. Save as discrete_demo.py.

Contract: finite adjacency lists; BFS/DFS require start and every reached vertex to be dictionary keys, including sinks. They return traversal order, not a shortest-path witness or cycle certificate. Kahn’s function also admits neighbours absent as keys as implicit sinks. Each edge u → v orders u before v; reversing this order is necessary only because this demo’s edges mean consumer → prerequisite. Traversals use O(V+E) elementary work; this DFS may hold duplicate pending stack entries, so auxiliary storage can reach O(V+E).

"""discrete_demo.py — sets, logic, combinatorics, graphs in one file."""
from __future__ import annotations
from collections import defaultdict, deque
from itertools import combinations, permutations
from math import comb, perm
 
# ── 1. Sets ─────────────────────────────────────────────────────────────
def demo_sets() -> None:
    students = {"Alice", "Bob", "Carol", "Dave"}
    passed_math = {"Alice", "Bob", "Dave"}
    passed_cs = {"Alice", "Carol", "Dave"}
 
    both = passed_math & passed_cs                      # intersection
    either = passed_math | passed_cs                    # union
    only_math = passed_math - passed_cs                 # difference
    one_only = passed_math ^ passed_cs                  # symmetric diff
    failed = students - either                          # complement
 
    print("both:", both, "| either:", either)
    print("only math:", only_math, "| exactly one:", one_only)
    print("failed both:", failed)
 
# ── 2. Logic + De Morgan's laws (testable) ─────────────────────────────
def implies(p: bool, q: bool) -> bool:
    """p → q is equivalent to ¬p ∨ q."""
    return (not p) or q
 
def prove_de_morgan() -> None:
    """Truth-table check that ¬(p ∧ q) ≡ ¬p ∨ ¬q for all inputs."""
    for p in (False, True):
        for q in (False, True):
            lhs = not (p and q)
            rhs = (not p) or (not q)
            assert lhs == rhs, (p, q)
    print("De Morgan #1 verified for all 4 inputs")
 
# ── 3. Combinatorics ───────────────────────────────────────────────────
def demo_counting() -> None:
    # Poker hands: choose 5 of 52 cards
    print("5-card poker hands:", comb(52, 5))
    # Race podium: order matters, pick 3 of 8 runners
    print("podium arrangements:", perm(8, 3))
    # Enumerate them for small n
    people = ["A", "B", "C", "D"]
    print("teams of 2:", list(combinations(people, 2)))
    print("2-arrangements:", list(permutations(people, 2)))
 
# ── 4. Graphs: BFS, DFS, topological sort ──────────────────────────────
def bfs(g: dict[str, list[str]], start: str) -> list[str]:
    """Breadth-first — shortest-hop order."""
    seen: set[str] = {start}
    q = deque([start])
    order: list[str] = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in g[node]:
            if nxt not in seen:
                seen.add(nxt)
                q.append(nxt)
    return order
 
def dfs(g: dict[str, list[str]], start: str) -> list[str]:
    """Depth-first, iterative."""
    seen: set[str] = set()
    stack = [start]
    order: list[str] = []
    while stack:
        node = stack.pop()
        if node in seen:
            continue
        seen.add(node)
        order.append(node)
        for nxt in reversed(g[node]):    # reverse for left-to-right output
            if nxt not in seen:
                stack.append(nxt)
    return order
 
def topological_sort(g: dict[str, list[str]]) -> list[str]:
    """Kahn's algorithm — O(V+E). Raises if the graph has a cycle."""
    indeg: dict[str, int] = defaultdict(int)
    for u in g:
        indeg.setdefault(u, 0)
        for v in g[u]:
            indeg[v] += 1
            indeg.setdefault(u, indeg[u])
    q = deque([u for u, d in indeg.items() if d == 0])
    order: list[str] = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g.get(u, []):
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    if len(order) != len(indeg):
        raise ValueError("cycle detected — no topological order exists")
    return order
 
def demo_graphs() -> None:
    # A tiny build-dependency graph: what must be built before what?
    deps = {
        "app":       ["auth", "ui", "db"],
        "auth":      ["crypto"],
        "ui":        ["design-system"],
        "db":        [],
        "crypto":    [],
        "design-system": [],
    }
    print("BFS from app:", bfs(deps, "app"))
    print("DFS from app:", dfs(deps, "app"))
    print("build order:", list(reversed(topological_sort(deps))))  # deps points consumer -> prerequisite
 
if __name__ == "__main__":
    print("── SETS ────────────────────"); demo_sets()
    print("\n── LOGIC ───────────────────"); prove_de_morgan()
    print("\n── COUNTING ────────────────"); demo_counting()
    print("\n── GRAPHS ──────────────────"); demo_graphs()

Run it:

python discrete_demo.py

Expected values (set display order and tuple spacing may vary; traversal order below follows the given dictionary and neighbour-list order):

── SETS ────────────────────
both: {'Dave', 'Alice'} | either: {'Alice', 'Bob', 'Carol', 'Dave'}
only math: {'Bob'} | exactly one: {'Bob', 'Carol'}
failed both: set()

── LOGIC ───────────────────
De Morgan #1 verified for all 4 inputs

── COUNTING ────────────────
5-card poker hands: 2598960
podium arrangements: 336
teams of 2: [('A','B'), ('A','C'), ('A','D'), ('B','C'), ('B','D'), ('C','D')]
2-arrangements: [('A','B'),('A','C'),('A','D'),('B','A'),('B','C'),('B','D'),('C','A'),('C','B'),('C','D'),('D','A'),('D','B'),('D','C')]

── GRAPHS ──────────────────
BFS from app: ['app', 'auth', 'ui', 'db', 'crypto', 'design-system']
DFS from app: ['app', 'auth', 'crypto', 'ui', 'design-system', 'db']
build order: ['design-system', 'crypto', 'db', 'ui', 'auth', 'app']

What each block does

Anatomy of the demo

Name: Set operators on Python sets

Desc: &, |, -, ^ are built-in. This IS applied discrete math — SQL joins, permission checks, feature-flag audiences.

Name: prove_de_morgan

Desc: A ‘truth-table proof’ — enumerate all 4 input combinations and assert both sides agree. This is how test-driven development meets formal logic.

Name: math.comb / math.perm

Desc: Since Python 3.8, exact integer formulas. Use these instead of hand-computing factorials (which overflow floats and hide bugs).

Name: BFS with a deque

Desc: collections.deque gives O(1) popleft — a plain list would be O(n). Repeated front removal from a list shifts elements and can make a traversal quadratic; no universal timing factor is implied.

Name: DFS with an explicit stack

Desc: Iterative form avoids Python's recursion limit (1000 by default). For deep dependency graphs this matters.

Name: Kahn's topological sort

Desc: The invariant is that indeg[v] counts edges into v from not-yet-emitted nodes. Removing u decrements exactly its outgoing edges; a zero-indegree node has no remaining predecessor and can be emitted safely. If every remaining vertex has a predecessor, following predecessors in a finite graph repeats a vertex, proving a cycle. Each vertex and edge is processed O(1) times, giving O(V+E) elementary work. BFS’s FIFO queue similarly preserves nondecreasing discovered hop distance; the first discovery cannot be improved by a later layer.

What to observe

BFS visits everything at distance 1 before distance 2 — suitable for minimum hop-count exploration. DFS explores deeply then backtracks. This visited-set implementation alone does not detect directed cycles; a cycle detector needs an active-path colour/state or Kahn’s indegree test. The build order is a valid dependency order: crypto appears before auth, db before app. Add a cycle (deps["crypto"] = ["auth"]) and watch topological_sort raise. That's your CI catching a circular import.

Goal: Recognise ‘which discrete-math tool for which problem’

Hint: For each of the six tasks below, name the right tool (set / logic / combinatorics / graph) BEFORE looking at the answer key below the code.

Match each real-world task to a discrete-math tool:

# 1. Users allowed if they're in group A OR group B, but NOT banned.
# 2. Total number of possible 8-character passwords using a-z A-Z 0-9.
# 3. Given a set of pages a user visited, find pages visited by both users A and B.
# 4. Order in which npm should install packages so no dep is installed after its dependent.
# 5. Find shortest path from London to Berlin on a road network.
# 6. Simplify: NOT (isAdmin AND (isBanned OR NOT hasPaid)).

Answer key

1. Set + Logic (set membership + boolean combo)
2. Combinatorics (ordered with replacement: 62⁸ ≈ 218 trillion)
3. Sets (intersection)
4. Graph (topological sort on a DAG)
5. Graph (BFS for hop count; Dijkstra for nonnegative travel costs, not arbitrary negative weights)
6. Logic (De Morgan: NOT isAdmin OR (NOT isBanned AND hasPaid))

(d) Production reality · 15 min

Two-hop recommendations without an invented benchmark

For a sparse social graph, candidates for user u are the union of neighbours of each neighbour, minus u and existing neighbours. Set deduplication removes candidates reached through several friends. The work is proportional to the sum of those friends’ degrees, not just the number of returned candidates. A high-degree hub can dominate latency. Batching adjacency reads or precomputing candidates trades freshness and storage for fewer remote reads; permission/deletion filtering still belongs on the serving path. The archived LinkedIn dates, system lineage and 1000× claim were not supported and are not reproduced here.

def two_hop_candidates(g, user):
    friends = set(g[user])
    candidates = {v for friend in friends for v in g[friend]}
    return candidates - friends - {user}
 
social = {"A": ["B", "C"], "B": ["A", "D"],
          "C": ["A", "D", "E"], "D": ["B", "C"], "E": ["C"]}
assert two_hop_candidates(social, "A") == {"D", "E"}

SQL exclusion with an explicit NULL policy

Choose “return distinct, non-NULL active IDs having no matching non-NULL banned ID.” This is a policy, not a claim that EXCEPT differs arbitrarily across engines. PostgreSQL EXCEPT without ALL eliminates duplicates, treating NULLs as not distinct for that purpose. Ordinary equality in a correlated predicate is a different rule.

WITH active(user_id) AS (VALUES (1), (1), (2), (NULL)),
     banned(user_id) AS (VALUES (2), (NULL))
SELECT DISTINCT a.user_id
FROM active AS a
WHERE a.user_id IS NOT NULL
  AND NOT EXISTS (SELECT 1 FROM banned AS b WHERE b.user_id = a.user_id);
-- result: one row, 1

If anonymous active rows should survive, remove the outer IS NOT NULL deliberately and expect one NULL output after DISTINCT. Test both policies. Filtering only NULLs from the banned side of NOT IN still rejects an outer NULL when the filtered list is nonempty.

Reject a cyclic prerequisite schedule before startup

For A → B → C → A, every indegree is one, so Kahn’s initial queue is empty and its output omits all three vertices. The demo raises ValueError; it does not reconstruct the cycle path. For a helpful path diagnostic, add a separate active-stack DFS or strongly-connected-component pass. Validate the graph before launching jobs and stop consumers after prerequisite failure—do not treat “queue empty” as “all work succeeded.”

Where this shows up in the rest of the plan

Root: Discrete math threads through everything

Label: S027 · Trees & tries

Desc: Trees are graphs with structure — traversal orders (preorder, inorder, postorder) are DFS variants.

Label: S033 · DP

Desc: DP problems are usually graph-traversals on an implicit DAG of subproblems.

Label: S035 · Relational model

Desc: Codd's algebra IS set theory. SQL extends that model with bags, NULLs, grouping and many other features.

Label: Graph databases (related topic)

Desc: Neo4j, DGraph, TigerGraph — traversals are the first-class query.

Label: S072 · Consensus protocols

Desc: Raft/Paxos correctness proofs use propositional + temporal logic.

Label: Prompt graphs / LangGraph (related topic)

Desc: Acyclic tool dependencies can use a topological order; agent loops require explicit iteration and termination rules.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Recall — click each to reveal

Q: What are the three basic set operations, and their Python operators?

A: Union (∪, |), intersection (∩, &), difference (∖, -). Bonus: symmetric difference (△, ^) is the ‘in exactly one of the two’ set.

Q: State De Morgan's laws.

A: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q. Read: NOT distributes over AND/OR by flipping the connective.

Q: You have 10 candidates and want to hire 3 for a team. How many possible teams? What if you also want to rank them 1st/2nd/3rd?

A: Team (unordered): C(10,3) = 120. Ranked (ordered): P(10,3) = 720. The ranked version is 3! = 6 times larger because each team has 6 orderings.

Q: What's the difference between a permutation with and without replacement?

A: Without replacement each item can be used at most once — n·(n-1)·(n-2)…. With replacement (like 4-digit PINs) each slot has all n choices — nʳ.

Q: When should you choose BFS over DFS?

A: BFS when you need the shortest number of hops (shortest path in an unweighted graph, level-order), OR you want to explore layer by layer. DFS is a basis for path enumeration, directed cycle detection with active-path state, and topological sorting with finish times. Memory depends on implementation and graph shape; the demo’s duplicate pending entries mean DFS is not automatically the smaller-memory choice.

Q: What does a topological sort require and what does it produce?

A: Requires a directed acyclic graph (DAG). Produces a linear ordering of nodes such that for every edge u → v, u appears before v. Used for build order, task scheduling, class prereqs, migration ordering.

Q: Adjacency list vs adjacency matrix — pick two axes to decide.

A: Sparsity: list wins on sparse graphs (memory O(V+E) vs O(V²)). Edge-lookup frequency: matrix wins when you constantly ask ‘is edge (u,v) present?’ — O(1) vs O(degree).

Q: Simplify: NOT (x AND (y OR NOT z)).

A: NOT x OR NOT (y OR NOT z) → NOT x OR (NOT y AND z). Two De Morgan applications.

Q: How many bit-strings of length 8 have exactly 3 ones?

A: C(8,3) = 56 — choose which 3 of the 8 positions are ones; the rest are zeros. This is the ‘choose 3 positions’ combination.

Q: Stretch — you have a build system with 200 tasks and want to run independent ones in parallel. Sketch an algorithm.

Stretch: true

A: 1. Build the DAG (prerequisite → dependent task). 2. Compute in-degree of every task. 3. Enqueue all in-degree-0 tasks; run them in parallel. 4. When any finishes, decrement its neighbours' in-degrees; enqueue any that just hit 0. 5. Repeat until queue empties. Decrement only after successful completion; on failure block consumers, and avoid double-decrement on retries. If nothing is ready or running while unfinished tasks remain, report a cycle or blocked prerequisite. This is a simplified scheduler model, not the full implementation of any named build system.

Explain-out-loud test

1. What's the difference between a permutation and a combination? Give one real example of each.
2. State one of De Morgan's laws in plain English.
3. What is a DAG and name one everyday example.

Explain-out-loud answer guide

1. A permutation orders selected distinct items, so a podium from five runners has 5·4·3 = 60 outcomes. A three-person team ignores order and has 60/3! = 10 outcomes.

2. “Not both p and q” means “not p or not q.” Exhausting four Boolean pairs proves this finite identity; SQL additionally has UNKNOWN and must be interpreted under its own tables.

3. A DAG is a directed graph with no directed cycle. With edges prerequisite → consumer, a topological order executes each prerequisite first; independent nodes can admit several valid orders.

What comes next

Next in sequence: S017 · Vectors. The destination is a navigation link, not part of this review’s acceptance.

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Corrective source notes

• Python set operations: distinct hashable elements, membership and set algebra; Boolean operands need not themselves be bool.
• Python 3.12 math: exact comb/perm integer contracts. Formulas above assume their stated counting domains.
• Python graphlib: topological order and DAG condition. Its dictionary API stores predecessors; our graph functions store outgoing neighbours.
• PostgreSQL subqueries, SELECT, DISTINCT and expression evaluation: bags, NULL, NOT IN/EXISTS and no fixed left-to-right evaluation order.

The Boolean truth-table check exhausts its four inputs; finite graph/counting fixtures do not prove every graph. The SQL examples were checked in a small SQLite fixture and against PostgreSQL documentation, not a running PostgreSQL service. Pigeonhole, counting and birthday formulas are analytic arguments under the explicitly stated assumptions. Optional media and historical anecdotes are not execution evidence.