Discrete Math & Graphs — Cheat Sheet

Sets group distinct items, logic combines true/false conditions, and combinatorics counts possibilities — the discrete foundations behind algorithms, feature engineering, and reasoning systems.

• ✓Set operations (∪, ∩, −) power dedup, vocabularies, and Jaccard similarity
• ✓Boolean logic underlies rule systems, decision-tree splits, and guardrail conditions
• ✓Combinatorics counts arrangements (permutations) and selections (combinations)
• ✓Factorial growth explains the combinatorial explosion that motivates heuristics & search

a = {"nlp", "python", "ml", "data"}
b = {"python", "ml", "cloud"}

print(a & b)                 # {'ml','python'}  intersection
print(a | b)                 # union
jaccard = len(a & b) / len(a | b)
print(round(jaccard, 3))     # 0.4  -> set-based similarity

Graphs model entities and their relationships; traversals like BFS and DFS explore them — the structures behind knowledge graphs, recommendation engines, and graph neural networks.

• ✓Graphs = nodes + edges; the model for relational data (social, knowledge, recommenders)
• ✓BFS explores level by level (shortest paths); DFS goes deep (reachability, cycles)
• ✓DAGs model dependencies — including the autograd computation graph
• ✓Graph Neural Networks let nodes aggregate neighbour info — fraud, molecules, recommendations

from collections import deque

graph = {
    "A": ["B", "C"], "B": ["A", "D"],
    "C": ["A", "D"], "D": ["B", "C", "E"], "E": ["D"],
}

def bfs(start):
    seen, order, q = {start}, [], deque([start])
    while q:
        node = q.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in seen:
                seen.add(nb); q.append(nb)
    return order

print(bfs("A"))   # ['A','B','C','D','E'] level by level