Concepts105
Category
VC Dimension
VC dimension measures how many distinct labelings a hypothesis class can realize on any set of points of a given size.
Rademacher Complexity
Rademacher complexity is a data-dependent measure of how well a function class can fit random noise on a given sample.
Measure Theory
Measure theory generalizes length, area, and probability to very flexible spaces while keeping countable additivity intact.
DP on Broken Profile - Plug DP
Plug DP (DP on broken profile with plugs) sweeps a grid cell by cell while remembering how partial path segments cross the frontier as labeled “plugs.”
Matrix Exponentiation - Advanced
Matrix exponentiation turns repeated linear transitions into fast O(n^{3} log k) computation using exponentiation by squaring.
Top Tree
Top trees are dynamic tree data structures that represent a forest as a hierarchy of clusters, allowing O(log n) amortized time for link, cut, path queries/updates, and many subtree queries.
Voronoi Diagram and Delaunay
Voronoi diagrams partition the plane so each region contains points closest to one site, while the Delaunay triangulation connects sites whose Voronoi cells touch.
Generating Functions - EGF
Exponential generating functions (EGFs) encode a sequence (a_n) as A(x) = \sum_{n \ge 0} a_n \frac{x^n}{n!}, which naturally models labeled combinatorial objects.
Pólya Enumeration
Pólya Enumeration Theorem generalizes Burnside’s Lemma by turning counting under symmetry into a polynomial substitution problem.
Burnside's Lemma
Burnside's Lemma says the number of distinct objects up to a symmetry group equals the average number of objects fixed by each symmetry.
Partition Function
The partition function p(n) counts the number of ways to write n as a sum of positive integers where order does not matter.
Generating Functions - OGF
An ordinary generating function (OGF) encodes a sequence (a_n) as a formal power series A(x) = \sum_{n \ge 0} a_n x^n.