Brute-force search 2026-10-20
Sliding-window algorithm 2026-10-20
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.
Backtracking 2026-10-20
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.
Search algorithm Created 2026-10-20 Updated 2026-11-05
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.
Maximum subarray problem 2026-10-20
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.
Meet-in-the-middle algorithm 2026-10-20
Rotating calipers 2026-10-20
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.
Floyd's cycle-finding algorithm 2026-10-20
For a deterministic iteration 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.
Cycle detection 2026-10-20
Redelmeier's algorithm Created 2026-10-20 Updated 2026-11-05
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 , occupy it, and add neighbours newly exposed by . Recurse with a copy of the updated frontier. On returning, undo those new neighbours and remove from the occupied set, but keep excluded from later sibling branches.
The exclusion prevents a later branch from reconstructing a polyomino already assigned to the branch containing . 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]
String-searching algorithm Created 2026-10-20 Updated 2026-11-05
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 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. Tonelli-Shanks algorithm Created 2026-10-20 Updated 2026-11-05
The Tonelli-Shanks algorithm finds a square root of a quadratic residue modulo an odd prime number . Handle separately and use the Legendre symbol to reject a quadratic nonresidue. Write with odd, choose a quadratic nonresidue , and initializemodulo . Maintain , with of multiplicative order and of multiplicative order dividing .
If , find the least with . Set and updateThe multiplicative order of decreases because its last nontrivial power and that of are both minus one. Thus strictly decreases. At , the invariant gives .
Aho-Corasick algorithm Created 2026-10-20 Updated 2026-11-05
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]
Efficient String Matching: An Aid to Bibliographic Search by Alfred V. Aho and Margaret J. Corasick. abstract, keyword-matching machine and single-pass search
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 total time, where is total pattern string length, text length and the number of reported occurrences. The 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.
Two-pointer technique Created 2026-10-20 Updated 2026-11-05
The two-pointer technique maintains two indices whose monotone movement avoids revisiting candidate pairs. To find two values summing to 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 time. The correctness depends on sorted order; blindly applying the rule to unsorted inputs can discard a valid pair.
Coordinate compression 2026-10-20
Exponential search Created 2026-10-20 Updated 2026-11-05
Exponential search locates a target's possible range in a sorted sequence by probing indices until the target is bounded above or the sequence ends, then uses binary search inside the final bracket. If the target lies near index , this takes 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.
Bitwise operation Created 2026-10-20 Updated 2026-11-05
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]https://docs.python.org/3/library/stdtypes.html#bitwise-operations-on-integer-types. Python language documentation, Bitwise Operations on Integer Types
Bostan-Mori algorithm Created 2026-10-20 Updated 2026-11-05
The Bostan-Mori algorithm computes without expanding all preceding coefficients. Work over a commutative ring with a unit; then the quotient defines a formal power series.
Set and . The polynomial contains only even powers. DefineBecause the denominator is even, selecting the numerator parity matching provesIterate until , then return . With bounded numerator/denominator polynomial degrees , the arithmetic complexity is , where is the cost of multiplying degree- polynomials.
For , the denominator update is . An odd index also multiplies the numerator by , recovering the familiar binary-powering pattern.[ref]
Unification Created 2026-10-20 Updated 2026-11-05
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, and have most general unifier . The variable remains free; assigning it a particular first-order term gives a more specific unifier. Requiring forces both and , so distinct constant symbols make it impossible.
Syntactic identity is essential. With addition treated as a binary function symbol, the first-order terms and 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 : a finite first-order term cannot equal one of its proper subterms. Unification makes resolution possible by aligning atomic formulas before inference.
Sorting 2026-10-20
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.
There are unlisted articles, also show them or only show them.