2-SAT is the problem of deciding whether a Boolean formula with at most two literals per clause has a satisfying assignment; it can be solved in linear time.
two-sat3SUM problemThe 3SUM problem asks whether a set of numbers contains three elements that sum to zero. It is a standard benchmark in fine-grained complexity theory.
3sum-problemA* SearchA* is a best-first search algorithm that combines accumulated path cost with an estimated remaining cost to find optimal paths under specified conditions.
a-star-searchAbstract Data TypeAn abstract data type specifies values and operations by their observable behavior, independently of their concrete representation or implementation.
abstract-data-typeAdditive white Gaussian noise channelAn additive white Gaussian noise channel models communication by adding signal-independent Gaussian noise with a flat power spectrum to the transmitted signal.
additive-white-gaussian-noise-channelAdjacency ListAn adjacency list represents a graph by associating each vertex with a collection of its neighboring vertices or incident edges.
adjacency-listAlan TuringAlan Turing was a British mathematician and codebreaker whose work established foundations of computer science, artificial intelligence, and mathematical biology.
alan-turingAlgorithmAn algorithm is a precisely specified procedure for performing a computation or solving a class of problems.
algorithmAliasingAliasing is the indistinguishability of different signals after sampling, producing false frequencies or patterns; in programming, it also means multiple references to the same storage.
aliasingAlpha–Beta PruningAlpha–beta pruning accelerates minimax game-tree search by eliminating branches that cannot affect the root value.
alpha-beta-pruningAmdahl's lawAmdahl’s law describes how the portion of a computation unaffected by an improvement limits the overall speedup, particularly when adding parallel processors.
amdahls-lawAmortized AnalysisAmortized analysis bounds the total cost of a sequence of operations, giving per-operation guarantees without assuming a probability distribution over inputs.
amortized-analysisApproximation AlgorithmAn approximation algorithm efficiently finds feasible solutions to optimization problems with mathematically proven bounds on their distance from optimality.
approximation-algorithmArithmetic codingArithmetic coding is a lossless compression technique that represents a sequence of symbols through successive subdivisions of a probability interval.
arithmetic-codingArray (Data Structure)An array is an indexed collection of elements, typically stored at regularly spaced memory locations for efficient direct access.
array-data-structureAutomated Theorem ProvingAutomated theorem proving uses computational methods to establish logical consequences of formally stated axioms, supporting mathematics, verification, and machine reasoning.
automated-theorem-provingB-treeA B-tree is a balanced multiway search tree that maintains sorted data and supports efficient searching, insertion, deletion, and external-memory access.
b-treeBeam SearchBeam search is a heuristic search algorithm that retains a limited number of promising partial solutions at each step, trading search coverage for lower computational cost.
beam-searchBellman–Ford AlgorithmThe Bellman–Ford algorithm computes single-source shortest paths in weighted graphs with negative edges and detects negative-weight cycles reachable from the source.
bellman-ford-algorithmBig-Omega NotationBig-Omega notation expresses an asymptotic lower bound on a function, commonly used to describe computational resource requirements as input size grows.
big-omega-notationBig-Theta NotationBig-Theta notation describes an asymptotically tight bound on a function’s growth, ignoring constant factors and behavior on sufficiently small inputs.
big-theta-notationBinary HeapA binary heap is a complete binary tree with an ordering constraint that supports efficient access to and removal of the minimum or maximum element.
binary-heapBinary SearchBinary search locates a value or boundary in an ordered search space by repeatedly eliminating approximately half the remaining candidates.
binary-searchBinary Search TreeA binary search tree maintains keys in hierarchical order, supporting search, updates, and ordered queries with efficiency determined by its height.
binary-search-treeBinary treeA binary tree is a rooted data structure in which each node has at most two distinguished children, supporting searching, priority queues, expression processing, and hierarchical computation.
binary-treeBitA bit is a binary digit and a unit of information, fundamental to digital computing, storage, and communication.
bitBM25BM25 is a probabilistically motivated text-ranking model that combines term rarity, term-frequency saturation, and document-length normalization to estimate relevance to a query.
bm25Boolean Satisfiability ProblemThe Boolean satisfiability problem asks whether a Boolean formula has a truth assignment that makes it true, linking computational complexity with practical automated reasoning.
boolean-satisfiability-problemBreadth-First SearchBreadth-first search explores a graph in successive distance layers, finding shortest paths when every edge has equal cost.
breadth-first-searchByte-pair encodingByte-pair encoding is a repeated pair-substitution algorithm used for lossless compression and, in adapted form, for learning subword vocabularies in language processing.
byte-pair-encodingChurch–Turing ThesisThe Church–Turing thesis identifies effectively calculable functions with those computable by a Turing machine, linking informal algorithms to a precise mathematical model.
church-turing-thesisComplexity ClassA complexity class groups computational problems by the resources and computational models required to solve them.
complexity-classComputability TheoryComputability theory studies which problems algorithms can solve and classifies the mathematical limits and degrees of unsolvability.
computability-theoryComputational ComplexityComputational complexity studies the resources required to solve computational problems and the limits of efficient computation.
computational-complexityComputational GeometryComputational geometry studies algorithms and data structures for representing, analyzing, and manipulating geometric objects, with applications in spatial search, graphics, engineering, and robotics.
computational-geometryComputer ScienceComputer science studies computation, algorithms, information processing, and the principles underlying software and computer systems.
computer-scienceDamerau–Levenshtein DistanceDamerau–Levenshtein distance measures the minimum number of insertions, deletions, substitutions, and adjacent transpositions needed to transform one string into another.
damerau-levenshtein-distanceData compressionData compression encodes information using fewer bits, either preserving the original exactly or allowing controlled loss to reduce storage and transmission requirements.
data-compressionData StructureA data structure organizes information and its relationships to support efficient access, modification, and processing in computer programs.
data-structureDepth-first SearchDepth-first search traverses a graph or tree by exploring each branch as far as possible before backtracking to explore alternatives.
depth-first-searchDijkstra's AlgorithmDijkstra’s algorithm computes shortest paths in graphs with nonnegative edge weights by repeatedly finalizing the nearest unsettled vertex.
dijkstra-algorithmDistributed ConsensusDistributed consensus enables independent computing processes to agree on a common decision despite failures, communication delays, or malicious behavior.
distributed-consensusDivide and ConquerAn algorithm-design paradigm that solves a problem by decomposing it into smaller problems and combining their solutions.
divide-and-conquerDynamic ArrayA dynamic array is a resizable sequence that combines constant-time indexed access with efficient amortized insertion at its end.
dynamic-arrayDynamic programmingA mathematical and computational method that solves structured problems by combining and reusing solutions to subproblems.
dynamic-programmingEdit DistanceEdit distance measures the minimum cost of transforming one sequence into another using specified operations, such as insertions, deletions, and substitutions.
edit-distanceError-correcting codeAn error-correcting code adds structured redundancy to data so that a decoder can recover information despite certain transmission or storage errors.
error-correcting-codeExponential Time HypothesisThe Exponential Time Hypothesis conjectures that deciding satisfiability of 3-CNF Boolean formulas requires exponential time in the number of variables in the worst case.
exponential-time-hypothesisEXPTIMEEXPTIME is the class of decision problems solvable by a deterministic algorithm in time exponential in a polynomial of the input length.
exptimeFinite-State MachineA finite-state machine models computation or control using finitely many states and rules for changing state in response to inputs.
finite-state-machineFisher–Yates shuffleThe Fisher–Yates shuffle generates a uniformly random permutation of a finite sequence, using a linear-time, in-place procedure in its modern form.
fisher-yates-shuffleFloyd–Warshall AlgorithmThe Floyd–Warshall algorithm computes shortest-path distances between all pairs of vertices in a weighted graph using dynamic programming.
floyd-warshall-algorithmFormal LanguageA formal language is a precisely defined set of symbol strings, studied through grammars, automata, algebra, logic, and computation.
formal-languageGame TreeA game tree represents possible sequences of moves and outcomes, supporting the analysis of strategic decisions and computer game-playing algorithms.
game-treeGreedy AlgorithmA greedy algorithm constructs a solution through locally preferred choices, yielding an optimum when the problem’s structure makes those choices globally safe.
greedy-algorithmGrover's AlgorithmGrover’s algorithm finds marked items in an unstructured search space using quadratically fewer oracle queries than classical search.
grovers-algorithmH.264/AVCH.264/AVC is a video compression standard combining predictive coding, transform coding, and entropy coding for broadcasting, recording, and network delivery.
h264-avcHalting ProblemThe halting problem asks whether a program terminates on a given input; no algorithm can answer correctly for every program and input.
halting-problemHamming DistanceHamming distance counts the positions at which two equal-length sequences differ, providing a fundamental measure for error-correcting codes and comparisons of discrete data.
hamming-distanceHash FunctionA hash function maps data to compact values for efficient lookup, comparison, distribution, and, with suitable security properties, cryptographic protection.
hash-function