Glossary

A group is abelian if its group operation $*$ is commutative.

A binary operation $*$ is associative if $((a *b) * c) = a * (b * c)$

A binary operation $*$ is commutative if $a * b = b * a$.

A field is a commutative ring (multiplication commutes) where $0 \neq 1$ (additive and multiplicative identities are different) and all nonzero elements are invertible under multiplication.

A group is a set with an operation $*$ that satisfies the following: the operation is associative and has an identity element $1$, and every element has an inverse (that is, for all g in the group, there exists an element $\overline{g}$ such that $g * \overline{g} = 1$

A ring $R$ is a set with two operations, $+$ and $*$. $R$ must be an abelian group under addition. Also, $\cdot$ must be associative and have an identity element. Finally, $\cdot$ must be distributive with respect to $+$, that is, $a \cdot (b+c) = a\cdot b + a\cdot c$ and (b+c) \cdot a = b\cdot a + c\cdot a$.

Like a ring, a semiring is a set with a $+$ and $\cdot$ operation. However, it drops the requirement that $+$ have additive inverses.

Big O notation is used to classify algorithms according to how their runtime or space requirements grow as the input size grows. For example, we say that an algorithm requires O(f(n)) time if, as the size of the input (n) grows linearly, the amount of time required to run the algorithm grows proportially to f(n).

A set $S$ is convex if for any two elements $x, y \in S$, any linear combination of $x$ and $y$ of the form $c_1x + c_2y$ is still in $S$.

A set equipped with a distance function, which provides a measure of distance between any two points in the set and satisfies certain axioms. Metrics must be symmetric, i.e. $d(u,v) = d(v,u)$, satisfy $d(x,y)=0$ iff $x=y$, and the triangle inequality: $d(x, z) \leq d(x, y) + d(y, z).$

In general, a dense graph is a graph in which the number of edges is close to the maximal number of edges. For a graph on $n$ vertices, there are $O(n^2)$ possible edges (one between each pair of vertices. Thus, a dense graph would have $O(n^2)$ edges.

Similarly, a sparse graph is one where the number of edges is not close to the maximum. For a graph on $n$ vertices, where there are $O(n^2)$ possible edges, a sparse graph might have $O(n)$ or even fewer edges.

A matching on a graph (or an independent edge set) is a set of edges that don't have vertices in common. In other words, each vertex has 0 or 1 edges incident to it.

A flow network is a directed graph where each edge has a capacity and receives a flow. The flow must satisfy Kirchhoff's circuit laws — the sum of the flows entering a node must equal the sum of the flows exiting it, and the directed sum of the flow in a cycle must be 0.

A tree is a graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic graph.

A triangular matrix is a special kind of square matrix. A square matrix is called lower triangular if all the entries above the main diagonal are zero. Similarly, a square matrix is called upper triangular if all the entries below the main diagonal are zero.

Any problem that takes an input (usually encoded by a bitstring) and outputs a single bit, 0 or 1. Canonically, we think about decision problems in the context of Turing machines, which accept or reject given an input tape.

The problem of finding the "best" solution from all feasible solutions, usually done by maximizing or minimizing the value of some objective function. Examples include: shortest paths, minimum spanning trees, etc.