A search algorithm that tests candidates directly, without exploiting enough structure to avoid their enumeration. A small brute-force implementation is often useful for checking an optimized algorithm independently.

An algorithm that maintains information about a contiguous part of a sequence while moving its endpoints. Updating a fixed-length window sum needs subtraction of the outgoing term and addition of the incoming term. A window product can be updated by division only when the outgoing factor is nonzero; zero counts or zero-free segments handle that exception.

Build a candidate incrementally, abandoning a partial candidate as soon as no valid completion is possible. A depth-first search explores one choice, restores the previous state, and tries the next. Constraint propagation and bounds can greatly reduce the visited state space, although the worst-case time complexity may remain exponential.

A search algorithm looks for an object satisfying a specified condition within a collection or state space. Linear search inspects entries directly; binary search exploits sorted order; breadth-first search explores graph states by distance from a start. The specification should say whether to return one witness, every witness or proof of absence. A procedure that eventually finds every reachable witness may still fail to terminate when none exists in an infinite space. Representation and available structure determine which candidates can safely be ruled out without inspection.

Given a finite sequence of real numbers, find a nonempty contiguous block with maximum sum. Its restriction to contiguous blocks distinguishes it from choosing an arbitrary subset. The problem admits a linear-time solution using Kadane's algorithm.

An algorithm that splits choices into two groups, enumerates partial results for each group, and matches compatible results. For $n$ binary choices, the two lists each have about $2^{n/2}$ entries instead of enumerating $2^n$ complete choices; the matching cost and memory requirements depend on the problem.

A family of algorithms that exploit monotonically changing geometric directions while traversing sorted points or the boundary of a convex polygon. For example, after sorting rays by polar angle around a point, a second index can advance monotonically to identify all rays lying in each open half-plane. Collinear rays require consistent boundary handling.

For a deterministic iteration $x_{n+1}=f(x_n)$ on a finite set, move one pointer by one step and another by two steps. They eventually meet inside the repeated cycle. Restarting one pointer at the initial state and advancing both by one step locates the cycle entrance; a further traversal measures its length. The method uses constant extra space complexity and time proportional to the preperiod plus cycle length.

Determine whether repeated deterministic updates revisit a state, and optionally find the preperiod and cycle length. Recording all visited states uses memory proportional to the visited orbit. Floyd's cycle-finding algorithm detects repetition with constant extra memory.

Redelmeier's algorithm enumerates fixed polyominoes, identifying translations while retaining different orientations. Put the leftmost cell of the bottom row at the origin. Allowed cells lie above the horizontal axis, or on it at nonnegative horizontal coordinates.

Maintain the occupied set of cells, an untried frontier of adjacent cells, and exclusions inherited from earlier branches. Remove a frontier cell $u$, occupy it, and add neighbours newly exposed by $u$. Recurse with a copy of the updated frontier. On returning, undo those new neighbours and remove $u$ from the occupied set, but keep $u$ excluded from later sibling branches.

The exclusion prevents a later branch from reconstructing a polyomino already assigned to the branch containing $u$. Requiring new cells to touch the occupied set preserves connectivity; every canonical polyomino has a branch determined by its first available frontier choice. Thus each fixed polyomino is visited once.

At size two there are two fixed polyominoes, horizontal and vertical, but one free polyomino after identifying rotations. Counting free polyominoes needs an additional treatment of symmetry.^[ref]

A string-searching algorithm locates occurrences of a pattern in a text, typically requiring a contiguous substring match. For text ababa and pattern aba, zero-based matches start at zero and two; overlaps count unless excluded by the specification. The direct algorithm compares the pattern at each start and can require $O(nm)$ character comparisons. The Knuth-Morris-Pratt algorithm reuses prefix information for linear total scanning work. State the alphabet, case handling and empty-pattern convention: matching bytes, Unicode code points and user-perceived characters can describe different tasks.

The Tonelli-Shanks algorithm finds a square root of a quadratic residue $a$ modulo an odd prime number $p$. Handle $a=0$ separately and use the Legendre symbol to reject a quadratic nonresidue. Write $p-1=2^{s}q$ with $q$ odd, choose a quadratic nonresidue $z$, and initializemodulo $p$. Maintain $r^2=at$, with $c$ of multiplicative order $2^m$ and $t$ of multiplicative order dividing $2^{m-1}$.

If $t\ne 1$, find the least $i$ with $t^{2^i}=1$. Set $b=c^{2^{m-i-1}}$ and updateThe multiplicative order of $t$ decreases because its last nontrivial power and that of $b^2$ are both minus one. Thus $m$ strictly decreases. At $t=1$, the invariant gives $r^2=a$.

