Maths
Pages in this section
- A finite tree that has more than one vertex must have at least two leaf verticesLast edited: 2023-11-11Proposition
A finite graph who has more than one vertex that is a tree must have at least two leaf vertex.
- A vertex with the highest post order number lies in a source SCC
Last edited: 2026-01-28LemmaSuppose we have a directed graph $G = (V,E)$ and $post: V \rightarrow \mathbb{N}$ be the result of running the DFS algorithm to find connected components in an undirected graph . Then the vertex with the largest post order number lies in a source strongly connected component in the strongly connected component graph .
- Acyclic graph
Last edited: 2026-01-28Acyclic graphA directed graph or undirected graph is acyclic if it contains no cycles .
- All linear programmes can be represented in standard form
Last edited: 2026-01-28# Statement
LemmaAll linear programmes can be represented in standard form .
- Arithmetic mean
Last edited: 2026-02-05Arithmetic meanGiven $k$ values $w_i \in \mathbb{R}$ for $1 \leq i \leq k$ we define the arithmetic mean to be
- Arithmetic mean is greater than or equal to the geometric mean
Last edited: 2026-01-28# Statement
LemmaFor $w_1, \ldots, w_k \geq 0$ we have the arithmetic mean is greater than or equal to the geometric mean . In other words
- Associativity
Last edited: 2025-12-05AssociativityA binary operation $\ast$ is associative if $(a \ast b) \ast c = a \ast (b \ast c)$.
- Big-O notation
Last edited: 2023-11-11Big-O notation is the main way people determine the runtime of algorithms. (Rightly or wrongly.) It is the worst case analysis and has a formal mathematical definition
$$ f = O(g) \mbox{ if } \exists \ x_0 \in \mathbb{N}, m \in \mathbb{R}_{>0} \mbox{ such that } f(x) \leq m \ast g(x)\ \forall x > x_0.$$This is just saying that $f$ eventually is at most a scalar multiple of $g$.
- Big-Omega notation
Last edited: 2023-11-11Big-Omega notation is said to be the best case runtime of an algorithm. However formally it is simply a lower bound on the run time - the same as Big-O notation is simply an upper bound. This has a similar formal definition
$$ f = \Omega(g) \mbox{ if } \exists \ x_0 \in \mathbb{N}, m \in \mathbb{R}_{>0} \mbox{ such that } 0 \leq m \ast g(x) \leq f(x) \ \forall x > x_0.$$This is just saying that $f$ eventually is at least a scalar multiple of $g$.
- Big-Theta notation
Last edited: 2023-11-11Big-Theta notation is the tight bound on the runtime of an algorithm. This is only really defined when some function is the following $f = O(g)$ using Big-O notation and $f = \Omega(g)$ then we have $f=\Theta(g)$ using Big-Theta notation this is also an equivalence relation, so $g = \Theta(f)$ as well.
- Binary operation
Last edited: 2026-01-28Binary operationA binary operation is a function that takes two inputs and outputs another one - all in the same domain.
- Binary step
Last edited: 2026-02-05Binary stepThe binary step is an activation function that determines what the value is in reference to a parameter $\theta$.
- Binomial coefficient
Last edited: 2026-02-05Binomial coefficientLet $0 \leq k \leq n$ for $k,n \in \mathbb{n}$ then define the binomial coefficient of $n$ choose $k$ as
- Bipartite graph
Last edited: 2026-02-05Bipartite graphA graph (directed graph or undirected graph ) $G = (V,E)$ is bipartite if you can partition the vertex set $V = V_1 \cup V_2$ such that for all $(u,v) \in E$ we have $u \in V_1$ and $v \in V_2$ or vice versa.
- Boolean function
Last edited: 2023-11-11A Boolean function is a function that takes only boolean inputs and outputs a boolean .
- Boolean variable
Last edited: 2023-11-11A Boolean variable is one that takes the value
TrueorFalseit is a basic type in most programming languages.In Maths Index the
TrueorFalsevalue is regularly replaced with1or0respectively. This is similar to the representation that variable would have in memory.- Carmichael number
Last edited: 2026-02-05Carmichael numberA $z \in \mathbb{N}$ is called a Carmichael number if it is not prime and has no non-trivial Fermat witness .
- Chinese remainder theorem
Last edited: 2023-11-11# Statement
Chinese remainder theoremLet $n_i \in \mathbb{Z}$ be positive non-zero, non-unit elements for $1 \leq i \leq k$ where $n_i$ are pairwise coprime and set $N = \prod_{i=1}^k n_i$. Then for any $a_i \in \mathbb{Z}$ with $0 \leq a_i < n_i$ and $1 \leq i \leq k$ there exists a unique $x \in \mathbb{Z}$ where $0 \leq x < N$ such that
- Clique (graph)
Last edited: 2026-02-05Clique (graph)In an undirected graph $G = (V,E)$ a set of vertices $C \subset V$ is a clique if the induced subgraph on $C$ is the complete graph on $C$. (i.e. $\{(c,c') \vert \ c, c' \in C \text{ with } c \neq c'\} \subset E$.)
- Clique of a given size problem is NP-complete
Last edited: 2026-01-28# Statement
LemmaClique of a given size problem is NP-Complete .
- Cliques in G are independent sets in the complement
Last edited: 2025-12-05# Statement
LemmaFor an undirected graph $G = (V,E)$ and $S \subset V$ we have the following equivalence: $S$ is a clique in $G$ if and only if $S$ is an independent set in $G^C$ the complement graph .
- Complement graph
Last edited: 2026-02-05Complement graphGiven an undirected graph or directed graph $G = (V,E)$. We define the complement graph
- Complete graph
Last edited: 2026-02-05Complete graphThe complete graph on $S$ is the undirected graph $(S, \{(s,s') \vert \ s, s' \in S \mbox{ with } s \not = s'\})$. (i.e. it is the graph with vertices $S$ and every possible edge between them excluding self-connected edges.)
- Computational folk theorem
Last edited: 2025-12-05# Statement
LemmaFor any 2-player discounted reward repeated game it is possible to build a Pavlov-like machine that is Subgame perfect and achieves Nash equilibrium in polynomial time. This is done in one of three ways
- Conjunctive normal form (CNF)
Last edited: 2023-11-11A Boolean function is in conjunctive normal form if it is a collection of or statements unified by and operations. The or statements can contain negated variables but no further nesting.
The following are in CNF:
- $A$,
- $(A \lor B)$,
- $(A) \land (B)$,
- $(A \lor B) \land (A)$,
- $\lnot A$ , and
- $(A \lor \lnot B \lor \lnot C) \land (\lnot D \lor E \lor F)$.
The following are not in CNFL:
- Connected (graph)
Last edited: 2023-11-11A graph $G = (V, E)$ is considered connected if for all vertices $x,y \in V$ there exists a path $\{v_i\}_{i=1}^k$ such that $v_1 = x$ and $v_k = y$.
- Connected components (graph)
Last edited: 2026-01-28Connected componentsIn a graph a connected component is a maximal connected subgraph $G'$ of $G$.
- Coprime
Last edited: 2026-02-05CoprimeGiven $m, n \in \mathbb{Z}$ we say they are coprime if and only if they have unit greatest common divisor $gcd(m,n) = 1$.
- CS6035 O01 Introduction to Information Security
Last edited: 2026-01-28Introduction to Information Security is a graduate-level introductory course in information security. It teaches the basic concepts and principles of information security, and the fundamental approaches to secure computers and networks.
Main topics include:
- Security basics
- Security management and risk assessment
- Software security
- Operating systems security
- Database security
- Cryptography algorithms and protocols
- Network authentication and secure network applications
- Malware
- Network threats and defences
- Web security
- Mobile security
- Legal and ethical issues
- Privacy
# Links
- CS6215 Introduction to Graduate Algorithms
Last edited: 2023-12-03This course is a graduate-level course in the design and analysis of algorithms. We study techniques for the design of algorithms (such as dynamic programming) and algorithms for fundamental problems (such as fast Fourier transform FFT). In addition, we study computational intractability, specifically, the theory of NP-completeness. The main topics covered in the course include: dynamic programming; divide and conquer, including FFT; randomized algorithms, including RSA cryptosystem; graph algorithms; max-flow algorithms; linear programming; and NP-completeness.
- CS7641 Machine Learning
Last edited: 2024-01-10This is a 3-course Machine Learning Series, taught as a dialogue between Professors Charles Isbell (Georgia Tech) and Michael Littman (Brown University).
Supervised Learning Supervised Learning is a machine learning task that makes it possible for your phone to recognize your voice, your email to filter spam, and for computers to learn a number of fascinating things. This sort of machine learning task is an important component in all kinds of technologies. From stopping credit card fraud; to finding faces in camera images; to recognizing spoken language - our goal is to give students the skills they need to apply supervised learning to these technologies and interpret their output. This is especially important for solving a range of data science problems.
- CS7642 Reinforcement Learning
Last edited: 2024-01-10The course explores automated decision-making from a computational perspective through a combination of classic papers and more recent work. It examines efficient algorithms, where they exist, for learning single-agent and multi-agent behavioral policies and approaches to learning near-optimal decisions from experience.
Topics include Markov decision processes, stochastic and repeated games, partially observable Markov decision processes, reinforcement learning, deep reinforcement learning, and multi-agent deep reinforcement learning. Of particular interest will be issues of generalization, exploration, and representation. We will cover these topics through lecture videos, paper readings, and the book Reinforcement Learning by Sutton and Barto.
- CS8803 O08 Compilers - Theory and Practice
Last edited: 2026-01-28The objective of this course is to learn the theory and practice behind building automatic translators (compilers) for higher level programming languages and to engineer and build key phases of a compiler in Java or C++ for a small language.
# Links
- Cut (graph)
Last edited: 2026-02-05CutLet $G = (V,E)$ be a undirected graph . A cut of $G$ is a partition of $V = S \cup \overline{S}$. The cut edges are
- Cut property
Last edited: 2023-11-11Cut propertyLet $G = (V,E)$ be an undirected graph with an edge weight $w: E \rightarrow \mathbb{R}$. Suppose $X \subset E$ is part of an MST $T$. Let $S \subset V$ be a cut where no edge of $X$ is in the cut edges $cut(S, \overline{S})$. Then for $e^{\ast} \in cut(S, \overline{S})$ of minimum weight - $X \cup \{e^{\ast}\}$ is part of an MST $T^{\ast}$.
- Cycle (graph)
Last edited: 2023-11-11A cycle in a graph is path $\{e_i = (x_i, y_i)\}_{i=1}^{k}$ such that $x_1 = y_k$ and $e_i = e_j \Rightarrow i = j$.
Visual representationLets use our simple graph below
In this graph we have a cycle using the vertices $\{1,2,3\}$.- Cycles in a graph via the DFS tree
Last edited: 2026-01-28LemmaA directed graph $G$ has a cycle if and only if its DFS tree has a back edge.
- Decision tree
Last edited: 2026-02-05Decision treeSuppose you have two sets $A$ and $B$. A decision tree is a representation of a function $f: A \rightarrow B$, it is comprised of,
- Degree (graph)
Last edited: 2023-11-11In a graph the degree of vertex is the number of ends of edges that are incidence to the vertex. This is denoted $\mbox{deg}(v)$ for some $v \in V$.
In a graph with no loops this is the same as the number of edges that are incident to the vertex. However, for evert loop in the graph on that vertex we have a contribution of 2 towards the vertex.
- DFS tree (algorithm)
Last edited: 2026-01-28DFS treeGiven a run of a DFS algorithm $A$ on a directed graph $G = (V,E)$, the DFS tree is a subgraph -forest $F = (V,E')$ where $E'$ are the edges used by $A$ to first explore a vertex.
- Directed graph
Last edited: 2026-01-28Directed graphLet $V$ be a set of vertices and let $E \subset V \times V$ be a set of edges. An edge $e = (x,y)$ is a directed edge from $x \in V$ to $y \in V$. The directed graph is the pair $(V,E)$.
- Dot product
Last edited: 2026-02-05Dot productFor two vectors $x,y \in \mathbb{R}^n$ the dot product is
- Edge weights
Last edited: 2026-02-05Edge weightsLet $G = (V,E)$ be a Graph or a directed graph then edge weights in some domain $D$ is a function $w: E \rightarrow D$.
- Eigenvector and Eigenvalue
Last edited: 2026-02-05Eigenvector and EigenvalueGiven a field $F$ and matrix $A \in M_{n,n}(F)$ an eigenvector is a vector $v \in M_{n,1}(F)$ such that
- Equivalent tree definitions
Last edited: 2026-01-28LemmaThe following conditions are equivalent for a graph $G = (V,E)$.
- Ergodic Markov chain
Last edited: 2026-02-05Ergodic Markov chainA Markov chain is said to be ergodic if it is both aperiodic and irreducible .
- Ergodic Markov chain limiting distribution
Last edited: 2026-02-05# Statement
LemmaFor an Ergodic Markov chain with unique stationary distribution $\pi$ we have
- Ergodic Markov chains have a unique stationary distribution
Last edited: 2026-01-28# Statement
LemmaAn ergodic Markov chain has a unique stationary distribution .
- Euclid's rule
Last edited: 2023-11-11# Statement
Euclid’s ruleFor integers $x,y \in \mathbb{Z}$ where $x \geq y > 0$ we have
- Euclidean algorithm
Last edited: 2023-11-11This algorithm is used to calculate the greatest common divisor for two positive integers. This uses Euclid’s rule and modular arithmetic .
# Algorithm
Euclid(x,y): Input: integers x,y where x >= y >= 0 Output: gcd(x,y) 1. If y = 0 return x 2. return Eculid(y, x mod y)# Run time
If $x$ and $y$ are $n$-bit integers then calculating $x$ mod $y$ takes $O(n^2)$ time. From Claim 1 we have every 2 rounds $x$ decreases by at least a factor of 2. So there are at most $2n$ rounds giving this algorithm a run time of $O(n^3)$.
- Euler's theorem (modular arithmetic)
Last edited: 2023-11-11# Statement
Euler’s theoremFor integers $n,a \in \mathbb{Z}$ such that gcd(n,a) = 1. Then
- Euler's totient function
Last edited: 2026-01-28Euler’s totient functionFor a natural number $n \in \mathbb{N}$ define Euler’s totient function as
- Eulers product formula (totient function)
Last edited: 2023-11-11# Statement
Euler’s product formulaGiven some $n \in \mathbb{N}$ with prime decomposition $n = \prod_{i=1}^k p_i^{e_i}$ with $p_i \in \mathbb{N}$ distinct primes and $e_i \in \mathbb{N}$. Then the Euler’s totient function of $n$ is
- Every min-cut has no flow going backwards along it in a max-flow
Last edited: 2025-12-05# Statement
LemmaGiven a Flow network $(G, c, s, t)$ with a max flow $f$. Then for every min st-cut $(S, T)$ we have $f(t',s') = 0$ for all edges $(t',s') \in E$ with $t' \in T$ and $s' \in S$.
- Exclusive or
Last edited: 2026-02-05Exclusive orExclusive or (Xor) is a binary operation where exactly on of the inputs needs to be true
- Existence of a Fermat witness if and only if composite
Last edited: 2023-11-11# Statement
LemmaA number $r$ has a Fermat witness if and only if $r$ is not prime .
- Extended Euclidean algorithm
Last edited: 2023-11-11This algorithm extends the Euclidean algorithm to be able to calculate the greatest common divisor of two integers.
# Algorithm
extended_euclidean(x,y): Input: integers x, y where x >= y >= 0 Output: integers d, a, b where d = gcd(x,y) and d = xa + yb 1. if y = 0, return (x,1,0) 2. (d, a', b') = extended_euclidean(y,x mod y) 3. return (d, b', a' - floor(x/y)b')# Runtime
Notice this is functionally the same as Euclidean algorithm . So if $x, y$ are $n$-bit integers then this takes $O(n^3)$.
- Fermat witness
Last edited: 2026-02-05Fermat WitnessFor a number $r \in \mathbb{N}$ a Fermat witness is a value $0 < z < r-1$ such that
- Fermat's little theorem
Last edited: 2023-11-11# Statement
Fermat’s little theoremFor any prime number $p$ and $a \in \mathbb{Z}$ we have
- Finding the maximum likelihood estimation for normally distributed noise is the same as minimising mean squared error
Last edited: 2026-01-28# Statement
LemmaSuppose we have some target $c : A \rightarrow \mathbb{R}$ where the training data $T$ has i.i.d. normally distributed noise values $\epsilon \sim N(0,\sigma^2)$ such that $(a_i,b_i) \in T$ we have $b_i = c(a_i) + \epsilon_i$. Then finding the maximum likelihood estimation is the same as minimising the Mean squared error (MSE) , i.e.
- Flows are maximal if there is no augmenting path
Last edited: 2023-11-11# Statement
LemmaGiven a flow network $(G, c, s, t)$ a flow $f$ is maximal if there is no path from $s$ to $t$ in the residual network $(G^f, c^f, s, t)$.
- Forest (graph)
Last edited: 2026-01-28ForestA graph is a forest if each of its connected components is a tree .
- Fourier Matrix
Last edited: 2023-11-11The Fourier matrix is used in Fast Fourier Transform . Let $\omega$ be a $n$‘th root of unity then define the Fourier matrix to be
$$F_n(\omega) = \left [ \begin{array} \ 1 & 1 & 1 & \cdots & 1\\ 1 & \omega & \omega^2 & \cdots & \omega^{n-1}\\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(n-1)}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & \omega^{n-1} & \omega^{n-2} & \cdots & \omega \end{array} \right ].$$- Function
Last edited: 2026-02-05FunctionGiven two sets $A$ and $B$, a function $f: A \rightarrow B$ takes an element of $a$ and maps to some element $f(a) \in B$ - importantly for every $a \in A$ there is only 1 element it maps to. Formally $f \subset A \times B$ such that for all $a \in A$ $\vert f \cap \{(a,b) \vert b \in B\}\vert = 1$. (We think of the set $f$ as $\{(a,f(a)) \vert a \in A\}$.)
- Function codomain
Last edited: 2026-02-05Function co-domainGiven a function $f: A \rightarrow B$ the codomain is $B$, the set of all possible values $f(a)$ can take. Note this is different form the image which is all values $f$ does take.
- Function domain
Last edited: 2026-02-05Function domainGiven a function $f: A \rightarrow B$ the domain of $f$ is $A$, the set of inputs.
- Function image
Last edited: 2026-02-05Function imageGiven a function $f: A \rightarrow B$ the image of the function is $F(A) = \{f(a) \vert a \in A\} \subset B$. Note this is not necessarily equal to the codomain $B$.
- Game theory
Last edited: 2026-02-05Game theoryGame theory is the study of systems where there are more than one rational players.
- Geometric mean
Last edited: 2026-02-05Arithmetic meanGiven $k$ values $w_i \in \mathbb{R}$ for $1 \leq i \leq k$ we define the geometric mean to be
- Graph
Last edited: 2025-12-05GraphA simple undirected graph is a tuple of $V$, the vertex set, and $E \subset V \times V$, an edge set. This is normally referred to as $G = (V, E)$. As this is undirected, an edge $e = (x,y)$ is the same as the edge $e = (y,x)$, so if we define an equivalence relation $(x,y) \sim (y,x)$ for all $x,y \in V$, then it is fairer to say $E \subset V \times V / \sim$.
- Greatest common divisor
Last edited: 2026-01-28Greatest common divisorLet $x, y \in \mathbb{Z}$. Then define the $\gcd(x,y)$ to be the largest natural number $n \in \mathbb{N}$ such that $n \mid x$ and $n \mid y$.
- Happens with high probability
Last edited: 2026-02-05Happens with high probabilityWe say an event $A(n)$ which depends on some constant $n$ happens with high probability if there is some polynomial $p(x)$ such that for sufficiently large $n$ we have
- How post order relates to strongly connected components
Last edited: 2023-11-11LemmaLet $G = (V,E)$ be a directed graph with two strongly connected components $S$ and $S'$. Let $post: V \rightarrow \mathbb{N}$ be the result of running the DFS to find connected components in an undirected graph algorithm $A$. If there exists $v \in S$ and $w \in S'$ such that $(v,w) \in E$ then
- Hyperbolic tangent (tanh)
Last edited: 2026-02-05Hyperbolic tangentThe hyperbolic tangent function maps $tanh: \mathbb{R} \rightarrow (-1,1)$ by
- Hyperplane
Last edited: 2026-02-05HyperplaneA hyperplane in an $n$-dimensional vector space $V$ over a field $\mathbb{F}$ is an $n-1$ dimensional subplane. This is given by $n-1$ linearly independent vectors $v_1, v_2, \ldots, v_{n-1} \in V$ and a point $x \in V$. Then the space is made of
- If a point in a linear programme has equal objective function to a point in its dual linear programme they are both optimal
Last edited: 2026-01-28# Statement
LemmaFor a linear programme given by $A$, $b$, and $c$ if there is a feasible point $x \in \mathbb{R}^n$ and a feasible point $y \in \mathbb{R}^m$ in the dual linear programme such that
- Increasing sequence
Last edited: 2026-02-05Increasing sequenceA sequence is increasing if each subsequent term is greater than the previous.
- Independent set (graph)
Last edited: 2026-02-05Independent set (graph)In a graph $G = (V,E)$ a subset $I \subset V$ is an independent set if the induced subgraph on $I$ has no edges. (i.e. for all $(u,v) \in E$ either $u \not \in I$ or $v \not \in I$.)
- Independent set of a given size is NP-complete
Last edited: 2026-01-28# Statement
LemmaIndependent set of a given size is NP-complete .
- Indicator function
Last edited: 2026-02-05Indicator functionThe indicator function takes a boolean value and maps it to $0$ or $1$ based on whether the value is true or not.
- Induced subgraph
Last edited: 2026-02-05Induced subgraphGiven a graph $G = (V, E)$ (directed graph or undirected graph ) and a subset of the vertices $X \subset V$. The induced subgraph of $G$ on $X$ is the subgraph of $G$ defined by $H = (X, \{(u,v) \in E \vert u,v \in X\})$.
- Inference
Last edited: 2026-02-05InferenceIn the modelling framework for a function $f: A \rightarrow B$ an inference about $f$ is some understanding of its True form. For example, if $A$ was a companies revenue and expenditure and $f$ was the profit function, an inference would be that $f$ is revenue minus expenditure.
- Information entropy
Last edited: 2026-02-05Information EntropySuppose we have a discrete random variable $X$ that can take values in $A$. We define the information entropy of $X$ to be
- Integer linear programming is NP-hard
Last edited: 2025-12-05# Statement
Lemmainteger linear programming is NP-hard .
- Inverse of the Fourier matrix
Last edited: 2023-11-11LemmaLet $F_n(\omega)$ be a Fourier Matrix then we have
- Irreducible
Last edited: 2026-02-05IrreducibleAn element $p$ is irreducible if it is a non-zero, non-unit element that when $p = mn$ then $m$ or $n$ is a unit.
- Irreducible Markov chain
Last edited: 2026-02-05Irreducible Markov chainA Markov chain given by $P \in M_{N,N}(\mathbb{R})$ is irreducible if the directed graph on $V = \{1, 2, \ldots, N\}$ given by non-zero values of $P$ has a single strongly connected component .
- Kernel trick
Last edited: 2026-02-05Kernel trickSuppose we are in the modelling framework with training data $T \subset A \times B$. When using SVMs we want to find a hyperplane that linearly separates the data - though this might not be possible for the current embedding of $T$ in $A$. Though it might be possible for a map
- Knapsack-search is NP
Last edited: 2026-01-28# Statement
LemmaKnapsack-search is in NP .
- Leaf (graph)
Last edited: 2023-11-11In a graph we say a vertex $v \in V$ is a leaf if the degree of the vertex is 1, i.e. $\mbox{deg}(v) = 1$.
Visual exampleIn the graph below $4$ is a leaf vertex.
- Learning rate convergence
Last edited: 2026-01-28# Statement
LemmaGiven a Markov decision process $M$, let $V_t(s)$ be the value estimate for a state $s$ at the $t$-th iteration. If we update this using the following update rule:
- Linear regression
Last edited: 2026-02-05Linear regressionLinear regression is the special case of polynomial regression where the degree of the polynomial is 1. Therefore we are restricted to the modelling paradigm of
- Linearly separable
Last edited: 2026-02-05Linearly separableTwo sets of points $X_1, X_2 \subset \mathbb{R}^n$ are linearly separable if there is some hyperplane $P$ defined $w_i, \theta \in \mathbb{R}$ for $1 \leq i \leq n$:
- Logarithms
Last edited: 2026-01-28A logarithm is the inverse operation to exponentiation. Given a base $b > 0$ and $b \not = 1$, the logarithm $\log_b(a)$ is the exponent $x$ you would raise $b$ to in order to get $a$.
LogarithmThis is defined as:
- Logical and
Last edited: 2026-02-05Logical andThis is a boolean function regularly expressed as $\land: \{T, F\}^2 \rightarrow \{T, F\}$ which is only true if both its inputs are.
- Logical OR
Last edited: 2026-02-05Logical ORThis is a boolean function typically expressed as $\lor: \{T, F\}^2 \rightarrow \{T, F\}$ which is only false if both its inputs are.
- Loop (graph)
Last edited: 2023-11-11A loop in a graph is an edge of the form $(v,v)$ i.e. the start and end vertices are the same. These are not permitted in simple graphs.
- Markov chain
Last edited: 2026-02-05Markov chainA Markov chain is specified by a number of states $N$ and a transition probability matrix $P \in M_{N \times N}(\mathbb{R})$. Intuitively think of this as a state machine which at state $i$ has probability $p_{i,j}$ of transitioning to state $j$.
- Masters theorem
Last edited: 2023-11-11Masters theoremGiven a $T$ a recurrence relation of the form
$$T(n) = a T(\frac{n}{b}) + f(n), \mbox{ with } T(1) = d$$for constants $a \geq 1$, $b > 1$, and $d > 0$. Let $c_{crit} = \log_b(a)$ with $f$ asymptotically positive. Then the following statements are true:
- Matrix
Last edited: 2026-02-05 - A vertex with the highest post order number lies in a source SCC