Concepts106
Tree Isomorphism
Tree isomorphism asks whether two trees have exactly the same shape, ignoring vertex names.
Harmonic Lemma
The Harmonic Lemma says that the values of \lfloor n/i \rfloor only change about 2\sqrt{n} times, so you can iterate those value blocks in O(\sqrt{n}) instead of O(n).
Game Theory - Nim
Nim is a two-player impartial game with several piles where a move removes any positive number of stones from exactly one pile.
Game Theory - Calculation Techniques
Sprague–Grundy theory converts any impartial, normal-play game into an equivalent Nim heap using a Grundy number.
Linearity of Expectation Applications
Linearity of expectation says the expected value of a sum equals the sum of expected values, even if the variables are dependent.
Expected Value
Expected value is the long-run average outcome of a random variable if you could repeat the experiment many times.
Bayes' Theorem
Bayes' Theorem tells you how to update the probability of a hypothesis after seeing new evidence.
Lucas' Theorem
Lucas' Theorem lets you compute C(n, k) modulo a prime p by working digit-by-digit in base p.
Inclusion-Exclusion Principle
The Inclusion-Exclusion Principle (IEP) corrects overcounting by alternately adding and subtracting sizes of intersections of sets.
Linear Diophantine Equations
A linear Diophantine equation ax + by = c has integer solutions if and only if gcd(a, b) divides c.
Binomial Theorem and Identities
The binomial theorem expands (x + y)^n into a sum of terms using binomial coefficients that count how many ways to choose k items from n.
Miller-Rabin Primality Test
Miller–Rabin is a fast primality test that uses modular exponentiation to detect compositeness with very high reliability.