Math for Data Science · MDS-7
The math that computers actually run on — logic, counting, graphs, and number theory, every idea grounded in Python code.
Discrete mathematics is the foundation of computer science: it is the math of logic, counting, structure, and algorithms rather than continuous change. This course builds the subject from propositional logic through graph theory, number theory, and asymptotic analysis, pairing every concept with a hands-on Python implementation. By the end you can write rigorous proofs, count and model with combinatorics and graphs, reason about modular arithmetic for hashing and crypto, and analyze how fast an algorithm grows.
Course Outline
Every lesson is self-contained: a full explanation, worked step-by-step examples (in Python), common mistakes, a try-it-yourself, and an interactive quiz. Jump to a unit:
Logic begins with propositions — statements that are definitively true or false — combined by connectives into compound claims.
A proposition is a declarative statement with a single, unambiguous truth value: True or False. 'It is raining' is a proposition; 'close the door' is not. Logical connectives build compound propositions from simpler ones: NOT (negation, flips the value), AND (conjunction, true only when both parts are true), OR (disjunction, true when at least one part is true), implication (p implies q), and biconditional (p if and only if q). This matters in CS because every if-statement, database query filter, and circuit reduces to a Boolean expression over propositions. In Python the connectives map directly to not, and, or — so reasoning about logic is reasoning about the code you write every day.
Worked Example 1
Problem. Let p = 'It is sunny' and q = 'We go hiking'. Express 'It is sunny and we do not go hiking' symbolically and evaluate it when p is True and q is False.
Answer. p AND (NOT q) evaluates to True.
Worked Example 2
Problem. Evaluate the disjunction (p OR q) for all four combinations of p and q.
Answer. p OR q is True, True, True, False for the four rows; only F OR F is False.
Problem. Let p = 'The number is even' and q = 'The number is positive'. Write 'the number is even or not positive' symbolically and evaluate it for the number -4.
Solution. Symbolically: p OR (NOT q). For -4: it is even so p = True; it is not positive so q = False, making NOT q = True. The expression is True OR True = True. (Even one true disjunct suffices.) Answer: True.
A truth table exhaustively lists a compound statement's value for every input combination, revealing tautologies, contradictions, and equivalences.
A truth table enumerates all 2^n combinations of n propositional variables and computes the resulting truth value of a compound statement in each row. A tautology is a statement that is True in every row (e.g., p OR NOT p); a contradiction is False in every row. Two statements are logically equivalent when their truth tables are identical column-for-column — they are interchangeable in any context. This is the foundation of program optimization and circuit simplification: if two expressions are equivalent, you can replace the costlier one with the cheaper one. In Python, itertools.product(*[(True,False)]*n) generates every row, so you can verify equivalences mechanically rather than by hand.
Worked Example 1
Problem. Build the truth table for p implies q.
Answer. p implies q is True, False, True, True down the rows.
Worked Example 2
Problem. Show that 'p implies q' is logically equivalent to 'NOT p OR q'.
Answer. The two columns are identical (T,F,T,T), so p implies q is equivalent to NOT p OR q.
Worked Example 3
Problem. Is (p AND q) OR (NOT p) a tautology?
Answer. No — it is False when p is True and q is False, so it is not a tautology.
Problem. Use a truth table to decide whether NOT(p AND q) is equivalent to NOT p OR NOT q.
Solution. NOT(p AND q): (T,T): not T = F; (T,F): not F = T; (F,T): not F = T; (F,F): not F = T -> F,T,T,T. NOT p OR NOT q: (T,T): F or F = F; (T,F): F or T = T; (F,T): T or F = T; (F,F): T or T = T -> F,T,T,T. The columns match in all four rows, so they are equivalent — this is De Morgan's law. Answer: equivalent.
From a single implication you can form its converse, inverse, and contrapositive — only one of which is always equivalent to the original.
Given the conditional p implies q, three related statements arise: the converse q implies p, the inverse NOT p implies NOT q, and the contrapositive NOT q implies NOT p. A crucial fact is that an implication is logically equivalent to its contrapositive but NOT to its converse or inverse. The biconditional p if and only if q is true exactly when p and q share the same truth value, and equals (p implies q) AND (q implies p). This matters in CS because proofs and program logic often replace a hard-to-prove implication with its easier contrapositive, and because confusing a statement with its converse is one of the most common reasoning bugs (affirming the consequent). Knowing which forms are equivalent prevents invalid inferences.
Worked Example 1
Problem. For 'If n is divisible by 4, then n is even,' write the converse and contrapositive.
Answer. Converse: 'If n is even then n is divisible by 4' (false). Contrapositive: 'If n is odd then n is not divisible by 4' (true).
Worked Example 2
Problem. Verify by truth table that p implies q equals its contrapositive NOT q implies NOT p.
Answer. Both columns are T,F,T,T, confirming the implication equals its contrapositive.
Problem. Write the contrapositive of 'If a graph is a tree, then it has no cycles,' and state whether it is equivalent to the original.
Solution. Let p = 'graph is a tree', q = 'graph has no cycles'. Contrapositive: NOT q implies NOT p = 'If a graph has a cycle, then it is not a tree.' Because an implication is always logically equivalent to its contrapositive, this statement has the same truth value as the original. Answer: contrapositive is 'If a graph has a cycle then it is not a tree'; yes, it is equivalent.
Predicates are propositions with variables; quantifiers bind those variables to make definite claims over a domain.
A predicate P(x) is a statement whose truth depends on the value of x — 'x > 5' is not true or false until x is given. Quantifiers turn predicates into propositions: the universal quantifier 'for all x, P(x)' claims P holds for every element of the domain, while the existential 'there exists x, P(x)' claims at least one element satisfies P. Negation follows De Morgan-style rules: NOT(for all x, P(x)) becomes 'there exists x, NOT P(x)', and NOT(there exists x, P(x)) becomes 'for all x, NOT P(x)'. Order matters when quantifiers nest. This is central to specifying program correctness ('for all inputs the output is sorted'), database queries, and formal verification. In Python, all() and any() over a domain directly implement universal and existential quantification.
Worked Example 1
Problem. Over the domain {2, 4, 6, 8}, evaluate 'for all x, x is even' and 'there exists x, x > 7'.
Answer. 'For all x even' is True; 'there exists x > 7' is True.
Worked Example 2
Problem. Negate 'For all integers n, n^2 >= n' and decide if the negation is true.
Answer. Negation: 'There exists an integer n with n^2 < n.' This negation is False (the original universal statement is True over the integers).
Worked Example 3
Problem. Distinguish 'for all x there exists y: y > x' from 'there exists y for all x: y > x' over the integers.
Answer. 'For all x, there exists y > x' is True; 'there exists y, for all x, y > x' is False. Quantifier order matters.
Problem. Over the domain of all real numbers, write the negation of 'There exists x such that x^2 = -1' and say whether the negation is true.
Solution. Negation of an existential is a universal with the predicate negated: 'For all real x, x^2 is not equal to -1.' Since a real square is always >= 0, no real x satisfies x^2 = -1, so the original existential is False and its negation is True. Answer: 'For all real x, x^2 != -1'; the negation is True.
Valid arguments derive conclusions from premises using truth-preserving rules like modus ponens, independent of the actual facts.
An argument is a set of premises and a conclusion; it is valid when the conclusion is true in every case where all premises are true — validity is about form, not content. Core rules of inference include modus ponens (from p and p implies q, conclude q), modus tollens (from NOT q and p implies q, conclude NOT p), hypothetical syllogism (chain implications), and disjunctive syllogism (from p OR q and NOT p, conclude q). Recognizing valid forms — and the invalid look-alikes like affirming the consequent — is essential for writing correct proofs, designing decision logic, and avoiding fallacies in algorithms and AI reasoning. A valid argument with true premises is called sound.
Worked Example 1
Problem. Premises: 'If it rains, the game is cancelled' and 'It is raining.' What follows?
Answer. By modus ponens, the game is cancelled.
Worked Example 2
Problem. Premises: 'If the file exists, the program runs' and 'The program did not run.' What follows?
Answer. By modus tollens, the file does not exist.
Worked Example 3
Problem. Is this valid? 'If it rains, the streets are wet. The streets are wet. Therefore it rained.'
Answer. Invalid — it commits the fallacy of affirming the consequent.
Problem. Given 'If a number is prime and greater than 2, it is odd' and 'n is prime and greater than 2,' what valid conclusion follows, and by which rule?
Solution. Let p = 'n is prime and greater than 2' and q = 'n is odd'. The premises are p implies q and p. By modus ponens we conclude q. Answer: 'n is odd', by modus ponens.
These three methods are the workhorses for proving implications and existence claims rigorously.
A direct proof assumes the hypothesis p and derives the conclusion q through a chain of valid steps. A proof by contrapositive instead proves the equivalent statement NOT q implies NOT p, which is often easier (handy when the hypothesis is hard to use directly). A proof by contradiction assumes the statement is false, then derives an impossibility, forcing the original to be true — this is how we prove the square root of 2 is irrational and that there are infinitely many primes. Choosing the right technique is a core skill: it makes the difference between a clean proof and a stuck one. These methods underpin algorithm correctness arguments and the formal reasoning behind data-structure invariants.
Worked Example 1
Problem. Prove directly: if n is even, then n^2 is even.
Answer. n^2 = 2(2k^2) is even, completing the direct proof.
Worked Example 2
Problem. Prove by contrapositive: if n^2 is even, then n is even.
Answer. Since n odd forces n^2 odd, by contrapositive n^2 even forces n even.
Worked Example 3
Problem. Prove by contradiction that the square root of 2 is irrational.
Answer. The contradiction shows no such a/b exists, so sqrt(2) is irrational.
Problem. Prove that if 3n + 2 is odd, then n is odd. Choose and justify a technique.
Solution. Use the contrapositive: prove 'if n is even, then 3n + 2 is even.' Assume n is even, n = 2k. Then 3n + 2 = 6k + 2 = 2(3k + 1), which is 2 times an integer, hence even. This proves the contrapositive, so the original statement holds: if 3n + 2 is odd then n is odd. Contrapositive is chosen because reasoning from 'n even' is concrete, whereas using the odd hypothesis directly is awkward.
Induction proves a statement for all integers from a base value by showing it survives the step from n to n+1.
Mathematical induction proves a statement P(n) holds for all integers n >= n0 in two parts: the base case verifies P(n0) directly, and the inductive step assumes P(k) (the inductive hypothesis) and proves P(k+1). Together they create a domino effect covering every n. Strong induction allows assuming P holds for all values up to k, useful for recursive definitions. Induction is the mathematical mirror of recursion and loops in programming: it is how we prove loop invariants, recurrence-based running times, and that recursive algorithms terminate correctly. Mastering the precise structure — clearly state the hypothesis and show exactly where you use it — separates valid proofs from hand-waving.
Worked Example 1
Problem. Prove by induction that 1 + 2 + ... + n = n(n+1)/2 for all n >= 1.
Answer. Base and step hold, so the formula is true for all n >= 1.
Worked Example 2
Problem. Prove that 2^n > n for all n >= 1.
Answer. By induction, 2^n > n for all n >= 1.
Worked Example 3
Problem. Prove that n^3 - n is divisible by 3 for all n >= 0.
Answer. Both parts hold, so 3 divides n^3 - n for all n >= 0.
Problem. Prove by induction that 1 + 3 + 5 + ... + (2n - 1) = n^2 for all n >= 1.
Solution. Base case n=1: left = 1, right = 1^2 = 1. Holds. Inductive hypothesis: assume 1 + 3 + ... + (2k - 1) = k^2. Step: add the next odd term (2(k+1) - 1) = 2k + 1 to both sides: 1 + 3 + ... + (2k - 1) + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2, which is the statement at n = k+1. Base and step hold, so the sum of the first n odd numbers equals n^2 for all n >= 1.
Write a Python function that takes a logical expression over a few variables (using AND, OR, NOT, and implication) and prints its full truth table. Use itertools.product to enumerate every combination of True/False inputs. Then use your engine to verify a logical equivalence of your choice, such as that an implication equals its contrapositive, and confirm that De Morgan's laws hold.
Deliverable · A script that prints labeled truth tables and a short note showing two equivalences your engine confirmed.
1. Which statement is logically equivalent to the implication 'p implies q'?
Answer B. An implication is always logically equivalent to its contrapositive; the converse and inverse are not equivalent to the original.
2. The implication 'p implies q' is false in exactly which case?
Answer C. An implication is false only when the hypothesis is true but the conclusion is false; in all other cases it is true.
3. Which of these is a tautology?
Answer B. p OR not-p (the law of excluded middle) is true for every value of p, so it is a tautology; p AND not-p is a contradiction.
4. What is the negation of 'For all x, P(x)'?
Answer B. Negating a universal quantifier yields an existential one with the predicate negated: there exists an x for which P(x) fails.
5. In a proof by mathematical induction, the inductive step proves that:
Answer B. Induction establishes a base case and then shows the truth of the statement at n implies its truth at n+1, covering all integers from the base on.
I can translate statements into propositional and predicate logic and evaluate them with truth tables.
I can identify valid arguments and choose an appropriate proof technique.
I can prove a statement by direct proof, contradiction, and mathematical induction.
Sets are unordered collections of distinct elements; set-builder notation defines them by a membership rule.
A set is a collection of distinct objects where order and repetition do not matter — {1, 2, 3} equals {3, 1, 1, 2}. The only question a set answers is whether an element belongs (membership). A is a subset of B if every element of A is also in B. Set-builder notation defines a set by a property, like {x : x is an even integer, 0 < x < 10}. Sets are the bedrock of data science and CS: relational databases, deduplication, type systems, and probability all rest on set theory. Python's set type mirrors the math exactly — membership with 'in', subset with <=, and comprehensions {x for x in ... if ...} that read like set-builder notation.
Worked Example 1
Problem. List the set A = {x : x is a positive integer and x divides 12} in roster form.
Answer. A = {1, 2, 3, 4, 6, 12}.
Worked Example 2
Problem. Is {2, 4} a subset of {1, 2, 3, 4, 5}? Is it a proper subset?
Answer. Yes, {2, 4} is a proper subset of {1, 2, 3, 4, 5}.
Problem. Write the set of perfect squares less than 30 in both set-builder and roster form, and state how many elements it has.
Solution. Set-builder: {n^2 : n is a positive integer and n^2 < 30}. Computing squares: 1, 4, 9, 16, 25 (next is 36 >= 30). Roster: {1, 4, 9, 16, 25}. In Python: {n*n for n in range(1, 30) if n*n < 30}. It has 5 elements.
These four operations combine and compare sets, and obey identities like De Morgan's laws.
Union (A union B) collects everything in either set; intersection (A intersect B) keeps only shared elements; difference (A minus B) keeps elements of A not in B; complement (A') is everything in the universal set outside A. These operations satisfy algebraic identities — commutativity, associativity, distributivity, and De Morgan's laws — that mirror logical AND/OR/NOT exactly. This is why set operations power SQL joins, search filters, and feature engineering in data science. Python's set supports them directly: A | B, A & B, A - B, and complement via U - A. Recognizing the identities lets you rewrite costly queries into cheaper equivalents.
Worked Example 1
Problem. Given A = {1,2,3,4} and B = {3,4,5,6}, compute A union B, A intersect B, and A minus B.
Answer. A union B = {1,2,3,4,5,6}; A intersect B = {3,4}; A minus B = {1,2}.
Worked Example 2
Problem. With universe U = {1,...,8}, A = {1,2,3,4}, B = {3,4,5,6}, verify De Morgan: (A union B)' = A' intersect B'.
Answer. Both sides equal {7,8}, confirming De Morgan's law for sets.
Problem. With U = {1,...,10}, A = {2,4,6,8,10} (evens), B = {3,6,9} (multiples of 3), compute A intersect B and (A union B)'.
Solution. A intersect B = elements in both = {6} (only 6 is even and a multiple of 3). A union B = {2,3,4,6,8,9,10}. Its complement relative to U is U minus that = {1,5,7}. Python: A&B == {6}; (set(range(1,11)) - (A|B)) == {1,5,7}. Answers: A intersect B = {6}; (A union B)' = {1,5,7}.
The power set lists all subsets; the Cartesian product pairs elements; cardinality measures size.
The power set P(A) is the set of all subsets of A, including the empty set and A itself; if |A| = n then |P(A)| = 2^n, because each element is independently in or out of a subset. The Cartesian product A x B is the set of all ordered pairs (a, b) with a in A and b in B, and |A x B| = |A| * |B|. Cardinality is just the size of a set. These ideas explain combinatorial explosion (why brute-forcing all subsets is exponential), relational database tables (rows are tuples from a Cartesian product), and feature spaces in machine learning. Python's itertools.product and itertools.combinations generate these structures.
Worked Example 1
Problem. List the power set of A = {a, b} and state its cardinality.
Answer. P(A) = {{}, {a}, {b}, {a, b}}; cardinality 4.
Worked Example 2
Problem. For A = {1, 2} and B = {x, y, z}, list A x B and give |A x B|.
Answer. A x B = {(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)}; |A x B| = 6.
Worked Example 3
Problem. How many subsets of a 10-element set contain at least one element?
Answer. 1023 nonempty subsets.
Problem. A set A has 5 elements. How many elements does P(A) have, and how many of those subsets have exactly 2 elements?
Solution. |P(A)| = 2^5 = 32 total subsets. The number of 2-element subsets is the combination 5 choose 2 = 10. In Python: 2**5 = 32 and math.comb(5, 2) = 10. Answers: 32 subsets total, 10 of which have exactly 2 elements.
A relation is a set of pairs; key properties classify how it links elements.
A relation R on a set A is a subset of A x A — a set of ordered pairs declaring which elements relate. Three properties matter most: reflexive (every element relates to itself, (a,a) in R for all a), symmetric (if (a,b) in R then (b,a) in R), and transitive (if (a,b) and (b,c) in R then (a,c) in R). Relations model 'less than', 'is connected to', 'is a friend of', and database foreign keys. Testing these properties is straightforward in Python by representing R as a set of tuples and checking the defining conditions with loops or comprehensions. These properties combine to define orderings and equivalence relations.
Worked Example 1
Problem. On A = {1,2,3}, is R = {(1,1),(2,2),(3,3),(1,2),(2,1)} reflexive, symmetric, transitive?
Answer. R is reflexive, symmetric, and transitive.
Worked Example 2
Problem. Is the relation 'less than' (<) on integers reflexive? Symmetric? Transitive?
Answer. '<' is transitive only; it is neither reflexive nor symmetric.
Problem. On A = {1,2,3}, classify R = {(1,1),(2,2),(3,3),(1,2),(2,3)} for reflexive, symmetric, transitive.
Solution. Reflexive: (1,1),(2,2),(3,3) all present -> reflexive. Symmetric: (1,2) is present but (2,1) is not -> NOT symmetric. Transitive: (1,2) and (2,3) require (1,3), which is missing -> NOT transitive. In Python you would check: all((b,a) in R for (a,b) in R) returns False (symmetry fails). Answer: reflexive only.
An equivalence relation (reflexive, symmetric, transitive) splits a set into disjoint equivalence classes.
A relation that is reflexive, symmetric, AND transitive is an equivalence relation. Its defining power is that it partitions the underlying set into equivalence classes: nonempty, disjoint subsets that together cover the whole set, where every element relates exactly to the members of its own class. 'Has the same remainder mod 5', 'is the same color', and 'is in the same connected component' are equivalence relations. This duality — equivalence relations correspond one-to-one with partitions — is fundamental for grouping, clustering, hashing into buckets, and union-find data structures. In Python you can compute classes by grouping elements that relate, then verify the classes are disjoint and cover the set.
Worked Example 1
Problem. On the integers, show 'a ~ b iff a - b is divisible by 3' is an equivalence relation and list its classes.
Answer. It is an equivalence relation; the three classes are integers with remainder 0, 1, and 2 mod 3.
Worked Example 2
Problem. Partition {1,...,6} by the relation 'same parity' and give the classes.
Answer. Two classes: {1,3,5} and {2,4,6}.
Problem. Is 'a ~ b iff a and b have the same number of digits' an equivalence relation on positive integers? If so, describe two classes.
Solution. Reflexive: a has the same digit count as itself -> yes. Symmetric: if a and b have the same count, so do b and a -> yes. Transitive: same count is transitive -> yes. So it is an equivalence relation. Two classes: all 1-digit numbers {1,...,9} and all 2-digit numbers {10,...,99}. Each positive integer falls in exactly one class by its digit length.
Functions map each input to one output; injective, surjective, and bijective describe how inputs and outputs correspond.
A function f from A to B assigns exactly one output in B to each input in A. It is injective (one-to-one) if distinct inputs give distinct outputs (no collisions); surjective (onto) if every element of the codomain B is hit by some input; and bijective if both — establishing a perfect one-to-one correspondence with an inverse. These properties decide whether a function can be inverted, whether a hash has collisions, and whether two sets have equal size. In Python you can test injectivity by checking len(set(outputs)) == len(inputs), and surjectivity by checking set(outputs) == codomain. Bijections are the formal basis for counting by correspondence.
Worked Example 1
Problem. Is f(x) = 2x from integers to integers injective? Surjective?
Answer. f(x) = 2x is injective but not surjective onto the integers.
Worked Example 2
Problem. For f: {1,2,3} -> {a,b} with f(1)=a, f(2)=b, f(3)=a, classify f.
Answer. f is surjective but not injective, so not bijective.
Worked Example 3
Problem. Show f(x) = x + 5 on the integers is bijective.
Answer. f(x) = x + 5 is bijective with inverse x - 5.
Problem. Classify f: {1,2,3,4} -> {1,2,3,4} defined by f(x) = (x mod 4) + 1 as injective, surjective, and/or bijective.
Solution. Compute outputs: f(1)=2, f(2)=3, f(3)=4, f(4)=(0)+1=1. Outputs are {2,3,4,1} = {1,2,3,4}. All four outputs distinct -> injective. Outputs cover the codomain -> surjective. Both -> bijective. In Python: outs=[(x%4)+1 for x in [1,2,3,4]] gives [2,3,4,1]; len(set(outs))==4 and set(outs)=={1,2,3,4}. Answer: bijective.
Some infinite sets can be listed (countable); others, like the reals, cannot (uncountable).
A set is countable if its elements can be put in one-to-one correspondence with the natural numbers — that is, listed in a sequence (possibly infinite) so each element eventually appears. The integers and even the rationals are countable, despite seeming larger, because clever enumerations list them all. A set is uncountable if no such listing exists; Cantor's diagonal argument proves the real numbers are uncountable — there are strictly more reals than naturals. This distinction underlies computability theory: there are only countably many programs but uncountably many functions, so most functions are uncomputable. Understanding it sharpens intuition about what algorithms can and cannot do.
Worked Example 1
Problem. Show the set of even natural numbers is countable.
Answer. Yes — n maps to 2n is a bijection with the naturals, so the evens are countable.
Worked Example 2
Problem. Sketch why the real numbers in (0,1) are uncountable (Cantor's diagonal).
Answer. The diagonal number d cannot be in any proposed list, so (0,1) is uncountable.
Problem. Is the set of all finite-length strings over the alphabet {0,1} countable or uncountable? Justify.
Solution. It is countable. List strings by length, then lexicographically within each length: '' (empty), '0','1', '00','01','10','11', '000', ... Every finite string has a finite length and a finite position within that length, so each appears at some point in the list — a bijection with the naturals. (By contrast, INFINITE binary sequences are uncountable.) Answer: countable.
Using Python's built-in set type, implement and verify the core set identities (such as De Morgan's laws and distributivity) on randomly generated sets. Then represent a relation as a set of tuples and write functions that test whether it is reflexive, symmetric, and transitive. Use your checker to decide whether a given relation is an equivalence relation and, if so, print its partition into equivalence classes.
Deliverable · A script that confirms two set identities by example and reports the reflexive/symmetric/transitive status of at least three sample relations.
1. If a set has 4 elements, how many subsets does it have?
Answer C. A set with n elements has 2^n subsets, so 2^4 = 16, which is the size of its power set.
2. An equivalence relation must be:
Answer A. By definition an equivalence relation is reflexive, symmetric, and transitive, which lets it partition a set into disjoint classes.
3. A function f is surjective (onto) when:
Answer B. Surjective means the range equals the codomain: every target value is the image of some input. Distinct outputs from distinct inputs describes injective.
4. What is the cardinality of the Cartesian product A x B if |A| = 3 and |B| = 5?
Answer B. The Cartesian product contains every ordered pair, so |A x B| = |A| * |B| = 3 * 5 = 15.
5. Which set is uncountable?
Answer D. The reals are uncountable (Cantor's diagonal argument); the integers, naturals, and rationals are all countably infinite.
I can perform set operations and reason about cardinality, power sets, and Cartesian products.
I can classify a relation and recognize an equivalence relation and its partition.
I can determine whether a function is injective, surjective, or bijective.
The two basic counting rules break a problem into mutually exclusive choices (add) or sequential independent choices (multiply).
The sum rule says that if a task can be done in one of several mutually exclusive ways — m ways OR n ways with no overlap — the total is m + n. The product rule says that if a procedure consists of a sequence of independent steps with m choices then n choices, the total is m * n. Almost every counting problem decomposes into combinations of these two rules; getting the decomposition right is the whole game. They underpin counting passwords, database keys, decision trees, and the size of state spaces in algorithms. In Python, nested loops or itertools.product realize the product rule, while summing disjoint case counts realizes the sum rule.
Worked Example 1
Problem. A menu has 3 appetizers and 4 desserts. How many ways to order exactly one item that is either an appetizer or a dessert?
Answer. 7 ways.
Worked Example 2
Problem. A meal is one appetizer AND one dessert. How many distinct meals?
Answer. 12 meals.
Worked Example 3
Problem. How many 4-character codes use an uppercase letter for each position (26 letters)?
Answer. 456,976 codes.
Problem. A license plate is 2 letters followed by 3 digits. How many plates are possible (letters 26, digits 10)?
Solution. Each position is an independent step, so use the product rule across all five positions: 26 * 26 * 10 * 10 * 10 = 26^2 * 10^3 = 676 * 1000 = 676,000. In Python: 26**2 * 10**3 = 676000. Answer: 676,000 plates.
Permutations count ordered arrangements, where the order of selection matters.
A permutation is an ordered arrangement of objects. The number of ways to arrange all n distinct objects is n! (n factorial). The number of ordered arrangements of k objects chosen from n is P(n, k) = n! / (n - k)!, since the first position has n choices, the next n-1, and so on for k positions. When objects repeat, divide by the factorials of each repeated group to avoid overcounting. Permutations count rankings, schedules, and orderings of tasks, and appear in sorting analysis and password strength. Python's math.factorial, math.perm, and itertools.permutations compute and enumerate them directly.
Worked Example 1
Problem. How many ways can 4 distinct runners finish 1st, 2nd, and 3rd (a podium of 3 from 4)?
Answer. 24 podium orderings.
Worked Example 2
Problem. How many distinct arrangements of the letters in 'LEVEL'?
Answer. 30 distinct arrangements.
Worked Example 3
Problem. In how many ways can 6 people sit in a row?
Answer. 720 seatings.
Problem. How many distinct ways can the letters of 'BANANA' be arranged?
Solution. BANANA has 6 letters: A appears 3 times, N appears 2 times, B appears 1 time. Distinct arrangements = 6! / (3! * 2! * 1!) = 720 / (6 * 2) = 720 / 12 = 60. In Python: math.factorial(6)//(math.factorial(3)*math.factorial(2)) = 60. Answer: 60 arrangements.
Combinations count unordered selections, given by the binomial coefficient n choose k.
A combination is a selection where order does NOT matter. The number of ways to choose k items from n is the binomial coefficient C(n, k) = n! / (k! (n - k)!), read 'n choose k'. It equals the number of permutations P(n,k) divided by k!, because the k! orderings of any chosen set are all the same combination. Combinations count committees, lottery tickets, poker hands, and subsets of a fixed size, and appear throughout probability and machine learning (feature subsets). A key identity is C(n, k) = C(n, n - k). Python's math.comb(n, k) and itertools.combinations compute and list them.
Worked Example 1
Problem. How many 2-person teams can be formed from 5 people?
Answer. 10 teams.
Worked Example 2
Problem. How many 5-card hands can be dealt from a 52-card deck?
Answer. 2,598,960 hands.
Worked Example 3
Problem. Verify the identity C(8, 3) = C(8, 5).
Answer. Both equal 56, confirming the symmetry identity.
Problem. A pizza shop offers 7 toppings. How many ways to choose exactly 3 different toppings?
Solution. Order of toppings does not matter, so use combinations: C(7, 3) = 7!/(3! 4!) = (7 * 6 * 5)/(3 * 2 * 1) = 210/6 = 35. In Python: math.comb(7, 3) = 35. Answer: 35 ways.
The binomial theorem expands (x + y)^n using binomial coefficients, which form Pascal's triangle.
The binomial theorem states that (x + y)^n = sum over k from 0 to n of C(n, k) x^(n-k) y^k. Each coefficient is a binomial coefficient, counting how many ways to choose which factors contribute a y. Pascal's triangle arranges these coefficients in rows, where each entry is the sum of the two above it — the identity C(n, k) = C(n-1, k-1) + C(n-1, k). This recurrence gives an efficient way to compute coefficients without factorials and connects counting to algebra. It appears in probability (binomial distribution), polynomial expansion, and dynamic-programming tables. In Python the triangle is built row by row from the previous row.
Worked Example 1
Problem. Expand (x + y)^3 using the binomial theorem.
Answer. (x + y)^3 = x^3 + 3x^2 y + 3x y^2 + y^3.
Worked Example 2
Problem. Find the coefficient of x^2 in (x + 2)^5.
Answer. The coefficient of x^2 is 80.
Worked Example 3
Problem. Build row 4 of Pascal's triangle from row 3 (1,3,3,1).
Answer. Row 4 is 1, 4, 6, 4, 1.
Problem. What is the coefficient of x^4 in the expansion of (x + 1)^6?
Solution. General term: C(6, k) x^(6-k) 1^k. For x^4 we need 6 - k = 4, so k = 2. Coefficient = C(6, 2) * 1^2 = 15 * 1 = 15. In Python: math.comb(6, 2) = 15. Answer: 15.
When selections allow repetition, counts change; stars and bars counts distributions of identical items.
If you choose k items from n types with repetition allowed and order matters, the count is n^k. If order does not matter, the count is C(n + k - 1, k) — the stars and bars formula. Stars and bars models distributing k identical items into n distinct bins: line up k stars and n-1 bars to separate bins, and choose where the bars go. This counts nonnegative integer solutions to x1 + x2 + ... + xn = k, which appears in resource allocation, integer-composition problems, and multiset counting. In Python, itertools.combinations_with_replacement enumerates these multisets directly for verification.
Worked Example 1
Problem. How many ways to distribute 5 identical candies among 3 children (some may get none)?
Answer. 21 ways.
Worked Example 2
Problem. How many nonnegative integer solutions does x + y + z + w = 10 have?
Answer. 286 solutions.
Worked Example 3
Problem. From 3 flavors of ice cream, how many ways to pick 4 scoops where repeats are allowed and order does not matter?
Answer. 15 ways.
Problem. How many ways can you buy 6 donuts choosing from 4 varieties (repeats allowed, order irrelevant)?
Solution. This is a multiset selection: choose 6 from 4 types with repetition. Stars and bars: C(6 + 4 - 1, 4 - 1) = C(9, 3) = (9 * 8 * 7)/(3 * 2 * 1) = 504/6 = 84. In Python: math.comb(9, 3) = 84, and len(list(itertools.combinations_with_replacement(range(4), 6))) also equals 84. Answer: 84 ways.
If more items than containers, some container holds at least two items — a simple idea with surprising power.
The pigeonhole principle states that if n items are placed into m containers and n > m, then at least one container holds two or more items. The generalized form: at least one container holds at least ceil(n / m) items. Though almost trivial to state, it proves striking facts: among 13 people two share a birth month, and in any group of n people two have the same number of acquaintances within the group. In CS it proves hash collisions are unavoidable, that lossless compression cannot shrink every input, and bounds in algorithm analysis. The skill is identifying what the 'pigeons' and 'holes' are.
Worked Example 1
Problem. Show that among any 13 people, two share a birth month.
Answer. Yes — 13 people into 12 months guarantees a shared month.
Worked Example 2
Problem. Among 100 integers, must at least 10 share the same remainder mod 9?
Answer. Yes — at least one remainder is shared by at least 12 of them (>= 10).
Problem. A drawer holds socks of 3 colors. How many socks must you pull (in the dark) to guarantee a matching pair?
Solution. Treat colors as 3 holes. Pulling 3 socks could give one of each color (no pair). Pulling a 4th sock: 4 pigeons into 3 holes forces at least one color to have >= 2 socks, i.e. a matching pair. By pigeonhole, 4 socks guarantee a pair. Answer: 4 socks.
To count a union of overlapping sets, add the sizes and subtract the overcounted overlaps in alternating signs.
The inclusion-exclusion principle corrects for double-counting when sets overlap. For two sets: |A union B| = |A| + |B| - |A intersect B|. For three: add the three single sizes, subtract the three pairwise intersections, then add back the triple intersection. In general, alternate signs over intersections of increasing size. This counts how many numbers in a range are divisible by at least one of several divisors, how many permutations avoid certain positions (derangements), and probabilities of unions of events. It is essential in combinatorics and probability. In Python you can verify it by direct set construction with the | operator and len().
Worked Example 1
Problem. In a class, 18 take math, 15 take art, 7 take both. How many take at least one?
Answer. 26 learners take at least one subject.
Worked Example 2
Problem. How many integers from 1 to 100 are divisible by 2 or 5?
Answer. 60 integers.
Worked Example 3
Problem. How many integers from 1 to 100 are divisible by 2, 3, or 5?
Answer. 74 integers.
Problem. Of 50 surveyed people, 30 like coffee, 25 like tea, and 12 like both. How many like neither?
Solution. By inclusion-exclusion, those who like at least one = |coffee union tea| = 30 + 25 - 12 = 43. Those who like neither = total minus that = 50 - 43 = 7. In Python you could verify with set sizes: 30 + 25 - 12 = 43, then 50 - 43 = 7. Answer: 7 people like neither.
For a small problem of your choice (for example, the number of 5-card poker hands of a given type, or arrangements of a word with repeated letters), compute the answer with a closed-form combinatorial formula. Then write a Python brute-force enumeration using itertools.permutations or itertools.combinations that counts the same thing directly. Confirm the two numbers match and explain why the formula generalizes where brute force cannot.
Deliverable · A script that prints both the formula-based count and the brute-force count, with a note on when enumeration becomes infeasible.
1. How many ways can you arrange 5 distinct books in a row on a shelf?
Answer C. Ordered arrangements of all 5 distinct items give 5! = 120.
2. How many ways can a committee of 3 be chosen from 10 people?
Answer B. Order does not matter, so use combinations: 10 choose 3 = 10!/(3!7!) = 120.
3. The pigeonhole principle guarantees that among 13 people, at least two share:
Answer B. There are only 12 months (pigeonholes) for 13 people (pigeons), so by the pigeonhole principle at least two must share a birth month.
4. In the binomial theorem, the coefficient of x^k y^(n-k) in the expansion of (x + y)^n is:
Answer B. Each term of (x + y)^n has coefficient given by the binomial coefficient n choose k, the same numbers that form Pascal's triangle.
5. How many ways can you distribute 7 identical candies among 3 children (some may get none)?
Answer B. This is stars and bars: choose 2 bars among 7 + 2 positions, giving (7 + 3 - 1) choose (3 - 1) = 9 choose 2 = 36.
I can apply the sum and product rules to break a counting problem into steps.
I can count arrangements and selections using permutations, combinations, and stars and bars.
I can use the pigeonhole principle and inclusion-exclusion to solve counting problems.
A graph is a set of vertices joined by edges; degree counts the edges at a vertex.
A graph G = (V, E) is a set of vertices V and a set of edges E, each edge joining a pair of vertices. Graphs model networks of all kinds: social connections, road maps, web links, and dependencies. The degree of a vertex is the number of edges incident to it. The handshake lemma states that the sum of all degrees equals twice the number of edges, because each edge adds one to the degree of each of its two endpoints. A consequence is that the number of odd-degree vertices is always even. Graphs may be directed (edges have direction) or undirected. In Python a graph is naturally a dictionary mapping each vertex to its list of neighbors.
Worked Example 1
Problem. A graph has vertices {A,B,C,D} and edges {A-B, A-C, B-C, C-D}. Find each degree and verify the handshake lemma.
Answer. Degrees A=2, B=2, C=3, D=1; degree sum 8 = 2 x 4 edges, confirming the handshake lemma.
Worked Example 2
Problem. Can a graph have exactly three vertices of odd degree?
Answer. No — the count of odd-degree vertices is always even, so three is impossible.
Problem. A graph has 5 vertices with degrees 3, 3, 2, 2, 2. How many edges does it have?
Solution. By the handshake lemma, the sum of degrees equals twice the number of edges. Sum = 3 + 3 + 2 + 2 + 2 = 12. So edges = 12 / 2 = 6. (The degree sum is even, so such a graph is feasible.) Answer: 6 edges.
Graphs are stored as an adjacency matrix (dense) or an adjacency list (sparse-friendly).
An adjacency matrix is an n-by-n table where entry (i, j) is 1 if an edge joins vertices i and j and 0 otherwise; it uses O(n^2) space and answers 'is there an edge?' in O(1), but wastes space on sparse graphs. An adjacency list stores, for each vertex, a list of its neighbors; it uses O(n + m) space (m = edges), ideal for sparse graphs, and is what most algorithms use. The choice affects the running time of traversals and queries. In Python, an adjacency list is a dict of lists/sets, and a matrix is a list of lists. Symmetric matrices represent undirected graphs.
Worked Example 1
Problem. Build the adjacency matrix for an undirected graph on {0,1,2} with edges 0-1 and 1-2.
Answer. [[0,1,0],[1,0,1],[0,1,0]].
Worked Example 2
Problem. Write the same graph as an adjacency list and give its space cost.
Answer. adj = {0:[1], 1:[0,2], 2:[1]}, using O(n + m) space.
Problem. Give the adjacency matrix and adjacency list for the undirected triangle on vertices {0,1,2} (all pairs connected).
Solution. All three pairs are edges. Adjacency matrix (no self-loops, so diagonal is 0): [[0,1,1],[1,0,1],[1,1,0]]. Adjacency list: {0:[1,2], 1:[0,2], 2:[0,1]}. Each vertex has degree 2 and the matrix is symmetric, consistent with 3 undirected edges.
Paths are routes without repeated vertices; a connected graph has a path between every pair of vertices.
A walk is any sequence of edges; a path is a walk that does not repeat vertices; a cycle is a path that returns to its starting vertex. A graph is connected if there is a path between every pair of vertices; otherwise it splits into connected components. Connectivity is the most basic structural question and is answered by a single traversal: run BFS or DFS from any vertex and check whether it reaches all vertices. These ideas underlie network reliability, reachability in dependency graphs, and detecting whether data forms one cluster or several. In Python, counting the vertices a traversal visits tells you the size of a component.
Worked Example 1
Problem. In the graph {A-B, B-C, C-D}, is there a path from A to D? Name it.
Answer. Yes — the path A -> B -> C -> D connects them.
Worked Example 2
Problem. A graph has edges {1-2, 2-3, 4-5}. How many connected components?
Answer. Two connected components: {1,2,3} and {4,5}.
Problem. Graph edges: {A-B, B-C, C-A, D-E}. Is the graph connected? How many components, and which vertices form a cycle?
Solution. A traversal from A reaches A, B, C (via A-B, B-C, C-A) but never D or E. A traversal from D reaches D, E. So the graph is NOT connected; it has 2 components: {A,B,C} and {D,E}. The vertices A, B, C form a cycle A -> B -> C -> A. Answer: not connected, 2 components, cycle on A,B,C.
A tree is a connected acyclic graph with n-1 edges; a spanning tree connects all vertices of a graph using a tree.
A tree is a connected graph with no cycles. A tree on n vertices has exactly n - 1 edges, and there is a unique path between any two vertices; adding any edge creates a cycle, while removing any edge disconnects it. A spanning tree of a connected graph is a subgraph that is a tree and includes every vertex — it is the minimal connected backbone. Spanning trees power network design (minimal cabling), BFS/DFS trees, and minimum-spanning-tree algorithms (Kruskal, Prim) used in clustering and routing. Recognizing the n-1 edge count is a quick sanity check. In Python, BFS or DFS from a root naturally produces a spanning tree of the visited component.
Worked Example 1
Problem. A connected graph has 6 vertices. If it is a tree, how many edges does it have? If it has 8 edges, how many independent cycles must it contain?
Answer. A tree would have 5 edges; with 8 edges there are 8 - 5 = 3 independent cycles.
Worked Example 2
Problem. Find a spanning tree of the graph with edges {A-B, B-C, C-A, C-D} (4 vertices).
Answer. A valid spanning tree is {A-B, B-C, C-D} (dropping the cycle edge C-A).
Problem. A graph is connected with 10 vertices and 9 edges. Is it necessarily a tree? Explain.
Solution. Yes. A connected graph on n vertices has at least n - 1 edges, and a connected graph with exactly n - 1 edges must be acyclic (an extra edge over n-1 would force a cycle). Here n = 10 and edges = 9 = n - 1, so the graph is connected, has no cycles, and is therefore a tree. Answer: yes, it must be a tree.
BFS explores level by level using a queue; DFS goes as deep as possible using a stack or recursion.
Breadth-first search (BFS) starts at a source and visits all neighbors, then their neighbors, expanding in waves of increasing distance; it uses a FIFO queue and finds shortest paths (in edges) in unweighted graphs. Depth-first search (DFS) plunges along one branch until it dead-ends, then backtracks; it uses a stack or recursion and is the basis for cycle detection, topological sorting, and connected-component labeling. Both visit every vertex exactly once in O(n + m) time with a visited set to avoid revisits. They are the most-used graph algorithms in practice. In Python, BFS uses collections.deque; DFS uses recursion or an explicit list as a stack.
Worked Example 1
Problem. Graph adj = {A:[B,C], B:[A,D], C:[A,D], D:[B,C]}. Give the BFS visiting order from A.
Answer. BFS order from A: A, B, C, D.
Worked Example 2
Problem. For the same graph, give a DFS visiting order from A using recursion (neighbors in listed order).
Answer. DFS order from A: A, B, D, C.
Worked Example 3
Problem. Use BFS to find the shortest path length from A to D in adj = {A:[B,C], B:[A,D], C:[A], D:[B]}.
Answer. Shortest path A to D has length 2 (A -> B -> D).
Problem. Graph adj = {1:[2,3], 2:[1,4], 3:[1,4], 4:[2,3]}. Give the BFS order from vertex 1 and the shortest distance from 1 to 4.
Solution. BFS from 1: queue [1], visit 1 (dist 0). Enqueue neighbors 2, 3 (dist 1). Dequeue 2, enqueue its unvisited neighbor 4 (dist 2). Dequeue 3 (4 already queued). Dequeue 4. Visiting order: 1, 2, 3, 4. Since 4 was first reached at distance 2 via 1 -> 2 -> 4, the shortest distance from 1 to 4 is 2.
Eulerian paths use every edge once; Hamiltonian paths visit every vertex once.
An Eulerian path traverses every edge exactly once; an Eulerian circuit does so and returns to start. A connected graph has an Eulerian circuit if and only if every vertex has even degree, and an Eulerian path (not circuit) if and only if exactly two vertices have odd degree — these conditions are checkable in O(n) time. A Hamiltonian path visits every vertex exactly once; deciding whether one exists is NP-complete, with no known efficient general test. The contrast is striking: Euler's edge condition is easy, Hamilton's vertex condition is hard. These power route planning (the Konigsberg bridges, mail delivery) and the traveling-salesman problem.
Worked Example 1
Problem. Does the graph with edges {A-B, B-C, C-A} (a triangle) have an Eulerian circuit?
Answer. Yes — all degrees are even, so an Eulerian circuit exists (e.g., A-B-C-A).
Worked Example 2
Problem. A path graph A-B-C-D: does it have an Eulerian path? An Eulerian circuit?
Answer. It has an Eulerian path (A to D) but no Eulerian circuit.
Problem. A graph has degrees 4, 4, 3, 3, 2. Does it have an Eulerian circuit, an Eulerian path, or neither (assume connected)?
Solution. Count odd-degree vertices: degrees 3 and 3 are odd, the rest (4,4,2) are even -> exactly two odd-degree vertices. With zero odd vertices you would get a circuit; with exactly two you get an Eulerian path but not a circuit. Therefore: an Eulerian path exists (starting and ending at the two odd-degree vertices), but no Eulerian circuit.
Coloring assigns colors so adjacent vertices differ; bipartite graphs are exactly the 2-colorable ones.
A proper graph coloring assigns a color to each vertex so that no edge joins two vertices of the same color; the chromatic number is the fewest colors needed. A graph is bipartite if its vertices split into two sets with edges only between the sets — equivalently, it is 2-colorable, equivalently it contains no odd-length cycle. You can test bipartiteness with a BFS/DFS that 2-colors vertices and checks for conflicts. Coloring models scheduling (exam timetables where conflicts cannot share a slot), register allocation in compilers, and frequency assignment. General k-coloring is NP-hard, but 2-coloring (bipartiteness) is solvable in linear time.
Worked Example 1
Problem. Is the cycle on 4 vertices (square A-B-C-D-A) bipartite?
Answer. Yes — it is bipartite (2-colorable), parts {A,C} and {B,D}.
Worked Example 2
Problem. Is the triangle A-B-C (cycle of length 3) bipartite? What is its chromatic number?
Answer. Not bipartite (it has an odd cycle); chromatic number is 3.
Problem. Determine whether the cycle on 5 vertices (A-B-C-D-E-A) is bipartite, and give its chromatic number.
Solution. Attempt a 2-coloring around the cycle: A=red, B=blue, C=red, D=blue, E=red. But E is adjacent to A, and both are red — a conflict. The cycle has length 5, which is odd, so it is NOT bipartite. An odd cycle requires 3 colors (e.g., A=red, B=blue, C=red, D=blue, E=green works), so the chromatic number is 3. Answer: not bipartite; chromatic number 3.
Implement a graph in Python using an adjacency-list dictionary. Add functions to compute each vertex's degree and verify the handshake lemma. Then implement breadth-first search (using a queue) and depth-first search (using recursion or a stack), and use BFS to find the shortest path between two vertices in an unweighted graph. Test connectivity by checking whether a traversal reaches every vertex.
Deliverable · A script with an adjacency-list graph, working BFS and DFS, a shortest-path result, and a connectivity check on at least two example graphs.
1. In any graph, the sum of all vertex degrees equals:
Answer C. Each edge contributes to the degree of two vertices, so the degree sum is twice the number of edges (the handshake lemma).
2. A tree with n vertices has exactly how many edges?
Answer B. A tree is connected and acyclic, which forces exactly n-1 edges; adding any edge creates a cycle.
3. Which traversal naturally finds the shortest path (in edges) in an unweighted graph?
Answer B. BFS explores vertices in order of increasing distance from the source, so the first time it reaches a vertex is via a shortest path.
4. A graph has an Eulerian circuit if and only if it is connected and:
Answer A. An Eulerian circuit traverses every edge once and returns to start; this is possible exactly when the graph is connected and every vertex has even degree.
5. A graph is bipartite if and only if it:
Answer B. A graph is bipartite exactly when it has no cycle of odd length, which is equivalent to being 2-colorable.
I can represent a graph as an adjacency matrix or list and compute vertex degrees.
I can implement breadth-first and depth-first search and use them to test connectivity.
I can recognize trees, bipartite graphs, and Eulerian or Hamiltonian paths.
Primes are the multiplicative atoms of the integers; every integer factors uniquely into primes.
We say a divides b (written a | b) when b = a*k for some integer k. A prime is an integer greater than 1 whose only positive divisors are 1 and itself; all other integers above 1 are composite. The fundamental theorem of arithmetic guarantees that every integer greater than 1 has a unique prime factorization, up to the order of factors — this uniqueness is why primes are the building blocks of number theory. Factorization underlies cryptography, the structure of GCD/LCM, and hashing. In Python you can test divisibility with the modulo operator (b % a == 0) and factor by trial division up to the square root of n, since any composite has a factor at or below sqrt(n).
Worked Example 1
Problem. Find the prime factorization of 84.
Answer. 84 = 2^2 * 3 * 7.
Worked Example 2
Problem. Is 91 prime? Justify with trial division.
Answer. 91 is not prime; 91 = 7 * 13.
Problem. Find the prime factorization of 360 and state how many distinct prime factors it has.
Solution. Divide out 2s: 360/2=180, 180/2=90, 90/2=45 (three 2s). 45 is odd; divide by 3: 45/3=15, 15/3=5 (two 3s). 5 is prime. So 360 = 2^3 * 3^2 * 5. The distinct primes are 2, 3, and 5 -> 3 distinct prime factors. Answer: 360 = 2^3 * 3^2 * 5, with 3 distinct prime factors.
The Euclidean algorithm finds the GCD by repeated remainder, far faster than factoring.
The greatest common divisor (GCD) of two integers is the largest integer dividing both. The Euclidean algorithm computes it using the key fact that GCD(a, b) = GCD(b, a mod b), repeatedly replacing the pair until the remainder is 0; the last nonzero remainder is the GCD. It runs in O(log(min(a,b))) steps — exponentially faster than factoring both numbers. GCD is foundational for reducing fractions, finding modular inverses, and cryptographic key math. The related LCM satisfies LCM(a,b) = a*b / GCD(a,b). In Python the algorithm is a short loop, and math.gcd does it built in.
Worked Example 1
Problem. Compute GCD(48, 18) with the Euclidean algorithm.
Answer. GCD(48, 18) = 6.
Worked Example 2
Problem. Find GCD(1071, 462) and then LCM(1071, 462).
Answer. GCD = 21, LCM = 23562.
Problem. Use the Euclidean algorithm to find GCD(252, 105), then reduce the fraction 252/105.
Solution. 252 mod 105 = 42; 105 mod 42 = 21; 42 mod 21 = 0. The last nonzero remainder is 21, so GCD(252,105) = 21. Reduce the fraction by dividing both by 21: 252/21 = 12 and 105/21 = 5, giving 12/5. In Python: math.gcd(252,105) = 21. Answer: GCD = 21; 252/105 reduces to 12/5.
Modular arithmetic 'wraps around' at a modulus; congruence means two numbers leave the same remainder.
In modular arithmetic we work with remainders after dividing by a modulus n. We write a is congruent to b mod n when n divides (a - b) — equivalently, a and b leave the same remainder mod n. Addition, subtraction, and multiplication all respect congruence: you may reduce mod n at any point. This is the math of clocks (12-hour wrap), checksums, cyclic buffers, and hash tables. A powerful tool is fast modular exponentiation: to compute a^b mod n efficiently, square and reduce repeatedly. In Python, the % operator gives nonnegative remainders for positive n, and pow(a, b, n) computes modular powers efficiently.
Worked Example 1
Problem. Compute (17 + 25) mod 12 and (17 * 25) mod 12.
Answer. (17 + 25) mod 12 = 6; (17 * 25) mod 12 = 5.
Worked Example 2
Problem. Is 38 congruent to 14 mod 8?
Answer. Yes — both leave remainder 6, so 38 is congruent to 14 mod 8.
Worked Example 3
Problem. Compute 3^200 mod 7 using fast modular exponentiation.
Answer. 3^200 mod 7 = 2.
Problem. Compute 7^100 mod 5.
Solution. Reduce the base: 7 mod 5 = 2, so 7^100 is congruent to 2^100 mod 5. Powers of 2 mod 5 cycle: 2^1=2, 2^2=4, 2^3=3, 2^4=1 (cycle length 4). Since 100 mod 4 = 0, 2^100 is congruent to 2^4 = 1 mod 5. In Python: pow(7, 100, 5) = 1. Answer: 1.
A modular inverse undoes multiplication mod n; it exists exactly when the number is coprime to n.
The modular inverse of a mod n is an integer x with a*x congruent to 1 mod n. It plays the role of division in modular arithmetic. The inverse exists if and only if GCD(a, n) = 1 (a and n are coprime), and it is found with the extended Euclidean algorithm, which expresses GCD(a,n) = a*x + n*y; then x mod n is the inverse. Inverses solve linear congruences a*x congruent to b mod n and are central to RSA decryption and hashing. In Python 3.8+, pow(a, -1, n) returns the modular inverse directly when it exists, raising an error otherwise.
Worked Example 1
Problem. Find the inverse of 3 mod 7.
Answer. The inverse of 3 mod 7 is 5.
Worked Example 2
Problem. Solve the linear congruence 4x congruent to 5 mod 9.
Answer. x congruent to 8 mod 9.
Problem. Find the inverse of 5 mod 11, then solve 5x congruent to 3 mod 11.
Solution. GCD(5,11)=1, so the inverse exists. Find x with 5x congruent to 1 mod 11: 5*9 = 45 = 44 + 1, and 45 mod 11 = 1, so the inverse of 5 is 9. To solve 5x congruent to 3, multiply both sides by 9: x congruent to 9*3 = 27 mod 11 = 5. In Python: pow(5,-1,11) = 9 and (9*3) % 11 = 5. Answer: inverse is 9; x congruent to 5 mod 11.
These theorems give shortcuts for exponents in modular arithmetic, powering fast computation and crypto.
Fermat's little theorem states that if p is prime and a is not divisible by p, then a^(p-1) is congruent to 1 mod p. Euler's theorem generalizes it: if GCD(a, n) = 1 then a^phi(n) is congruent to 1 mod n, where phi(n) (Euler's totient) counts integers in [1, n] coprime to n. These let you reduce huge exponents modulo p-1 (or phi(n)) before computing, and they give a quick way to find modular inverses: a^(p-2) is the inverse of a mod a prime p. They are the mathematical engine behind RSA, where decryption exponents are chosen using phi(n). In Python, pow(a, p-1, p) demonstrates the theorem.
Worked Example 1
Problem. Use Fermat's little theorem to compute 2^100 mod 7.
Answer. 2^100 mod 7 = 2.
Worked Example 2
Problem. Find the inverse of 4 mod 7 using Fermat's little theorem.
Answer. The inverse of 4 mod 7 is 2.
Worked Example 3
Problem. Use Euler's theorem with n = 10 (phi(10) = 4) to compute 3^22 mod 10.
Answer. 3^22 mod 10 = 9.
Problem. Compute 5^123 mod 11 using Fermat's little theorem.
Solution. 11 is prime and 5 is not divisible by 11, so by Fermat 5^10 is congruent to 1 mod 11. Reduce the exponent mod 10: 123 mod 10 = 3, so 5^123 is congruent to 5^3 mod 11. Compute 5^3 = 125, and 125 mod 11 = 125 - 121 = 4. In Python: pow(5, 123, 11) = 4. Answer: 4.
Hash functions use a modulus to map data into a fixed range of buckets, ideally spreading inputs evenly.
A hash function maps arbitrary data to a fixed range of integers, typically by computing a numeric value and reducing it mod m (the table size). Good hashing spreads inputs uniformly across buckets to keep lookups fast (near O(1) on average); poor hashing clusters inputs, causing collisions that degrade to O(n). Choosing m to be prime helps avoid patterns when keys share common factors. A classic string hash (polynomial rolling hash) treats characters as digits in some base and reduces mod a prime. This is the backbone of Python dicts and sets, caches, and bloom filters. You can measure quality by counting how many keys land in each bucket and checking the spread.
Worked Example 1
Problem. Hash the integers 0..9 into 7 buckets with h(k) = k mod 7. Which bucket gets two keys?
Answer. Buckets 0, 1, and 2 each get two keys.
Worked Example 2
Problem. Compute a polynomial rolling hash of 'cat' with base 31 mod 101 (a=0,...,z=25, so c=2, a=0, t=19).
Answer. The hash of 'cat' is 22.
Problem. Using h(k) = k mod 5, hash the keys 12, 25, 7, 5, 19 and report the bucket of each and any collisions.
Solution. Compute each mod 5: 12 mod 5 = 2; 25 mod 5 = 0; 7 mod 5 = 2; 5 mod 5 = 0; 19 mod 5 = 4. Buckets: bucket 0 holds {25, 5}, bucket 2 holds {12, 7}, bucket 4 holds {19}. Collisions occur in bucket 0 (25 and 5) and bucket 2 (12 and 7). In Python: Counter(k % 5 for k in [12,25,7,5,19]) shows counts {2:2, 0:2, 4:1}. Answer: 12->2, 25->0, 7->2, 5->0, 19->4; collisions in buckets 0 and 2.
RSA uses the ease of multiplying primes versus the hardness of factoring their product to enable public-key encryption.
RSA is a public-key cryptosystem. You pick two large primes p and q, compute n = p*q and phi(n) = (p-1)(q-1). Choose a public exponent e coprime to phi(n), and compute the private exponent d as the modular inverse of e mod phi(n). The public key is (n, e); the private key is (n, d). Encryption of a message m is c = m^e mod n; decryption is m = c^d mod n, which works because e*d is congruent to 1 mod phi(n) and Euler's theorem makes m^(ed) return m. Security rests on the fact that recovering p and q by factoring n is computationally infeasible for large n, even though multiplying them is easy. This asymmetry is what makes secure key exchange and digital signatures possible.
Worked Example 1
Problem. Build a toy RSA key with p = 3, q = 11, e = 7. Find n, phi(n), and d.
Answer. n = 33, phi(n) = 20, d = 3 (public key (33,7), private key (33,3)).
Worked Example 2
Problem. Using the toy key above, encrypt m = 4 and decrypt the result to confirm.
Answer. Encryption gives c = 16; decryption returns m = 4, confirming the keys work.
Problem. With p = 5, q = 11, e = 3, compute n, phi(n), and the private exponent d.
Solution. n = p*q = 55. phi(n) = (5-1)(11-1) = 4 * 10 = 40. Check GCD(3, 40) = 1, so e = 3 is valid. The private exponent d is the inverse of 3 mod 40: we need 3d congruent to 1 mod 40. Testing, 3*27 = 81 = 80 + 1, and 81 mod 40 = 1, so d = 27. In Python: pow(3, -1, 40) = 27. Answer: n = 55, phi(n) = 40, d = 27.
In Python, implement the Euclidean algorithm for GCD and extend it to find modular inverses (the extended Euclidean algorithm). Implement fast modular exponentiation using Python's pow(base, exp, mod) and verify Fermat's little theorem on several primes. Finally, build a tiny hash function that maps strings to buckets via a modulus, and measure how evenly it distributes a list of inputs.
Deliverable · A script demonstrating GCD, a modular inverse, a Fermat's-little-theorem check, and a histogram of hash-bucket counts.
1. What is GCD(48, 18) by the Euclidean algorithm?
Answer B. 48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, so the GCD is 6.
2. What is 17 mod 5?
Answer B. 17 = 3*5 + 2, so the remainder, 17 mod 5, is 2.
3. A modular inverse of a modulo n exists if and only if:
Answer C. a has a multiplicative inverse mod n exactly when a and n are coprime, that is GCD(a, n) = 1.
4. By Fermat's little theorem, for a prime p and a not divisible by p, a^(p-1) mod p equals:
Answer B. Fermat's little theorem states a^(p-1) is congruent to 1 mod p whenever p is prime and a is not a multiple of p.
5. The security of RSA rests primarily on the difficulty of:
Answer B. RSA is secure because, while multiplying two large primes is easy, recovering those primes by factoring their product is computationally hard.
I can find a GCD with the Euclidean algorithm and factor integers into primes.
I can compute with congruences and find modular inverses.
I can explain how modular arithmetic underlies hashing and the intuition behind RSA.
A recurrence defines each term of a sequence from earlier terms plus base cases.
A sequence is an ordered list of numbers; a recurrence relation defines each term using earlier terms together with one or more base cases. For example, the factorial f(n) = n * f(n-1) with f(0) = 1, or Fibonacci F(n) = F(n-1) + F(n-2) with F(0)=0, F(1)=1. Recurrences are the natural language of recursive algorithms: the work an algorithm does is often expressed as a recurrence in its input size. Understanding them lets you predict how recursive code behaves and convert it into iterative or memoized form. In Python, a recurrence translates directly into a recursive function (with base cases) or an iterative loop that builds up values from the base.
Worked Example 1
Problem. Given a(1) = 2 and a(n) = a(n-1) + 3, compute a(1) through a(5).
Answer. 2, 5, 8, 11, 14.
Worked Example 2
Problem. The Fibonacci recurrence is F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1. Find F(6).
Answer. F(6) = 8.
Problem. A sequence has T(1) = 1 and T(n) = 2*T(n-1) + 1. Compute T(1) through T(5).
Solution. T(1) = 1 (base). T(2) = 2*1 + 1 = 3. T(3) = 2*3 + 1 = 7. T(4) = 2*7 + 1 = 15. T(5) = 2*15 + 1 = 31. The pattern is T(n) = 2^n - 1. In Python: t=1; for _ in range(4): t = 2*t + 1 ends at 31. Answer: 1, 3, 7, 15, 31.
Linear recurrences with constant coefficients have closed-form solutions found via the characteristic equation.
A linear homogeneous recurrence with constant coefficients, like a(n) = c1*a(n-1) + c2*a(n-2), can be solved in closed form. Guess a(n) = r^n, substitute, and divide to get the characteristic equation r^2 = c1*r + c2. Its roots r1, r2 give the general solution a(n) = A*r1^n + B*r2^n, with A, B fixed by the base cases. For Fibonacci the roots are the golden ratio phi and its conjugate, giving Binet's formula. Closed forms let you compute the n-th term in O(1) (up to precision) and reveal the growth rate. In Python you can verify a closed form against the iterative sequence for small n.
Worked Example 1
Problem. Solve a(n) = 5a(n-1) - 6a(n-2) with a(0)=0, a(1)=1.
Answer. a(n) = 3^n - 2^n (check: a(2) = 9 - 4 = 5, and 5*1 - 6*0 = 5).
Worked Example 2
Problem. Write the characteristic equation for Fibonacci F(n) = F(n-1) + F(n-2) and give its roots.
Answer. Characteristic equation r^2 - r - 1 = 0 with roots (1 +/- sqrt(5))/2.
Problem. Solve a(n) = 3a(n-1) - 2a(n-2) with a(0) = 2, a(1) = 3.
Solution. Characteristic equation: r^2 - 3r + 2 = 0, factoring (r-1)(r-2) = 0, roots 1 and 2. General solution a(n) = A*1^n + B*2^n = A + B*2^n. Apply bases: a(0) = A + B = 2; a(1) = A + 2B = 3. Subtract: B = 1, so A = 1. Closed form a(n) = 1 + 2^n. Check a(2) = 1 + 4 = 5, and 3*3 - 2*2 = 5. Answer: a(n) = 1 + 2^n.
Substitution guesses a bound and proves it by induction; iteration unrolls the recurrence to spot a pattern.
Two general techniques solve recurrences when the characteristic method does not apply. The iteration (or unrolling) method repeatedly expands the recurrence, substituting the definition into itself until a summation pattern emerges, then sums it. The substitution method guesses a closed-form bound (often from intuition or unrolling) and proves it correct by induction, verifying the guess satisfies the recurrence. Both are essential for analyzing algorithm running times where the recurrence does not fit a neat formula. In CS these handle the cost recurrences of recursive algorithms; the answer feeds directly into Big-O analysis. A short Python check on small n can validate a guessed bound before you prove it.
Worked Example 1
Problem. Solve T(n) = T(n-1) + n with T(0) = 0 by iteration.
Answer. T(n) = n(n+1)/2, i.e. Theta(n^2).
Worked Example 2
Problem. Solve T(n) = 2T(n/2) + n by iteration (n a power of 2, T(1)=1).
Answer. T(n) = n log2(n) + n = Theta(n log n).
Problem. Solve T(n) = T(n-1) + 1 with T(0) = 0 by iteration, and give its Big-O.
Solution. Unroll: T(n) = T(n-1) + 1 = T(n-2) + 1 + 1 = ... = T(0) + n*1 = 0 + n = n. Each level adds a constant 1 and there are n levels down to the base. So T(n) = n, which is Theta(n) (linear). A Python loop adding 1 n times confirms T(n) = n. Answer: T(n) = n = O(n).
The Master Theorem instantly solves recurrences of the form T(n) = a T(n/b) + f(n).
Divide-and-conquer algorithms split a problem of size n into a subproblems of size n/b and combine in f(n) work, giving T(n) = a T(n/b) + f(n). The Master Theorem compares f(n) to n^(log_b a): Case 1, if f(n) grows slower (f = O(n^(log_b a - e))), then T(n) = Theta(n^(log_b a)); Case 2, if they match (f = Theta(n^(log_b a))), then T(n) = Theta(n^(log_b a) * log n); Case 3, if f grows faster (with a regularity condition), then T(n) = Theta(f(n)). This single theorem analyzes merge sort, binary search, and many recursive algorithms without unrolling. The key first step is computing the critical exponent log_b a.
Worked Example 1
Problem. Solve T(n) = 2T(n/2) + n (merge sort) with the Master Theorem.
Answer. T(n) = Theta(n log n).
Worked Example 2
Problem. Solve T(n) = T(n/2) + 1 (binary search).
Answer. T(n) = Theta(log n).
Worked Example 3
Problem. Solve T(n) = 4T(n/2) + n.
Answer. T(n) = Theta(n^2).
Problem. Use the Master Theorem to solve T(n) = 3T(n/2) + n.
Solution. Here a = 3, b = 2, f(n) = n. The critical exponent is log_b a = log2(3) ~ 1.585, so n^(log_b a) = n^1.585. Compare f(n) = n^1 to n^1.585: f grows strictly slower (n = O(n^(1.585 - e))), which is Case 1. Therefore T(n) = Theta(n^(log2 3)) ~ Theta(n^1.585). (This is the recurrence behind Karatsuba multiplication.) Answer: T(n) = Theta(n^(log2 3)).
Asymptotic notation describes how a function grows for large inputs, ignoring constants and lower-order terms.
Asymptotic notation classifies growth rates as input size n grows large. Big-O gives an upper bound: f(n) = O(g(n)) means f grows no faster than a constant multiple of g for large n. Big-Omega gives a lower bound: f grows at least as fast as g. Big-Theta is a tight bound: f is both O(g) and Omega(g), so they grow at the same rate. We drop constant factors and lower-order terms because they do not affect large-n behavior — 3n^2 + 5n + 7 is Theta(n^2). This vocabulary lets us compare algorithms independently of hardware. The standard hierarchy is O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!).
Worked Example 1
Problem. Give the tightest Big-Theta bound for f(n) = 3n^2 + 100n + 50.
Answer. f(n) = Theta(n^2).
Worked Example 2
Problem. Is 2^(n+1) = O(2^n)?
Answer. Yes — 2^(n+1) = 2 * 2^n = O(2^n).
Worked Example 3
Problem. Order these by growth: n!, n^2, log n, 2^n, n log n.
Answer. log n < n log n < n^2 < 2^n < n!.
Problem. Give the tightest Big-Theta bound for f(n) = 5n^3 + 2n^2 log n + 1000, and state whether f(n) = O(n^4).
Solution. The dominant term is 5n^3 (it grows faster than 2n^2 log n and the constant 1000). Dropping the constant factor and lower-order terms gives f(n) = Theta(n^3). Since n^3 grows slower than n^4, f(n) is also O(n^4) (a valid but loose upper bound). Answer: f(n) = Theta(n^3); and yes, f(n) = O(n^4).
Counting the dominant operations as a function of input size yields an algorithm's time complexity.
To analyze an algorithm, count how many basic operations it performs as a function of input size n, then express that count in asymptotic notation. A single loop over n elements is O(n); nested loops over n are O(n^2); halving the problem each step is O(log n); a recursive divide-and-conquer is analyzed with the Master Theorem. We focus on the worst case (or average case) and the dominant term. This guides algorithm choice: an O(n log n) sort beats an O(n^2) one decisively for large data. In Python, you can confirm an analysis empirically by timing the code on growing inputs and checking the curve matches the predicted growth.
Worked Example 1
Problem. What is the time complexity of a doubly nested loop that runs j from 0 to n for each i from 0 to n?
Answer. Theta(n^2).
Worked Example 2
Problem. Analyze: a loop where i starts at n and is halved each iteration until it reaches 1.
Answer. Theta(log n).
Worked Example 3
Problem. What is the worst-case complexity of linear search through n items, and of accessing a list by index?
Answer. Linear search is O(n); list indexing is O(1).
Problem. An algorithm has an outer loop running n times; inside it, an inner loop runs from the current i up to n. What is the time complexity?
Solution. For outer index i, the inner loop runs about (n - i) times. Total operations = sum over i from 0 to n-1 of (n - i) = n + (n-1) + ... + 1 = n(n+1)/2. Dropping the constant 1/2 and lower-order term, this is Theta(n^2). (Even though the inner loop shrinks, the total is still quadratic.) Answer: Theta(n^2).
Timing algorithms on growing inputs lets you observe Big-O classes in practice and confirm theory.
Theory predicts asymptotic growth, but timing real code validates it and exposes constant factors that matter at practical sizes. The approach: run an algorithm on inputs of increasing size n, record the running time, and plot or tabulate time against n. An O(n) algorithm's time roughly doubles when n doubles; an O(n^2) algorithm's time roughly quadruples; an O(log n) algorithm barely changes. Comparing the empirical curve to the predicted shape confirms the analysis (or reveals a bug or a large hidden constant). In Python, time.perf_counter measures elapsed time and matplotlib (optional) plots the curves. The ratio of times at successive sizes is the most reliable diagnostic.
Worked Example 1
Problem. An O(n) routine takes 10 ms at n = 1000. Predict its time at n = 4000.
Answer. About 40 ms (4x the input gives 4x the time).
Worked Example 2
Problem. An O(n^2) routine takes 2 s at n = 1000. Predict its time at n = 3000.
Answer. About 18 s (tripling n multiplies time by 9).
Problem. An algorithm you suspect is O(n log n) takes 1.0 s at n = 1,000,000. Estimate its time at n = 2,000,000.
Solution. For O(n log n), doubling n multiplies the time by a factor of (2n log(2n)) / (n log n) = 2 * (log(2n)/log n). With n = 1,000,000, log2(n) ~ 20 and log2(2n) ~ 21, so the factor is about 2 * (21/20) = 2.1. Predicted time ~ 1.0 s * 2.1 = 2.1 s. (Just over double, because the log factor grows slightly.) Answer: roughly 2.1 seconds.
Pick two algorithms with different complexities (for example, linear search at O(n) and binary search at O(log n), or a naive recursive Fibonacci vs. an iterative one). In Python, time each algorithm on inputs of growing size and plot running time against n. Compare the empirical curves to the Big-O predictions. For the recursive Fibonacci, write its recurrence and explain why its running time is exponential.
Deliverable · A script with timing data, a plot of running time vs. input size, and a short note connecting each curve to its Big-O class.
1. Which growth rate is fastest (largest) as n grows large?
Answer D. For large n the ordering is log n < n < n log n < n^2, so O(n^2) grows the fastest of these four.
2. Binary search on a sorted array of n elements has time complexity:
Answer B. Binary search halves the search range each step, so it runs in O(log n) time.
3. Saying f(n) is Theta(g(n)) means:
Answer B. Big-Theta is a tight bound: f is both O(g) and Omega(g), so the two functions grow at the same rate up to constants.
4. For the divide-and-conquer recurrence T(n) = 2 T(n/2) + O(n), the solution is:
Answer B. By the Master Theorem this is the balanced case (like merge sort), giving T(n) = O(n log n).
5. Why is the naive recursive Fibonacci so slow?
Answer B. The two recursive calls overlap heavily, recomputing the same values, which makes the running time grow exponentially with n.
I can set up and solve recurrence relations, including divide-and-conquer ones.
I can classify a function's growth using Big-O, Big-Omega, and Big-Theta.
I can analyze an algorithm's running time and confirm it empirically in Python.
Boolean algebra works over the values 0 and 1 with AND, OR, NOT, governed by identities like De Morgan's laws.
Boolean algebra is the algebra of two values, 0 (false) and 1 (true), with operations AND (multiply-like), OR (add-like), and NOT (complement). It obeys identities that let you simplify expressions: identity (A AND 1 = A, A OR 0 = A), domination (A OR 1 = 1, A AND 0 = 0), idempotence (A AND A = A), complement (A AND NOT A = 0), distributivity, absorption (A OR (A AND B) = A), and De Morgan's laws (NOT(A AND B) = NOT A OR NOT B). These laws are the basis for optimizing digital circuits and simplifying conditional logic in code. In Python the operations map to and, or, not on booleans, so you can verify any identity by exhaustive truth-table comparison.
Worked Example 1
Problem. Simplify A AND (A OR B) using Boolean identities.
Answer. A AND (A OR B) = A.
Worked Example 2
Problem. Use De Morgan's law to rewrite NOT(A OR B) and verify by truth table.
Answer. NOT(A OR B) = NOT A AND NOT B (both give 0,0,0,1).
Worked Example 3
Problem. Simplify (A AND B) OR (A AND NOT B).
Answer. (A AND B) OR (A AND NOT B) = A.
Problem. Simplify the Boolean expression (A OR B) AND (A OR NOT B).
Solution. Apply the distributive law (treating OR as the outer operation): (A OR B) AND (A OR NOT B) = A OR (B AND NOT B). Since B AND NOT B = 0 (complement law), this becomes A OR 0 = A. Verify in Python: all(((a or b) and (a or (not b))) == a for a in (0,1) for b in (0,1)) returns True. Answer: A.
A Boolean function maps binary inputs to a binary output and is fully specified by its truth table.
A Boolean function takes n binary inputs and produces one binary output; it is completely described by a truth table listing the output for all 2^n input combinations. Because there are 2^n rows and each can be 0 or 1, there are 2^(2^n) distinct Boolean functions of n variables. Any function can be built from AND, OR, NOT (a functionally complete set), and in fact from NAND alone. Boolean functions model every digital logic block and every Boolean condition in code. In Python, you can represent a function as a lambda over booleans and generate its truth table with itertools.product over (0,1) tuples, which is the basis for verification and simplification.
Worked Example 1
Problem. Write the truth table for the XOR function f(A,B) = A XOR B.
Answer. XOR truth table outputs: 0, 1, 1, 0 (1 exactly when A != B).
Worked Example 2
Problem. How many distinct Boolean functions of 2 variables exist?
Answer. 16 distinct Boolean functions of 2 variables.
Worked Example 3
Problem. Express the majority function of A, B, C (output 1 when at least two inputs are 1) and check the row A=1,B=1,C=0.
Answer. Majority(A,B,C) = (A AND B) OR (A AND C) OR (B AND C); for (1,1,0) it is 1.
Problem. Write the truth table for f(A,B) = (NOT A) OR B and identify which familiar operation it equals.
Solution. Evaluate all rows. (A,B)=(0,0): (not 0) or 0 = 1 or 0 = 1. (0,1): 1 or 1 = 1. (1,0): 0 or 0 = 0. (1,1): 0 or 1 = 1. Outputs: 1, 1, 0, 1. This is 0 exactly when A=1, B=0 — precisely the truth table of the implication A implies B. So (NOT A) OR B equals A implies B. Answer: outputs 1,1,0,1; it is the implication A implies B.
Any Boolean function can be written canonically as an OR of minterms (SOP) or an AND of maxterms (POS).
Every Boolean function has two canonical forms derived directly from its truth table. The sum-of-products (SOP) form is an OR of minterms: one AND term for each row where the output is 1, with each variable appearing true or complemented to match that row. The product-of-sums (POS) form is an AND of maxterms: one OR term for each row where the output is 0. These standard forms give a guaranteed (if not minimal) circuit for any function and are the starting point for simplification. They matter in circuit design and in converting truth tables into logic. In Python you read the SOP straight off the 1-rows of a generated truth table.
Worked Example 1
Problem. Find the SOP form of f(A,B) that is 1 on rows (A=0,B=1) and (A=1,B=1).
Answer. SOP: (NOT A AND B) OR (A AND B), which simplifies to B.
Worked Example 2
Problem. Find the POS form of f(A,B) that is 0 only on row (A=0,B=0).
Answer. POS: (A OR B).
Problem. Give the sum-of-products form for f(A,B) = A XOR B directly from its truth table.
Solution. XOR is 1 on rows where inputs differ: (A=0,B=1) and (A=1,B=0). Build a minterm for each, matching each variable (complement it when its value is 0): row (0,1) -> (NOT A AND B); row (1,0) -> (A AND NOT B). OR them: f = (NOT A AND B) OR (A AND NOT B). This is the canonical SOP for XOR. Answer: (NOT A AND B) OR (A AND NOT B).
Logic gates are hardware that implement Boolean operations; wiring them builds digital circuits.
A logic gate is a physical (or simulated) device implementing a Boolean operation: AND, OR, NOT, plus the derived NAND, NOR, XOR. Connecting gates so that outputs feed inputs builds combinational circuits that compute Boolean functions — adders, multiplexers, comparators. NAND and NOR are each functionally complete: any circuit can be built from NAND alone, which is why hardware favors them. The depth (longest gate path) affects circuit speed, and the gate count affects cost — so simplification matters. This is where Boolean algebra meets real computing. In Python you can simulate a circuit by composing functions for each gate and checking the overall truth table.
Worked Example 1
Problem. Build a half-adder: outputs Sum and Carry for two bits A and B. Give the gate expressions.
Answer. Sum = A XOR B, Carry = A AND B.
Worked Example 2
Problem. Show how to build a NOT gate using only a NAND gate.
Answer. NOT A = NAND(A, A).
Problem. Express an OR gate using only NAND gates.
Solution. By De Morgan, A OR B = NOT(NOT A AND NOT B). First make NOT A = NAND(A,A) and NOT B = NAND(B,B). Then A OR B = NAND(NOT A, NOT B), because NAND(NOT A, NOT B) = NOT((NOT A) AND (NOT B)) = NOT A OR NOT(NOT B)... more directly: NAND(x,y)=NOT(x AND y), so NAND(NOT A, NOT B) = NOT(NOT A AND NOT B) = A OR B. So OR uses three NAND gates: two as inverters plus one combining them. Answer: A OR B = NAND(NAND(A,A), NAND(B,B)).
Simplifying Boolean expressions reduces gate count; Karnaugh maps make minimization visual.
Minimizing a Boolean expression cuts the number of gates and the circuit's cost and delay. You can simplify algebraically with the identities (especially absorption, complement, and distributivity), but it is easy to miss reductions. A Karnaugh map (K-map) lays out the truth table in a grid ordered by Gray code so that adjacent cells differ in exactly one variable. Grouping adjacent 1-cells into rectangles of size a power of two lets each group drop the variable that changes across it, yielding a minimal SOP. K-maps are practical for up to four or so variables. Both techniques start from the same canonical SOP and produce an equivalent but smaller expression, which you can verify equals the original on every input.
Worked Example 1
Problem. Simplify f = (A AND NOT B) OR (A AND B) algebraically.
Answer. f = A.
Worked Example 2
Problem. Use a K-map idea to simplify f(A,B,C) = 1 on minterms where A=1 (i.e. ABC = 100,101,110,111).
Answer. f(A,B,C) = A.
Problem. Simplify f(A,B) = (A AND B) OR (NOT A AND B) OR (A AND NOT B).
Solution. Group the first two terms by factoring B: (A AND B) OR (NOT A AND B) = B AND (A OR NOT A) = B AND 1 = B. So f = B OR (A AND NOT B). Now apply the absorption variant: B OR (A AND NOT B) = B OR A (since the term contributes only when B=0, where it equals A). Verify on all rows: f is 1 unless A=0 and B=0, matching A OR B. Answer: f = A OR B.
A finite state machine has states and labeled transitions that model step-by-step computation.
A finite state machine (FSM) is a discrete structure with a finite set of states, a start state, transitions labeled by input symbols, and (for acceptors) a set of accepting states. At each step the machine reads an input and moves along the transition for that symbol. FSMs recognize regular languages and model lexical scanners, network protocols, vending machines, and UI flows. They are essentially labeled directed graphs, tying this unit back to graph theory. You can represent an FSM in Python as a dictionary mapping (state, symbol) to the next state, then process an input string by following transitions from the start state and checking whether it ends in an accepting state.
Worked Example 1
Problem. Design an FSM that accepts binary strings ending in 1. Give states and transitions, then test '101' and '110'.
Answer. '101' ends in S1 -> accepted; '110' ends in S0 -> rejected.
Worked Example 2
Problem. Model a turnstile FSM with states Locked and Unlocked; inputs 'push' and 'coin'. Describe the transitions.
Answer. Locked --coin--> Unlocked --push--> Locked, with self-loops for push-on-Locked and coin-on-Unlocked.
Problem. Design an FSM that accepts binary strings containing an even number of 1s, and test the string '1101'.
Solution. Use two states tracking parity of 1s: Even (accepting, start) and Odd (non-accepting). Transitions: on 0 stay in the same state; on 1 flip Even<->Odd. Run '1101' from Even: read 1 -> Odd; read 1 -> Even; read 0 -> Even; read 1 -> Odd. It ends in Odd (non-accepting), so '1101' is rejected — correct, since it has three 1s (odd). In Python: state='Even'; for c in '1101': if c=='1': state = 'Odd' if state=='Even' else 'Even'. Answer: '1101' is rejected (odd number of 1s).
Boolean algebra, set algebra, and propositional logic are three faces of the same algebraic structure.
Boolean algebra, the algebra of sets, and propositional logic share the same laws because they are all instances of an abstract Boolean algebra. The correspondence: AND matches set intersection matches logical conjunction; OR matches set union matches disjunction; NOT matches set complement matches negation; 1 matches the universal set matches True; 0 matches the empty set matches False. Every identity transfers across all three — De Morgan's laws, distributivity, and absorption hold identically. Recognizing this unity means a proof or simplification in one domain instantly gives results in the others, and it explains why the same reasoning powers circuit design, database queries, and logical proofs. It is the unifying capstone of discrete structures.
Worked Example 1
Problem. Translate De Morgan's law across all three domains.
Answer. All three express the same De Morgan identity, swapping AND/intersect/conjunction with OR/union/disjunction under negation.
Worked Example 2
Problem. Show the distributive law in set form mirrors Boolean distributivity.
Answer. The set identity X ∩ (Y ∪ Z) = (X ∩ Y) ∪ (X ∩ Z) is the same law as Boolean distributivity.
Problem. State the absorption law A OR (A AND B) = A in set notation and verify it with X = {1,2,3} and Y = {2,3,4,5}.
Solution. In set form, absorption is X ∪ (X ∩ Y) = X. Compute with X = {1,2,3}, Y = {2,3,4,5}: X ∩ Y = {2,3}; then X ∪ {2,3} = {1,2,3} ∪ {2,3} = {1,2,3} = X. The result equals X, confirming the law. This mirrors the Boolean identity A OR (A AND B) = A and the logical p OR (p AND q) = p. Answer: X ∪ (X ∩ Y) = X = {1,2,3}, verified.
Choose a Boolean function of three variables and write out its full truth table in Python. From the truth table, derive its sum-of-products canonical form. Then implement the function two ways (the unsimplified SOP and a hand-simplified version using Boolean identities) and verify in code that they produce identical outputs for all 8 input combinations. Explain which Boolean laws justified your simplification.
Deliverable · A script printing the truth table, the SOP form, both implementations, and a confirmation that they match on every input.
1. By De Morgan's law, NOT(A AND B) is equivalent to:
Answer B. De Morgan's law turns the negation of an AND into an OR of the negations: NOT(A AND B) = NOT A OR NOT B.
2. In Boolean algebra, what does A OR (A AND B) simplify to?
Answer A. By the absorption law, A OR (A AND B) = A, since whenever A is true the whole expression is true regardless of B.
3. A sum-of-products (SOP) expression is structured as:
Answer B. SOP form is an OR (the 'sum') of AND terms (the 'products'), each AND term being a minterm of the function.
4. How many rows does the truth table of a 3-variable Boolean function have?
Answer C. Each of the 3 variables has 2 possible values, giving 2^3 = 8 distinct input combinations.
5. A Karnaugh map is used to:
Answer B. A Karnaugh map arranges minterms so that adjacent cells differ by one variable, letting you group them to simplify the expression.
I can manipulate Boolean expressions using the standard identities and De Morgan's laws.
I can express a Boolean function in canonical form and simplify it.
I can connect Boolean algebra to logic, set theory, and simple digital circuits.
Where this leads
Part of the open-source Crunch Academy tech-education path. Pair it with the data-science and ML tracks when you're ready.
All Math for Data Science courses Crunch Academy home