For $p=13,a=10,z=2$, initialization gives $(c,t,r,m)=(8,12,9,2)$. One update gives $r=7,t=1$, so the roots are $7$ and $6$ modulo thirteen.^[ref]

The Aho-Corasick algorithm reports occurrences of a finite collection of nonempty pattern strings in one string. It builds an Aho-Corasick automaton from their trie. Each scanned character extends the current state; when no edge matches, failure links find a shorter matching suffix. Report the current terminal pattern string and the terminal ancestors reached through output links.^[ref]

The state represents the longest suffix of the scanned text that is a prefix of some pattern string. This invariant explains correctness: a match ending now is exactly a terminal suffix represented by that state or a failure link ancestor. It also reports overlaps. With pattern strings ab, bab, bc, scanning babc reports ab and bab at position three, then bc at position four.

For a fixed-size alphabet, completed transitions and output links give $O(M+n+z)$ total time, where $M$ is total pattern string length, $n$ text length and $z$ the number of reported occurrences. The $z$ term is unavoidable when listing every match. Store terminal output links instead of copying every inherited match list: copied suffix lists can greatly enlarge preprocessing.

The two-pointer technique maintains two indices whose monotone movement avoids revisiting candidate pairs. To find two values summing to $t$ in an increasing array, start at its ends. If their sum is too small, move the left index right: every pair using the old left value is too small. If too large, move the right index left by the symmetric argument. Each step eliminates one index, so after sorting the scan takes $O(n)$ time. The correctness depends on sorted order; blindly applying the rule to unsorted inputs can discard a valid pair.

Coordinate compression replaces coordinates by a smaller representation while retaining the order or distance information needed by an algorithm. Rank compression retains only order; geometry-specific transformations may instead remove known gaps or widths.

Exponential search locates a target's possible range in a sorted sequence by probing indices $1,2,4,8,\dots$ until the target is bounded above or the sequence ends, then uses binary search inside the final bracket. If the target lies near index $k$, this takes $O(\log (k+1))$ probes under random-access and constant-comparison assumptions. For an unbounded monotone predicate, the same method brackets the first true index. It is useful when the relevant prefix is much shorter than the whole sequence or its length is not initially known. Finite sequences still require bounds checks at each probe.

A bitwise operation applies a Boolean operation separately to corresponding positions of binary representations. For four-bit values 1010 and 1100, AND gives 1000, OR gives 1110, and exclusive or gives 0110. Bit shifts move positions, while bitwise complement reverses each bit. The representation width and signedness matter: fixed-width machine arithmetic and unbounded integers need not interpret leading bits alike. These operations are useful for compact sets, flags and bit parallelism. They differ from logical operations that test the truth of entire operands.^[ref]

The Bostan-Mori algorithm computes $[x^N]P(x)/Q(x)$ without expanding all preceding coefficients. Work over a commutative ring with $Q(0)$ a unit; then the quotient defines a formal power series.

Set $U(x)=P(x)Q(-x)$ and $V(x)=Q(x)Q(-x)$. The polynomial $V$ contains only even powers. DefineBecause the denominator $V(x)=Q^{\prime }(x^2)$ is even, selecting the numerator parity matching $N$ provesIterate until $N=0$, then return $P(0)/Q(0)$. With bounded numerator/denominator polynomial degrees $O(d)$, the arithmetic complexity is $O(M(d)\log (N+1))$, where $M(d)$ is the cost of multiplying degree-$d$ polynomials.

For $1/(1-cx)$, the denominator update is $1-c^{2}y$. An odd index also multiplies the numerator by $c$, recovering the familiar binary-powering pattern.^[ref]

Unification finds a substitution making given first-order terms syntactically identical. In first-order unification, a substitution replaces variables by first-order terms while leaving function symbols fixed. A most general unifier captures the necessary identifications: every other unifier follows by a further substitution.^[ref]

For example, $f(x,g(y))$ and $f(g(z),g(a))$ have most general unifier $\{x\mapsto g(z),y\mapsto a\}$. The variable $z$ remains free; assigning it a particular first-order term gives a more specific unifier. Requiring $f(x,x)=f(a,b)$ forces both $x=a$ and $x=b$, so distinct constant symbols $a,b$ make it impossible.

Syntactic identity is essential. With addition treated as a binary function symbol, the first-order terms $x+0$ and $x$ are different even though their values agree under ordinary arithmetic. Equational unification incorporates specified identities and is a different problem. For finite first-order terms, the occurs check rejects $x=f(x)$: a finite first-order term cannot equal one of its proper subterms. Unification makes resolution possible by aligning atomic formulas before inference.

Rearranging a finite sequence according to a specified order while preserving its entries and their multiplicities. A sorting algorithm performs this operation; lexicographic order supplies a common order for tuples or strings.