aiwiki.page
English

Algorithms & Theory

141 entriesPage 1 of 3
2-SAT

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-sat
3SUM problem

The 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-problem
A* Search

A* 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-search
Abstract Data Type

An abstract data type specifies values and operations by their observable behavior, independently of their concrete representation or implementation.

abstract-data-type
Additive white Gaussian noise channel

An 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-channel
Adjacency List

An adjacency list represents a graph by associating each vertex with a collection of its neighboring vertices or incident edges.

adjacency-list
Alan Turing

Alan Turing was a British mathematician and codebreaker whose work established foundations of computer science, artificial intelligence, and mathematical biology.

alan-turing
Algorithm

An algorithm is a precisely specified procedure for performing a computation or solving a class of problems.

algorithm
Aliasing

Aliasing is the indistinguishability of different signals after sampling, producing false frequencies or patterns; in programming, it also means multiple references to the same storage.

aliasing
Alpha–Beta Pruning

Alpha–beta pruning accelerates minimax game-tree search by eliminating branches that cannot affect the root value.

alpha-beta-pruning
Amdahl's law

Amdahl’s law describes how the portion of a computation unaffected by an improvement limits the overall speedup, particularly when adding parallel processors.

amdahls-law
Amortized Analysis

Amortized analysis bounds the total cost of a sequence of operations, giving per-operation guarantees without assuming a probability distribution over inputs.

amortized-analysis
Approximation Algorithm

An approximation algorithm efficiently finds feasible solutions to optimization problems with mathematically proven bounds on their distance from optimality.

approximation-algorithm
Arithmetic coding

Arithmetic coding is a lossless compression technique that represents a sequence of symbols through successive subdivisions of a probability interval.

arithmetic-coding
Array (Data Structure)

An array is an indexed collection of elements, typically stored at regularly spaced memory locations for efficient direct access.

array-data-structure
Automated Theorem Proving

Automated theorem proving uses computational methods to establish logical consequences of formally stated axioms, supporting mathematics, verification, and machine reasoning.

automated-theorem-proving
B-tree

A B-tree is a balanced multiway search tree that maintains sorted data and supports efficient searching, insertion, deletion, and external-memory access.

b-tree
Beam Search

Beam 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-search
Bellman–Ford Algorithm

The 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-algorithm
Big-Omega Notation

Big-Omega notation expresses an asymptotic lower bound on a function, commonly used to describe computational resource requirements as input size grows.

big-omega-notation
Big-Theta Notation

Big-Theta notation describes an asymptotically tight bound on a function’s growth, ignoring constant factors and behavior on sufficiently small inputs.

big-theta-notation
Binary Heap

A 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-heap
Binary Search

Binary search locates a value or boundary in an ordered search space by repeatedly eliminating approximately half the remaining candidates.

binary-search
Binary Search Tree

A binary search tree maintains keys in hierarchical order, supporting search, updates, and ordered queries with efficiency determined by its height.

binary-search-tree
Binary tree

A 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-tree
Bit

A bit is a binary digit and a unit of information, fundamental to digital computing, storage, and communication.

bit
BM25

BM25 is a probabilistically motivated text-ranking model that combines term rarity, term-frequency saturation, and document-length normalization to estimate relevance to a query.

bm25
Boolean Satisfiability Problem

The 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-problem
Breadth-First Search

Breadth-first search explores a graph in successive distance layers, finding shortest paths when every edge has equal cost.

breadth-first-search
Byte-pair encoding

Byte-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-encoding
Church–Turing Thesis

The Church–Turing thesis identifies effectively calculable functions with those computable by a Turing machine, linking informal algorithms to a precise mathematical model.

church-turing-thesis
Complexity Class

A complexity class groups computational problems by the resources and computational models required to solve them.

complexity-class
Computability Theory

Computability theory studies which problems algorithms can solve and classifies the mathematical limits and degrees of unsolvability.

computability-theory
Computational Complexity

Computational complexity studies the resources required to solve computational problems and the limits of efficient computation.

computational-complexity
Computational Geometry

Computational geometry studies algorithms and data structures for representing, analyzing, and manipulating geometric objects, with applications in spatial search, graphics, engineering, and robotics.

computational-geometry
Computer Science

Computer science studies computation, algorithms, information processing, and the principles underlying software and computer systems.

computer-science
Damerau–Levenshtein Distance

Damerau–Levenshtein distance measures the minimum number of insertions, deletions, substitutions, and adjacent transpositions needed to transform one string into another.

damerau-levenshtein-distance
Data compression

Data compression encodes information using fewer bits, either preserving the original exactly or allowing controlled loss to reduce storage and transmission requirements.

data-compression
Data Structure

A data structure organizes information and its relationships to support efficient access, modification, and processing in computer programs.

data-structure
Depth-first Search

Depth-first search traverses a graph or tree by exploring each branch as far as possible before backtracking to explore alternatives.

depth-first-search
Dijkstra's Algorithm

Dijkstra’s algorithm computes shortest paths in graphs with nonnegative edge weights by repeatedly finalizing the nearest unsettled vertex.

dijkstra-algorithm
Distributed Consensus

Distributed consensus enables independent computing processes to agree on a common decision despite failures, communication delays, or malicious behavior.

distributed-consensus
Divide and Conquer

An algorithm-design paradigm that solves a problem by decomposing it into smaller problems and combining their solutions.

divide-and-conquer
Dynamic Array

A dynamic array is a resizable sequence that combines constant-time indexed access with efficient amortized insertion at its end.

dynamic-array
Dynamic programming

A mathematical and computational method that solves structured problems by combining and reusing solutions to subproblems.

dynamic-programming
Edit Distance

Edit distance measures the minimum cost of transforming one sequence into another using specified operations, such as insertions, deletions, and substitutions.

edit-distance
Error-correcting code

An error-correcting code adds structured redundancy to data so that a decoder can recover information despite certain transmission or storage errors.

error-correcting-code
Exponential Time Hypothesis

The 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-hypothesis
EXPTIME

EXPTIME is the class of decision problems solvable by a deterministic algorithm in time exponential in a polynomial of the input length.

exptime
Finite-State Machine

A finite-state machine models computation or control using finitely many states and rules for changing state in response to inputs.

finite-state-machine
Fisher–Yates shuffle

The 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-shuffle
Floyd–Warshall Algorithm

The Floyd–Warshall algorithm computes shortest-path distances between all pairs of vertices in a weighted graph using dynamic programming.

floyd-warshall-algorithm
Formal Language

A formal language is a precisely defined set of symbol strings, studied through grammars, automata, algebra, logic, and computation.

formal-language
Game Tree

A game tree represents possible sequences of moves and outcomes, supporting the analysis of strategic decisions and computer game-playing algorithms.

game-tree
Greedy Algorithm

A greedy algorithm constructs a solution through locally preferred choices, yielding an optimum when the problem’s structure makes those choices globally safe.

greedy-algorithm
Grover's Algorithm

Grover’s algorithm finds marked items in an unstructured search space using quadratically fewer oracle queries than classical search.

grovers-algorithm
H.264/AVC

H.264/AVC is a video compression standard combining predictive coding, transform coding, and entropy coding for broadcasting, recording, and network delivery.

h264-avc
Halting Problem

The halting problem asks whether a program terminates on a given input; no algorithm can answer correctly for every program and input.

halting-problem
Hamming Distance

Hamming 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-distance
Hash Function

A hash function maps data to compact values for efficient lookup, comparison, distribution, and, with suitable security properties, cryptographic protection.

hash-function