The NIST ''Dictionary of Algorithms and Data Structures'' is a reference work maintained by the U.S.

National Institute of Standards and Technology The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into Outline of p ...

. It defines a large number of terms relating to algorithms and data structures. For algorithms and data structures not necessarily mentioned here, see list of algorithms and list of data structures. This list of terms was originally derived from the index of that document, and is in the public domain, as it was compiled by a Federal Government employee as part of a Federal Government work. Some of the terms defined are: __NOTOC__

A

absolute performance guarantee In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solut ...

abstract data type In computer science, an abstract data type (ADT) is a mathematical model for data types. An abstract data type is defined by its behavior (semantics) from the point of view of a '' user'', of the data, specifically in terms of possible values, po ...

(ADT) *

(a,b)-tree In computer science, an (a,b) tree is a kind of balanced search tree. An (a,b)-tree has all of its leaves at the same depth, and all internal nodes except for the root have between and children, where and are integers such that . The root has, ...

* accepting state * Ackermann's function *

active data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...

* acyclic directed graph * adaptive heap sort * adaptive Huffman coding *

adaptive k-d tree An adaptive k-d tree is a tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with sec ...

* adaptive sort *

address-calculation sort In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', also ...

adjacency list In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This i ...

representation *

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple ...

representation *

adversary An adversary is generally considered to be a person, group, or force that opposes and/or attacks. Adversary may also refer to: * Satan ("adversary" in Hebrew), in Judeo-Christian religion Entertainment Fiction * Adversary (comics), villain fr ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

algorithm BSTW The Algorithm BSTW is a data compression algorithm, named after its designers, Bentley, Sleator, Tarjan and Wei in 1986. BSTW is a dictionary-based algorithm that uses a move-to-front transform to keep recently seen dictionary entries at the fro ...

* algorithm FGK *

algorithmic efficiency In computer science, algorithmic efficiency is a property of an algorithm which relates to the amount of computational resources used by the algorithm. An algorithm must be analyzed to determine its resource usage, and the efficiency of an al ...

* algorithmically solvable *

algorithm V Adaptive Huffman coding (also called Dynamic Huffman coding) is an adaptive coding technique based on Huffman coding. It permits building the code as the symbols are being transmitted, having no initial knowledge of source distribution, that allows ...

all pairs shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between tw ...

alphabet An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a s ...

Alpha Skip Search algorithm Alpha (uppercase , lowercase ; grc, ἄλφα, ''álpha'', or ell, άλφα, álfa) is the first letter of the Greek alphabet. In the system of Greek numerals, it has a value of one. Alpha is derived from the Phoenician letter aleph , whic ...

alternating path Alternating may refer to: Mathematics * Alternating algebra, an algebra in which odd-grade elements square to zero * Alternating form, a function formula in algebra * Alternating group, the group of even permutations of a finite set * Alternati ...

alternating Turing machine In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. ...

* alternation *

American flag sort An American flag sort is an efficient, in-place variant of radix sort that distributes items into buckets. Non-comparative sorting algorithms such as radix sort and American flag sort are typically used to sort large objects such as strings, for ...

amortized cost In accounting, an economic item's historical cost is the original nominal monetary value of that item. Historical cost accounting involves reporting assets and liabilities at their historical costs, which are not updated for changes in the items' ...

* ancestor * and *

American National Standards Institute The American National Standards Institute (ANSI ) is a private non-profit organization that oversees the development of voluntary consensus standards for products, services, processes, systems, and personnel in the United States. The organ ...

(ANSI) *

antichain In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its w ...

antisymmetric relation In mathematics, a binary relation R on a set X is antisymmetric if there is no pair of ''distinct'' elements of X each of which is related by R to the other. More formally, R is antisymmetric precisely if for all a, b \in X, \text \,aRb\, \te ...

* AP * Apostolico–Crochemore * Apostolico–Giancarlo algorithm *

approximate string matching In computer science, approximate string matching (often colloquially referred to as fuzzy string searching) is the technique of finding strings that match a pattern approximately (rather than exactly). The problem of approximate string matching ...

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...

* arborescence *

arithmetic coding Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a string of characters is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic ...

array An array is a systematic arrangement of similar objects, usually in rows and columns. Things called an array include: {{TOC right Music * In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...

array index In computer science, an array is a data structure consisting of a collection of ''elements'' (values or variables), each identified by at least one ''array index'' or ''key''. An array is stored such that the position of each element can be co ...

array merging In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same i ...

array search In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with eith ...

articulation point Articulation may refer to: Linguistics * Articulatory phonetics, the study of how humans produce speech sounds via the interaction of physiological structures ** Manner of articulation, how speech organs involved in making a sound make contact * ...

A* search algorithm A* (pronounced "A-star") is a graph traversal and path search algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its O(b^d) space complexity, ...

assignment problem The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows: :The problem instance has a number of ''agents'' and a number of ''tasks''. Any agent can be assigned to perform any t ...

* association list *

associative In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...

associative array In computer science, an associative array, map, symbol table, or dictionary is an abstract data type that stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection. In mathematical terms an ...

* asymptotically tight bound * asymptotic bound * asymptotic lower bound * asymptotic space complexity *

asymptotic time complexity In computational complexity theory, asymptotic computational complexity is the usage of asymptotic analysis for the estimation of computational complexity of algorithms and computational problems, commonly associated with the usage of the big O nota ...

* asymptotic upper bound *

augmenting path In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations res ...

automaton An automaton (; plural: automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions.Automaton – Definition and More ...

* average case *

average-case cost In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...

* AVL tree * axiomatic semantics

B

backtracking Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...

* bag *

Baillie–PSW primality test The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines whether a number is composite or is a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff. The Bailli ...

* balanced binary search tree *

balanced binary tree In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donald ...

* balanced k-way merge sort * balanced merge sort * balanced multiway merge * balanced multiway tree *

balanced quicksort Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...

* balanced tree *

balanced two-way merge sort In telecommunications and professional audio, a balanced line or balanced signal pair is a circuit consisting of two conductors of the same type, both of which have equal impedances along their lengths and equal impedances to ground and to other ci ...

* BANG file *

Batcher sort Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of O(n\log^2(n)) comparators and have ...

Baum Welch algorithm Baum is a German surname meaning "tree" (not to be confused with the French surname Baume). Notable people with this surname include: * Bernie Baum (1929–1993), American songwriter * Carol Baum, American film producer * Christina Baum (bor ...

* BB α tree * BDD * BD-tree *

Bellman–Ford algorithm The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it i ...

Benford's law Benford's law, also known as the Newcomb–Benford law, the law of anomalous numbers, or the first-digit law, is an observation that in many real-life sets of numerical data, the leading digit is likely to be small.Arno Berger and Theodore P ...

* best case * best-case cost *

best-first search Best-first search is a class of search algorithms, which explore a graph by expanding the most promising node chosen according to a specified rule. Judea Pearl described the best-first search as estimating the promise of node ''n'' by a "heuristic ...

biconnected component In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks ...

biconnected graph In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices. The property of being ...

bidirectional bubble sort Cocktail shaker sort, also known as bidirectional bubble sort, cocktail sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuffle sort, or shuttle sort, is an extension of bubble sort. The algorithm extends bub ...

big-O notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Land ...

binary function In mathematics, a binary function (also called bivariate function, or function of two variables) is a function that takes two inputs. Precisely stated, a function f is binary if there exists sets X, Y, Z such that :\,f \colon X \times Y \rightar ...

binary GCD algorithm The binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, is an algorithm that computes the greatest common divisor of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conv ...

binary heap A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort. A binary ...

binary insertion sort Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Howev ...

binary knapsack problem The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit an ...

* binary priority queue *

binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...

binary search In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...

binary search tree In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and ...

binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binar ...

* binary tree representation of trees *

bingo sort In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(''n''2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is not ...

* binomial heap * binomial tree * bin packing problem * bin sort *

bintree Bintree is a village and civil parish in Norfolk, England, about nine miles (14 km) south-east of Fakenham. According to the 2001 census it had a population of 300, increasing to 329 at the 2011 Census. For the purposes of local government ...

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

bipartite matching In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem. Definit ...

* bisector *

bitonic sort Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of O(n\log^2(n)) comparators and have ...

bit vector A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level p ...

Bk tree A BK-tree is a metric tree suggested by Walter Austin Burkhard and Robert M. Keller specifically adapted to discrete metric spaces. For simplicity, consider integer discrete metric d(x,y). Then, BK-tree is defined in the following way. An arbitrar ...

* bdk tree (not to be confused with k-d-B-tree) *

block Block or blocked may refer to: Arts, entertainment and media Broadcasting * Block programming, the result of a programming strategy in broadcasting * W242BX, a radio station licensed to Greenville, South Carolina, United States known as ''96.3 ...

block addressing index Block or blocked may refer to: Arts, entertainment and media Broadcasting * Block programming, the result of a programming strategy in broadcasting * W242BX, a radio station licensed to Greenville, South Carolina, United States known as ''96.3 ...

blocking flow Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz. The algorithm runs in O(V^2 E) ti ...

block search In computer science, a jump search or block search refers to a search algorithm for ordered lists. It works by first checking all items ''L'km'', where k \in \mathbb and ''m'' is the block size, until an item is found that is larger than the sea ...

Bloom filter A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in ...

blossom (graph theory) In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph.) is a Graph (discrete mathematics), graph with vertices in which every subgraph of vertices has a perfect matching. (A perfect matching in a graph is a ...

bogosort In computer science, bogosort (also known as permutation sort, stupid sort, slowsort or bozosort) is a sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one t ...

* boogol *

boolean Any kind of logic, function, expression, or theory based on the work of George Boole is considered Boolean. Related to this, "Boolean" may refer to: * Boolean data type, a form of data with only two possible values (usually "true" and "false" ...

boolean expression In computer science, a Boolean expression is an expression used in programming languages that produces a Boolean value when evaluated. A Boolean value is either true or false. A Boolean expression may be composed of a combination of the Boolean con ...

boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ...

bottleneck traveling salesman The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. The problem is to find the Hamiltonian cycle (visiting each node exactly once) in a weighted graph which minimizes the weight of t ...

* bottom-up tree automaton * boundary-based representation * bounded error probability in polynomial time *

bounded queue In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. By convention, ...

bounded stack In computer science, a stack is an abstract data type that serves as a collection of elements, with two main operations: * Push, which adds an element to the collection, and * Pop, which removes the most recently added element that was not y ...

Bounding volume hierarchy A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects, that form the leaf nodes of the tree, are wrapped in bounding volumes. These nodes are then grouped as small sets and enclosed within larg ...

, also referred to as bounding volume tree (BV-tree, BVT) *

Boyer–Moore string-search algorithm In computer science, the Boyer–Moore string-search algorithm is an efficient string-searching algorithm that is the standard benchmark for practical string-search literature. It was developed by Robert S. Boyer and J Strother Moore in 1977. ...

* Boyer–Moore–Horspool algorithm * bozo sort *

B+ tree A B+ tree is an m-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children. A B+ tree can be viewed as a B ...

BPP (complexity) In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by ...

* Bradford's law *

branch A branch, sometimes called a ramus in botany, is a woody structural member connected to the central trunk of a tree (or sometimes a shrub). Large branches are known as boughs and small branches are known as twigs. The term '' twig'' usually ...

(as in control flow) *

(as in revision control) *

branch and bound Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutio ...

breadth-first search Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next d ...

Bresenham's line algorithm Bresenham's line algorithm is a line drawing algorithm that determines the points of an ''n''-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw li ...

* brick sort *

bridge A bridge is a structure built to span a physical obstacle (such as a body of water, valley, road, or rail) without blocking the way underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually somethi ...

* British Museum algorithm *

brute-force attack In cryptography, a brute-force attack consists of an attacker submitting many passwords or passphrases with the hope of eventually guessing correctly. The attacker systematically checks all possible passwords and passphrases until the correct ...

brute-force search In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the soluti ...

brute-force string search In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the soluti ...

* brute-force string search with mismatches *

BSP-tree In computer science, binary space partitioning (BSP) is a method for space partitioning which recursively subdivides a Euclidean space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to a represent ...

* B*-tree *

B-tree In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for ...

bubble sort Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passes ...

bucket A bucket is typically a watertight, vertical cylinder or truncated cone or square, with an open top and a flat bottom, attached to a semicircular carrying handle called the ''bail''. A bucket is usually an open-top container. In contrast, a p ...

bucket array Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the b ...

bucketing method A bucket shop is a business that allows gambling based on the prices of stocks or commodities. A 1906 U.S. Supreme Court ruling defined a ''bucket shop'' as "an establishment, nominally for the transaction of a stock exchange business, or business ...

bucket sort Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the b ...

bucket trie In computer science, radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process i ...

buddy system The buddy system is a procedure in which two individuals, the "buddies", operate together as a single unit so that they are able to monitor and help each other. As per Merriam-Webster, the first known use of the phrase "buddy system" goes as far ...

buddy tree Buddy may refer to: People *Buddy (nickname) *Buddy (rapper), real name Simmie Sims III (1993–Present) *Buddy Rogers (wrestler), ring name of American professional wrestler Herman Gustav Rohde, Jr. (1921–1992) *Buddy Boeheim (born 1999), Amer ...

* build-heap *

Burrows–Wheeler transform The Burrows–Wheeler transform (BWT, also called block-sorting compression) rearranges a character string into runs of similar characters. This is useful for compression, since it tends to be easy to compress a string that has runs of repeated c ...

(BWT) * busy beaver *

Byzantine generals A Byzantine fault (also Byzantine generals problem, interactive consistency, source congruency, error avalanche, Byzantine agreement problem, and Byzantine failure) is a condition of a computer system, particularly distributed computing systems, ...

C

cactus stack In computer science, an in-tree or parent pointer tree is an -ary tree data structure in which each node has a pointer to its parent node, but no pointers to child nodes. When used to implement a set of stacks, the structure is called a spaghetti ...

* Calculus of Communicating Systems (CCS) * calendar queue *

candidate consistency testing A candidate, or nominee, is the prospective recipient of an award or honor, or a person seeking or being considered for some kind of position; for example: * to be elected to an office — in this case a candidate selection procedure occurs. * t ...

candidate verification A candidate, or nominee, is the prospective recipient of an award or honor, or a person seeking or being considered for some kind of position; for example: * to be elected to an office — in this case a candidate selection procedure occurs. * t ...

canonical complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms ...

capacitated facility location The study of facility location problems (FLP), also known as location analysis, is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering fact ...

* capacity *

capacity constraint Capacity or capacities may refer to: Mathematics, science, and engineering * Capacity of a container, closely related to the volume of the container * Capacity of a set, in Euclidean space, the total charge a set can hold while maintaining a giv ...

Cartesian tree In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely defined from the properties that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the original sequence. ...

cascade merge sort Cascade merge sort is similar to the polyphase merge sort A polyphase merge sort is a variation of a bottom-up merge sort that sorts a list using an initial uneven distribution of sub-lists (runs), primarily used for external sorting, and is more ...

* caverphone * Cayley–Purser algorithm *

C curve C, or c, is the third letter in the Latin alphabet, used in the modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is ''cee'' (pronounced ), plural ''cees''. History "C" ...

cell probe model Cell most often refers to: * Cell (biology), the functional basic unit of life Cell may also refer to: Locations * Monastic cell, a small room, hut, or cave in which a religious recluse lives, alternatively the small precursor of a monastery w ...

cell tree Cell most often refers to: * Cell (biology), the functional basic unit of life Cell may also refer to: Locations * Monastic cell, a small room, hut, or cave in which a religious recluse lives, alternatively the small precursor of a monastery w ...

cellular automaton A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tess ...

centroid In mathematics and physics, the centroid, also known as geometric center or center of figure, of a plane figure or solid figure is the arithmetic mean position of all the points in the surface of the figure. The same definition extends to any ...

certificate Certificate may refer to: * Birth certificate * Marriage certificate * Death certificate * Gift certificate * Certificate of authenticity, a document or seal certifying the authenticity of something * Certificate of deposit, or CD, a financial pro ...

chain (order theory) In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexiv ...

* chaining (algorithm) * child *

Chinese postman problem In graph theory, a branch of mathematics and computer science, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undi ...

Chinese remainder theorem In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of the ...

Christofides algorithm The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle ine ...

Christofides heuristic The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle ine ...

chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

Church–Turing thesis In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a thesis about the nature of co ...

circuit Circuit may refer to: Science and technology Electrical engineering * Electrical circuit, a complete electrical network with a closed-loop giving a return path for current ** Analog circuit, uses continuous signal levels ** Balanced circu ...

circuit complexity In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the ci ...

* circuit value problem * circular list *

circular queue In computer science, a circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams. There ...

clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popula ...

clique problem In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cliq ...

* clustering (see

hash table In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', ...

) *

clustering free Clustering can refer to the following: In computing: *Computer cluster, the technique of linking many computers together to act like a single computer *Data cluster, an allocation of contiguous storage in databases and file systems *Cluster analys ...

* coalesced hashing * coarsening *

cocktail shaker sort Cocktail shaker sort, also known as bidirectional bubble sort, cocktail sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuffle sort, or shuttle sort, is an extension of bubble sort. The algorithm extends bub ...

codeword In communication, a code word is an element of a standardized code or protocol. Each code word is assembled in accordance with the specific rules of the code and assigned a unique meaning. Code words are typically used for reasons of reliability ...

* coding tree * collective recursion *

collision In physics, a collision is any event in which two or more bodies exert forces on each other in a relatively short time. Although the most common use of the word ''collision'' refers to incidents in which two or more objects collide with great fo ...

collision resolution scheme In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', ...

* Colussi *

combination In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are th ...

comb sort Comb sort is a relatively simple sorting algorithm originally designed by Włodzimierz Dobosiewicz and Artur Borowy in 1980, later rediscovered (and given the name "Combsort") by Stephen Lacey and Richard Box in 1991. Comb sort improves on bubble ...

Communicating Sequential Processes In computer science, communicating sequential processes (CSP) is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or ...

commutative In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name o ...

compact DAWG In computer science, a deterministic acyclic finite state automaton (DAFSA),Jan Daciuk, Stoyan Mihov, Bruce Watson and Richard Watson (2000). Incremental construction of minimal acyclic finite state automata. Computational Linguistics 26(1):3-16. ...

* compact trie *

comparison sort A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should oc ...

* competitive analysis * competitive ratio *

complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-clas ...

* complete binary tree *

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...

completely connected graph Completely may refer to: * ''Completely'' (Diamond Rio album) * ''Completely'' (Christian Bautista album), 2005 * "Completely", a song by American singer and songwriter Michael Bolton * "Completely", a song by Shane Filan from '' Love Always'', ...

complete tree Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies ...

complexity Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence. The term is generally used to c ...

complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms ...

* computable *

concave function In mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap, or upper convex. Definition A real-valued function f on an ...

* concurrent flow * concurrent read, concurrent write * concurrent read, exclusive write *

configuration Configuration or configurations may refer to: Computing * Computer configuration or system configuration * Configuration file, a software file used to configure the initial settings for a computer program * Configurator, also known as choice boar ...

confluently persistent data structure In computing, a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (vi ...

conjunction Conjunction may refer to: * Conjunction (grammar), a part of speech * Logical conjunction, a mathematical operator ** Conjunction introduction, a rule of inference of propositional logic * Conjunction (astronomy), in which two astronomical bodies ...

* connected components *

connected graph In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgra ...

co-NP In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precise ...

constant function In mathematics, a constant function is a function whose (output) value is the same for every input value. For example, the function is a constant function because the value of is 4 regardless of the input value (see image). Basic properti ...

* continuous knapsack problem * Cook reduction * Cook's theorem *

counting sort In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small positive integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that possess d ...

* covering *

CRCW In computer science, a parallel random-access machine (parallel RAM or PRAM) is a shared-memory abstract machine. As its name indicates, the PRAM is intended as the parallel-computing analogy to the random-access machine (RAM) (not to be confused ...

* Crew (algorithm) *

critical path problem Critical or Critically may refer to: *Critical, or critical but stable, medical states **Critical, or intensive care medicine *Critical juncture, a discontinuous change studied in the social sciences. *Critical Software, a company specializing in ...

CSP CSP may refer to: Education * College Student Personnel, an academic discipline * Commonwealth Supported Place, a category in Australian education * Concordia University (Saint Paul, Minnesota), US Organizations * Caledonian Steam Packet Compa ...

(communicating sequential processes) *

(constraint satisfaction problem) * CTL *

cuckoo hashing Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table, with worst-case constant lookup time. The name derives from the behavior of some species of cuckoo, where the cuckoo chick p ...

cut (graph theory) In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connec ...

* cut (logic programming) * cutting plane * cutting stock problem *

cutting theorem Cutting is the separation or opening of a physical object, into two or more portions, through the application of an acutely directed force. Implements commonly used for cutting are the knife and saw, or in medicine and science the scalpel an ...

* cut vertex * cycle sort * cyclic redundancy check (CRC)

D

* D-adjacent *

DAG shortest paths In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between ...

Damerau–Levenshtein distance In information theory and computer science, the Damerau–Levenshtein distance (named after Frederick J. Damerau and Vladimir I. Levenshtein.) is a string metric for measuring the edit distance between two sequences. Informally, the Damerau–Leve ...

data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the rel ...

* decidable *

decidable language In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of t ...

* decimation *

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

decision tree A decision tree is a decision support tool that uses a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm that only contains co ...

decomposable searching problem Decomposition or rot is the process by which dead organic substances are broken down into simpler organic or inorganic matter such as carbon dioxide, water, simple sugars and mineral salts. The process is a part of the nutrient cycle and ...

degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathemati ...

* dense graph * depoissonization * depth *

depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alo ...

(DFS) * deque * derangement * descendant (see

tree structure A tree structure, tree diagram, or tree model is a way of representing the hierarchical nature of a structure in a graphical form. It is named a "tree structure" because the classic representation resembles a tree, although the chart is genera ...

) *

deterministic Determinism is a philosophical view, where all events are determined completely by previously existing causes. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping motives and consi ...

deterministic algorithm In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far ...

deterministic finite automata string search In computer science, string-searching algorithms, sometimes called string-matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger strin ...

deterministic finite automaton In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...

(DFA) * deterministic finite state machine *

deterministic finite tree automaton A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines. The following article deals with branching tree automata, which correspond to regular languages o ...

* deterministic pushdown automaton (DPDA) *

deterministic tree automaton A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines. The following article deals with branching tree automata, which correspond to regular languages of ...

Deutsch–Jozsa algorithm The Deutsch–Jozsa algorithm is a deterministic quantum algorithm proposed by David Deutsch and Richard Jozsa in 1992 with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998. Although of little current ...

* DFS forest * DFTA *

diagonalization argument In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument, the anti-diagonal argument, the diagonal method, and Cantor's diagonalization proof, was published in 1891 by Georg Cantor as a ...

diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...

dichotomic search In computer science, a dichotomic search is a search algorithm that operates by selecting between two distinct alternatives (dichotomies) at each step. It is a specific type of divide and conquer algorithm. A well-known example is binary search. ...

* dictionary (data structure) * diet (see ''discrete interval encoding tree'' below) * difference (set theory) * digital search tree *

digital tree In computer science, a trie, also called digital tree or prefix tree, is a type of ''k''-ary search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes de ...

* digraph *

Dijkstra's algorithm Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years ...

* diminishing increment sort * dining philosophers *

direct chaining hashing Direct may refer to: Mathematics * Directed set, in order theory * Direct limit of (pre), sheaves * Direct sum of modules, a construction in abstract algebra which combines several vector spaces Computing * Direct access (disambiguation), ...

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one v ...

(DAG) * directed acyclic word graph (DAWG) *

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...

discrete interval encoding tree Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory *Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit *Discrete group, a ...

* discrete p-center * disjoint set *

disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor ...

distributed algorithm A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientific ...

* distributional complexity *

distribution sort In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is importan ...

divide-and-conquer algorithm In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...

divide and marriage before conquest In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...

division method Division or divider may refer to: Mathematics *Division (mathematics), the inverse of multiplication * Division algorithm, a method for computing the result of mathematical division Military *Division (military), a formation typically consisting ...

* data domain * don't-care term *

Doomsday rule The Doomsday rule, Doomsday algorithm or Doomsday method is an algorithm of determination of the day of the week for a given date. It provides a perpetual calendar because the Gregorian calendar moves in cycles of 400 years. The algorithm for ...

* double-direction bubble sort *

double-ended priority queue In computer science, a double-ended priority queue (DEPQ)double hashing Double hashing is a computer programming technique used in conjunction with open addressing in hash tables to resolve hash collisions, by using a secondary hash of the key as an offset when a collision occurs. Double hashing with open addressing is ...

double left rotation Left rotation refers to the following * In an array, moving all items to the next lower location. The first item is moved to the last location, which is now vacant. * In a list, removing the head and inserting it at the tail. * In machine code ( ...

Double Metaphone Metaphone is a phonetic algorithm, published by Lawrence Philips in 1990, for indexing words by their English pronunciation. It fundamentally improves on the Soundex algorithm by using information about variations and inconsistencies in English sp ...

* double right rotation *

double-ended queue In computer science, a double-ended queue (abbreviated to deque, pronounced ''deck'', like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). ...

doubly linked list In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the se ...

* dragon curve *

dual graph In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loo ...

dual linear program The dual of a given linear program (LP) is another LP that is derived from the original (the primal) LP in the following schematic way: * Each variable in the primal LP becomes a constraint in the dual LP; * Each constraint in the primal LP becomes ...

dyadic tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...

dynamic array In computer science, a dynamic array, growable array, resizable array, dynamic table, mutable array, or array list is a random access, variable-size list data structure that allows elements to be added or removed. It is supplied with standard lib ...

dynamic data structure Dynamics (from Greek δυναμικός ''dynamikos'' "powerful", from δύναμις ''dynamis'' " power") or dynamic may refer to: Physics and engineering * Dynamics (mechanics) ** Aerodynamics, the study of the motion of air ** Analytical dyna ...

* dynamic hashing *

dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. I ...

dynamization transformation In computer science, dynamization is the process of transforming a static data structure into a dynamic one. Although static data structures may provide very good functionality and fast queries, their utility is limited because of their inability ...

E

edge Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed b ...

* eb tree (elastic binary tree) *

edge coloring In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...

edge connectivity In graph theory, a connected graph is -edge-connected if it remains connected whenever fewer than edges are removed. The edge-connectivity of a graph is the largest for which the graph is -edge-connected. Edge connectivity and the enumeration ...

edge crossing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis ...

edge-weighted graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

edit distance In computational linguistics and computer science, edit distance is a string metric, i.e. a way of quantifying how dissimilar two strings (e.g., words) are to one another, that is measured by counting the minimum number of operations required to t ...

* edit operation * edit script *

8 queens The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. There are 92 solutions. ...

* elastic-bucket trie *

element uniqueness In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct. It is a well studied problem in many different models of computation. ...

* end-of-string *

epidemic algorithm An epidemic (from Greek ἐπί ''epi'' "upon or above" and δῆμος ''demos'' "people") is the rapid spread of disease to a large number of patients among a given population within an area in a short period of time. Epidemics of infectiou ...

Euclidean algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an ...

Euclidean distance In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefore o ...

* Euclidean Steiner tree * Euclidean traveling salesman problem * Euclid's algorithm * Euler cycle * Eulerian graph *

Eulerian path In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...

* exact string matching * EXCELL (

extendible cell Extensibility is a software engineering and systems design principle that provides for future growth. Extensibility is a measure of the ability to extend a system and the level of effort required to implement the extension. Extensions can be t ...

) *

exchange sort In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important ...

exclusive or Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...

exclusive read, concurrent write In computer science, a parallel random-access machine (parallel RAM or PRAM) is a shared-memory abstract machine. As its name indicates, the PRAM is intended as the parallel-computing analogy to the random-access machine (RAM) (not to be confus ...

(ERCW) *

exclusive read, exclusive write In computer science, a parallel random-access machine (parallel RAM or PRAM) is a shared-memory abstract machine. As its name indicates, the PRAM is intended as the parallel-computing analogy to the random-access machine (RAM) (not to be confused ...

(EREW) *

exhaustive search In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the soluti ...

* existential state * expandable hashing *

expander graph In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several appli ...

* exponential * extended binary tree *

extended Euclidean algorithm In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's ...

* extended k-d tree * extendible hashing * external index *

external memory algorithm In computing, external memory algorithms or out-of-core algorithms are algorithms that are designed to process data that are too large to fit into a computer's main memory at once. Such algorithms must be optimized to efficiently fetch and access da ...

external memory data structure External may refer to: * External (mathematics), a concept in abstract algebra * Externality In economics, an externality or external cost is an indirect cost or benefit to an uninvolved third party that arises as an effect of another party ...

external merge External sorting is a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in t ...

external merge sort External may refer to: * External (mathematics), a concept in abstract algebra * Externality In economics, an externality or external cost is an indirect cost or benefit to an uninvolved third party that arises as an effect of another party ...

* external node *

external quicksort Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster tha ...

external radix sort External may refer to: * External (mathematics), a concept in abstract algebra * Externality In economics, an externality or external cost is an indirect cost or benefit to an uninvolved third party that arises as an effect of another party ...

* external sort * extrapolation search * extremal *

extreme point In mathematics, an extreme point of a convex set S in a real or complex vector space is a point in S which does not lie in any open line segment joining two points of S. In linear programming problems, an extreme point is also called vertex ...

F

facility location Facility location is a name given to several different problems in computer science and in game theory: * Facility location problem The study of facility location problems (FLP), also known as location analysis, is a branch of operations research ...

* factor (see

substring In formal language theory and computer science, a substring is a contiguous sequence of characters within a string. For instance, "''the best of''" is a substring of "''It was the best of times''". In contrast, "''Itwastimes''" is a subsequence ...

) *

factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) ...

fast fourier transform A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in t ...

(FFT) * fathoming *

feasible region In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potent ...

* feasible solution *

feedback edge set In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks ...

feedback vertex set In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles ("removal" means deleting the vertex and all edges adjacent to it). Equivalently, each FVS conta ...

* Ferguson–Forcade algorithm *

Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a integer sequence, sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start ...

* Fibonacci search * Fibonacci tree * Fibonacci heap * Find * find kth least element * finitary tree * finite Fourier transform (

discrete Fourier transform In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced Sampling (signal processing), samples of a function (mathematics), function into a same-length sequence of equally-spaced samples of the discre ...

) *

finite state automaton A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...

finite-state machine A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number ...

* finite state machine minimization * finite-state transducer *

first come, first served Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...

* first-in, first-out (FIFO) * fixed-grid method *

flash sort Flash, flashes, or FLASH may refer to: Arts, entertainment, and media Fictional aliases * Flash (DC Comics character), several DC Comics superheroes with super speed: ** Flash (Barry Allen) ** Flash (Jay Garrick) ** Wally West, the first Kid ...

flow Flow may refer to: Science and technology * Fluid flow, the motion of a gas or liquid * Flow (geomorphology), a type of mass wasting or slope movement in geomorphology * Flow (mathematics), a group action of the real numbers on a set * Flow (psych ...

* flow conservation * flow function *

flow network In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations re ...

Floyd–Warshall algorithm In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with p ...

* Ford–Bellman algorithm * Ford–Fulkerson algorithm *

forest A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...

forest editing problem A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of s ...

formal methods In computer science, formal methods are mathematically rigorous techniques for the specification, development, and verification of software and hardware systems. The use of formal methods for software and hardware design is motivated by the exp ...

formal verification In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal met ...

forward index Search engine indexing is the collecting, parsing, and storing of data to facilitate fast and accurate information retrieval. Index design incorporates interdisciplinary concepts from linguistics, cognitive psychology, mathematics, informatics, and ...

fractal In mathematics, a fractal is a geometric shape containing detailed structure at arbitrarily small scales, usually having a fractal dimension strictly exceeding the topological dimension. Many fractals appear similar at various scales, as il ...

fractional knapsack problem In theoretical computer science, the continuous knapsack problem (also known as the fractional knapsack problem) is an algorithmic problem in combinatorial optimization in which the goal is to fill a container (the "knapsack") with fractional amount ...

fractional solution A fraction is one or more equal parts of something. Fraction may also refer to: * Fraction (chemistry), a quantity of a substance collected by fractionation * Fraction (floating point number), an (ambiguous) term sometimes used to specify a part ...

* free edge * free list *

free tree In graph theory, a tree is an undirected graph in which any two vertices are connected by ''exactly one'' path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by ''a ...

* free vertex *

frequency count heuristic Frequency is the number of occurrences of a repeating event per unit of time. It is also occasionally referred to as ''temporal frequency'' for clarity, and is distinct from '' angular frequency''. Frequency is measured in hertz (Hz) which is ...

* full array * full binary tree * full inverted index *

fully dynamic graph problem Fully () is a municipality in the district of Martigny in the canton of Valais in Switzerland. History Fully is first mentioned in the 11th Century as ''Fuliacum''. Geography Fully has an area, , of . Of this area, 30.5% is used for agricultu ...

fully persistent data structure In computing, a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (vi ...

fully polynomial approximation scheme A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It r ...

function (programming) In computer programming, a function or subroutine is a sequence of program instructions that performs a specific task, packaged as a unit. This unit can then be used in programs wherever that particular task should be performed. Functions may ...

function (mathematics) In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the func ...

functional data structure In computer science, a purely functional data structure is a data structure that can be implemented in a purely functional language. The main difference between an arbitrary data structure and a purely functional one is that the latter is (stron ...

G

* Galil–Giancarlo * Galil–Seiferas *

gamma function In mathematics, the gamma function (represented by , the capital letter gamma from the Greek alphabet) is one commonly used extension of the factorial function to complex numbers. The gamma function is defined for all complex numbers except th ...

* GBD-tree *

geometric optimization problem Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is ca ...

global optimum In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given r ...

gnome sort Gnome sort (nicknamed stupid sort) is a variation of the insertion sort sorting algorithm that does not use nested loops. Gnome sort was originally proposed by Iranian computer scientist Hamid Sarbazi-Azad (professor of Computer Science and Eng ...

goobi Goobi (Abbr. of ''Göttingen online-objects binaries'') is an open-source software suite intended to support mass digitisation projects for cultural heritage institutions. The software implements international standards such as METS, MODS and oth ...

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

* graph concentration *

graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, car ...

graph isomorphism In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) ...

graph partition In mathematics, a graph partition is the reduction of a graph to a smaller graph by partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the groups will produce edges in the partitioned graph ...

Gray code The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). For example, the representat ...

greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' i ...

(GCD) *

greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locall ...

greedy heuristic A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...

* grid drawing *

grid file In computer science, a grid file or bucket grid is a point access method which splits a space into a non-periodic grid where one or more cells of the grid refer to a small set of points. Grid files (a symmetric data structure) provide an efficie ...

Grover's algorithm In quantum computing, Grover's algorithm, also known as the quantum search algorithm, refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output ...

H

halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a ...

Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

Hamiltonian path In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

Hamming distance In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chang ...

* Harter–Highway dragon *

hash function A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually ...

hash heap Hash, hashes, hash mark, or hashing may refer to: Substances * Hash (food), a coarse mixture of ingredients * Hash, a nickname for hashish, a cannabis product Hash mark *Hash mark (sports), a marking on hockey rinks and gridiron football fiel ...

* hash table delete *

Hausdorff distance In mathematics, the Hausdorff distance, or Hausdorff metric, also called Pompeiu–Hausdorff distance, measures how far two subsets of a metric space are from each other. It turns the set of non-empty compact subsets of a metric space into a metri ...

* hB-tree * head *

heap Heap or HEAP may refer to: Computing and mathematics * Heap (data structure), a data structure commonly used to implement a priority queue * Heap (mathematics), a generalization of a group * Heap (programming) (or free store), an area of memory f ...

heapify In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a ''max heap'', for any given node C, if P is a parent node of C, then the ''key'' (the '' ...

* heap property *

heapsort In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the ...

* heaviest common subsequence *

height Height is measure of vertical distance, either vertical extent (how "tall" something or someone is) or vertical position (how "high" a point is). For example, "The height of that building is 50 m" or "The height of an airplane in-flight is ab ...

height-balanced binary search tree In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donald ...

height-balanced tree In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donald ...

heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediat ...

hidden Markov model A hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process — call it X — with unobservable ("''hidden''") states. As part of the definition, HMM requires that there be an ob ...

highest common factor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...

* Hilbert curve *

histogram sort Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the b ...

* homeomorphic * horizontal visibility map * Huffman encoding *

Hungarian algorithm The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hu ...

hybrid algorithm {{Unreferenced, date=May 2014 A hybrid algorithm is an algorithm that combines two or more other algorithms that solve the same problem, and is mostly used in programming languages like C++, either choosing one (depending on the data), or switching ...

* hyperedge *

hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) ...

I

Identity function Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, unc ...

ideal merge Ideal may refer to: Philosophy * Ideal (ethics), values that one actively pursues as goals * Platonic ideal, a philosophical idea of trueness of form, associated with Plato Mathematics * Ideal (ring theory), special subsets of a ring consider ...

* implication * implies * in-branching *

inclusion–exclusion principle In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as : , A \c ...

inclusive or In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor ...

* incompressible string *

incremental algorithm Increment or incremental may refer to: *Incrementalism, a theory (also used in politics as a synonym for gradualism) *Increment and decrement operators, the operators ++ and -- in computer programming *Incremental computing *Incremental backup, wh ...

* in-degree *

independent set (graph theory) In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the tw ...

* index file *

information theoretic bound Information is an abstract concept that refers to that which has the power to inform. At the most fundamental level information pertains to the interpretation of that which may be sensed. Any natural process that is not completely random, ...

in-place algorithm In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However, a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output ...

in-order traversal In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. ...

* in-place sort *

insertion sort Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Howe ...

* instantaneous description *

integer linear program An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective ...

integer multi-commodity flow An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

integer polyhedron An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

interactive proof system In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a ''prover'' and a ''verifier''. The parties interact by exchanging messages in order t ...

interface Interface or interfacing may refer to: Academic journals * ''Interface'' (journal), by the Electrochemical Society * '' Interface, Journal of Applied Linguistics'', now merged with ''ITL International Journal of Applied Linguistics'' * '' Int ...

* interior-based representation *

internal node In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be con ...

internal sort {{no sources, date=December 2022 An internal sort is any data sorting process that takes place entirely within the main memory of a computer. This is possible whenever the data to be sorted is small enough to all be held in the main memory. like a ...

* interpolation search * interpolation-sequential search * interpolation sort *

intersection (set theory) In set theory, the intersection of two sets A and B, denoted by A \cap B, is the set containing all elements of A that also belong to B or equivalently, all elements of B that also belong to A. Notation and terminology Intersection is writ ...

* interval tree *

intractable Intractable may refer to: * Intractable conflict, a form of complex, severe, and enduring conflict * Intractable pain, pain which cannot be controlled/cured by any known treatment * Intractable problem In theoretical computer science and mathema ...

* introsort * introspective sort *

inverse Ackermann function In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total ...

* inverted file index * inverted index * irreflexive * isomorphic *

iteration Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...

J

Jaro–Winkler distance In computer science and statistics, the Jaro–Winkler distance is a string metric measuring an edit distance between two sequences. It is a variant proposed in 1990 by William E. Winkler of the Jaro distance metric (1989, Matthew A. Jaro). T ...

* Johnson's algorithm * Johnson–Trotter algorithm * jump list * jump search

K

Karmarkar's algorithm Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also po ...

Karnaugh map The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logic ...

* Karp–Rabin string-search algorithm * Karp reduction * k-ary heap * k-ary Huffman encoding * k-ary tree * k-clustering *

k-coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

* k-connected graph * k-d-B-tree (not to be confused with bdk tree) * k-dimensional * K-dominant match *

k-d tree In computer science, a ''k''-d tree (short for ''k-dimensional tree'') is a space-partitioning data structure for organizing points in a ''k''-dimensional space. ''k''-d trees are a useful data structure for several applications, such as sea ...

* key * KMP * KmpSkip Search *

knapsack problem The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit a ...

knight's tour A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again im ...

Knuth–Morris–Pratt algorithm In computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies ...

* Königsberg bridges problem *

Kolmogorov complexity In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that prod ...

* Kraft's inequality *

Kripke structure : ''This article describes Kripke structures as used in model checking. For a more general description, see Kripke semantics''. A Kripke structure is a variation of the transition system, originally proposed by Saul Kripke, used in model checkin ...

Kruskal's algorithm Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. (A minimum spanning tree of a connected graph is a subset of the edges that forms a tree that ...

* kth order Fibonacci numbers * kth shortest path * kth smallest element *

KV diagram The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 ''logi ...

* k-way merge * k-way merge sort *

k-way tree In graph theory, an ''m''-ary tree (also known as ''n''-ary, ''k''-ary or ''k''-way tree) is a rooted tree in which each node has no more than ''m'' children. A binary tree is the special case where ''m'' = 2, and a ternary tree is another ...

L

* labeled graph *

language Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of ...

* last-in, first-out (LIFO) *

Las Vegas algorithm In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the ...

lattice (group) In geometry and group theory, a lattice in the real coordinate space \mathbb^n is an infinite set of points in this space with the properties that coordinate wise addition or subtraction of two points in the lattice produces another lattice poi ...

layered graph Layer or layered may refer to: Arts, entertainment, and media * ''Layers'' (Kungs album) * ''Layers'' (Les McCann album) * ''Layers'' (Royce da 5'9" album) *"Layers", the title track of Royce da 5'9"'s sixth studio album *Layer, a female Maveric ...

LCS LCS may refer to: Schools and organizations * Laboratory for Computer Science, research institute at the Massachusetts Institute of Technology * Lake County Schools school district of Lake County, Florida * Lakefield College School an indepe ...

leaf A leaf (plural, : leaves) is any of the principal appendages of a vascular plant plant stem, stem, usually borne laterally aboveground and specialized for photosynthesis. Leaves are collectively called foliage, as in "autumn foliage", wh ...

least common multiple In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bo ...

(LCM) * leftist tree *

left rotation Left rotation refers to the following * In an array, moving all items to the next lower location. The first item is moved to the last location, which is now vacant. * In a list, removing the head and inserting it at the tail. * In machine code (a ...

* left-child right-sibling binary tree also termed ''first-child next-sibling binary tree'', ''doubly chained tree'', or ''filial-heir chain'' *

Lempel–Ziv–Welch Lempel–Ziv–Welch (LZW) is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch. It was published by Welch in 1984 as an improved implementation of the LZ78 algorithm published by Lempe ...

(LZW) * level-order traversal *

Levenshtein distance In information theory, linguistics, and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-charact ...

lexicographical order In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of ...

linear Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear ...

linear congruential generator A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generat ...

linear hash Linear hashing (LH) is a dynamic data structure which implements a hash table and grows or shrinks one bucket at a time. It was invented by Witold Litwin in 1980. It has been analyzed by Baeza-Yates and Soza-Pollman. It is the first in a numbe ...

linear insertion sort Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Howev ...

linear order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexiv ...

* linear probing *

linear probing sort Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear ...

linear product Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear ...

linear program Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...

* linear quadtree *

linear search In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. A linear search runs in at ...

* link *

linked list In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whi ...

list A ''list'' is any set of items in a row. List or lists may also refer to: People * List (surname) Organizations * List College, an undergraduate division of the Jewish Theological Seminary of America * SC Germania List, German rugby uni ...

list contraction A ''list'' is any set of items in a row. List or lists may also refer to: People * List (surname) Organizations * List College, an undergraduate division of the Jewish Theological Seminary of America * SC Germania List The SC Germania L ...

little-o notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Land ...

Lm distance In mathematical physics, Minkowski space (or Minkowski spacetime) () is a combination of three-dimensional Euclidean space and time into a four-dimensional manifold where the spacetime interval between any two events is independent of the ...

* load factor (computer science) *

local alignment Local may refer to: Geography and transportation * Local (train), a train serving local traffic demand * Local, Missouri, a community in the United States * Local government, a form of public administration, usually the lowest tier of administrat ...

local optimum In applied mathematics and computer science, a local optimum of an optimization problem is a solution that is optimal (either maximal or minimal) within a neighboring set of candidate solutions. This is in contrast to a global optimum, which i ...

logarithm In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 of ...

logarithmic scale A logarithmic scale (or log scale) is a way of displaying numerical data over a very wide range of values in a compact way—typically the largest numbers in the data are hundreds or even thousands of times larger than the smallest numbers. Such a ...

* longest common subsequence * longest common substring * Lotka's law *

lower bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an ele ...

lower triangular matrix In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...

lowest common ancestor In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) of two nodes and in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both and as descendants, where ...

l-reduction In computer science, particularly the study of approximation algorithms, an L-reduction ("''linear reduction''") is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-prese ...

M

* Malhotra–Kumar–Maheshwari blocking flow ( ru.) *

Manhattan distance A taxicab geometry or a Manhattan geometry is a geometry whose usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their Cartesian co ...

many-one reduction In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem L_1 into instances of a second decision problem L_2 where the instan ...

Markov chain A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happen ...

* marriage problem (see

) *

Master theorem (analysis of algorithms) In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides an asymptotic analysis (using Big O notation) for recurrence relations of types that occur in the Analysis of algorithms, analysis of many divide and con ...

matched edge In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem. Definitio ...

* matched vertex *

matching (graph theory) In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem. Definitio ...

matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** '' The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...

* matrix-chain multiplication problem * max-heap property * maximal independent set * maximally connected component *

Maximal Shift Maximal may refer to: *Maximal element, a mathematical definition *Maximal (Transformers), a faction of Transformers *Maximalism, an artistic style *Maximal set * ''Maxim'' (magazine), a men's magazine marketed as ''Maximal'' in several countries ...

* maximum bipartite matching * maximum-flow problem *

MAX-SNP In computational complexity theory, SNP (from Strict NP) is a complexity class containing a limited subset of NP based on its logical characterization in terms of graph-theoretical properties. It forms the basis for the definition of the class Max ...

Mealy machine In the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs. This is in contrast to a Moore machine, whose output values are determined solely by its ...

mean There are several kinds of mean in mathematics, especially in statistics. Each mean serves to summarize a given group of data, often to better understand the overall value ( magnitude and sign) of a given data set. For a data set, the '' ari ...

* median * meld (data structures) *

memoization In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. Memoization ...

merge algorithm Merge algorithms are a family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order. These algorithms are used as subroutines in various sorting ...

merge sort In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same ...

* Merkle tree *

meromorphic function In the mathematical field of complex analysis, a meromorphic function on an open subset ''D'' of the complex plane is a function that is holomorphic on all of ''D'' ''except'' for a set of isolated points, which are poles of the function. ...

metaheuristic In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimizatio ...

* metaphone * midrange *

Miller–Rabin primality test The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen pri ...

* min-heap property * minimal perfect hashing * minimum bounding box (MBB) * minimum cut *

minimum path cover Given a directed graph ''G'' = (''V'', ''E''), a path cover is a set of directed paths such that every vertex ''v'' ∈ ''V'' belongs to at least one path. Note that a path cover may include paths of length 0 (a single ver ...

minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...

* minimum vertex cut *

mixed integer linear program Mixed is the past tense of ''mix''. Mixed may refer to: * Mixed (United Kingdom ethnicity category), an ethnicity category that has been used by the United Kingdom's Office for National Statistics since the 1991 Census * ''Mixed'' (album), a co ...

* mode *

model checking In computer science, model checking or property checking is a method for checking whether a finite-state model of a system meets a given specification (also known as correctness). This is typically associated with hardware or software system ...

model of computation In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes h ...

* moderately exponential
MODIFIND
* monotone priority queue *

monotonically decreasing In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of ord ...

monotonically increasing In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of ord ...

Monte Carlo algorithm In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples of such algorithms are Karger–Stein algorithm and Monte Carlo algorithm for minimum Feedb ...

Moore machine In the theory of computation, a Moore machine is a finite-state machine whose current output values are determined only by its current state. This is in contrast to a Mealy machine, whose output values are determined both by its current state and b ...

* Morris–Pratt * move (

transition) *

move-to-front heuristic The move-to-front (MTF) transform is an encoding of data (typically a stream of bytes) designed to improve the performance of entropy encoding techniques of compression. When efficiently implemented, it is fast enough that its benefits usual ...

* move-to-root heuristic *

multi-commodity flow The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes. Definition Given a flow network \,G(V,E), where edge (u,v) \in E has capacity \,c(u,v). There are \,k co ...

multigraph In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by mo ...

* multilayer grid file *

multiplication method Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being addit ...

* multiprefix *

multiprocessor model Multiprocessing is the use of two or more central processing units (CPUs) within a single computer system. The term also refers to the ability of a system to support more than one processor or the ability to allocate tasks between them. There ar ...

multiset In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that ...

* multi suffix tree * multiway decision * multiway merge * multiway search tree * multiway tree * Munkres' assignment algorithm

N

naive string search In computer science, string-searching algorithms, sometimes called string-matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger strin ...

* nand *

n-ary function Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematic ...

* NC * NC many-one reducibility *

nearest neighbor search Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function ...

negation In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and fals ...

* network flow (see

) * network flow problem * next state *

NIST The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical sc ...

node In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics * Vertex (graph theory), a vertex in a mathematical graph * Vertex (geometry), a point where two or more curves, line ...

* nonbalanced merge * nonbalanced merge sort *

nondeterministic Nondeterminism or nondeterministic may refer to: Computer science * Nondeterministic programming *Nondeterministic algorithm In computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit diffe ...

nondeterministic algorithm In computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave diffe ...

nondeterministic finite automaton In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if * each of its transitions is ''uniquely'' determined by its source state and input symbol, and * reading an input symbol is required for each state t ...

* nondeterministic finite-state machine (NFA) * nondeterministic finite tree automaton (NFTA) * nondeterministic polynomial time * nondeterministic tree automaton * nondeterministic Turing machine *

nonterminal node In computer science, terminal and nonterminal symbols are the lexical elements used in specifying the production rules constituting a formal grammar. ''Terminal symbols'' are the elementary symbols of the language defined by a formal grammar ...

* nor * not * Not So Naive * NP *

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...

NP-complete language In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

n queens The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. There are 92 solutions. ...

* nullary function *

null tree In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph"). Order-zero graph The order-zero graph, , is t ...

* New York State Identification and Intelligence System (NYSIIS)

O

objective function In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cos ...

* occurrence *

octree An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three-dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional a ...

* odd–even sort *

offline algorithm In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an o ...

offset (computer science) In computer science, an offset within an array or other data structure object is an integer indicating the distance (displacement) between the beginning of the object and a given element or point, presumably within the same object. The concept of ...

omega Omega (; capital: Ω, lowercase: ω; Ancient Greek ὦ, later ὦ μέγα, Modern Greek ωμέγα) is the twenty-fourth and final letter in the Greek alphabet. In the Greek numeric system/ isopsephy ( gematria), it has a value of 800. Th ...

omicron Omicron (; uppercase Ο, lowercase ο, ell, όμικρον) is the 15th letter of the Greek alphabet. This letter is derived from the Phoenician letter ayin: . In classical Greek, omicron represented the close-mid back rounded vowel in contr ...

one-based indexing In computer science, array is a data type that represents a collection of ''elements'' ( values or variables), each selected by one or more indices (identifying keys) that can be computed at run time during program execution. Such a collectio ...

* one-dimensional *

online algorithm In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an o ...

* open addressing * optimal * optimal cost * optimal hashing *

optimal merge Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

optimal mismatch Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

* optimal polygon triangulation problem * optimal polyphase merge * optimal polyphase merge sort * optimal solution * optimal triangulation problem * optimal value *

optimization problem In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables ...

* or *

oracle set In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in ...

* oracle tape * oracle Turing machine *

orders of approximation In science, engineering, and other quantitative disciplines, order of approximation refers to formal or informal expressions for how accurate an approximation is. Usage in science and engineering In formal expressions, the ordinal number used ...

ordered array Order, ORDER or Orders may refer to: * Categorization, the process in which ideas and objects are recognized, differentiated, and understood * Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of d ...

* ordered binary decision diagram (OBDD) * ordered linked list * ordered tree * order preserving hash * order preserving minimal perfect hashing * oriented acyclic graph * oriented graph *

oriented tree In mathematics, and more specifically in graph theory, a polytree (also called directed tree, oriented tree; . or singly connected network.) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, if we replace its ...

* orthogonal drawing * orthogonal lists * orthogonally convex rectilinear polygon * oscillating merge sort * out-branching * out-degree * overlapping subproblems

P

* packing (see set packing) * padding argument * Pagoda (data structure), pagoda * pairing heap * PAM (point access method) * parallel computation thesis * parallel prefix computation * parallel random-access machine (PRAM) * parametric searching * parent * partial function * partially decidable problem * partially dynamic graph problem * partially ordered set * partially persistent data structure * partial order * partial recursive function * partition (set theory) * passive data structure * patience sorting * path (graph theory) * path cover * path system problem * Patricia tree * pattern * pattern element * P-complete * Phencyclidine, PCP * Peano curve * Pearson's hashing * perfect binary tree * perfect hashing * perfect k-ary tree * perfect matching * shuffling, perfect shuffle * performance guarantee * performance ratio * permutation * persistent data structure * phonetic coding * pile (data structure) * pipelined divide and conquer * planar graph * planarization * planar straight-line graph * PLOP-hashing * point access method * pointer jumping * pointer machine * poissonization * polychotomy * polyhedron * polylogarithmic * polynomial * polynomial-time approximation scheme (PTAS) * polynomial hierarchy * polynomial time * polynomial-time

* polynomial-time reduction * polyphase merge * polyphase merge sort * polytope * poset * postfix traversal * Post machine (see Post–Turing machine) * postman's sort * postorder traversal * Post correspondence problem * potential function (see potential method) * Predicate (computer programming), predicate * Prefix (computer science), prefix * prefix code * prefix computation * prefix sum * prefix traversal * preorder traversal * primary clustering * primitive recursive * Prim's algorithm * principle of optimality * priority queue * prisoner's dilemma * Pseudorandom number generator, PRNG * probabilistic algorithm * probabilistically checkable proof * probabilistic Turing machine * probe sequence * Procedure (computer science) * process algebra * proper (see proper subset) * proper binary tree * proper coloring * proper subset * property list * prune and search * pseudorandom number generator * pth order Fibonacci numbers * P-tree * purely functional language * pushdown automaton (PDA) * pushdown transducer * p-way merge sort

Q

* qm sort * qsort * quadratic probing * quadtree * quadtree complexity theorem * quad trie * quantum computation * queue (data structure), queue * quicksort

R

* Rabin–Karp algorithm, Rabin–Karp string-search algorithm * radix quicksort * radix sort * ragged matrix * Raita algorithm * random-access machine * random number generation * randomization * randomized algorithm * randomized binary search tree * randomized complexity * randomized polynomial time * randomized rounding * randomized search tree * Randomized-Select * random number generator * random sampling * range (function) * range sort * Rank (graph theory) * Ratcliff/Obershelp pattern recognition * reachable * Self-balancing binary search tree, rebalance * recognizer * rectangular matrix * wikt: rectilinear, rectilinear * rectilinear Steiner tree * recurrence equations * recurrence relation * recursion * recursion termination * recursion tree * recursive (computer science) * recursive data structure * recursive doubling * recursive language * recursively enumerable language * recursively solvable * red–black tree * reduced basis * reduced digraph * reduced ordered binary decision diagram (ROBDD) * Reduction (complexity), reduction * reflexive relation * regular decomposition * rehashing * relation (mathematics) * relational structure * relative performance guarantee * Relaxation technique (mathematics), relaxation * relaxed balance * rescalable * restricted universe sort * result cache * Reverse Colussi * Reverse Factor * R-file * Rice's method * right rotation * right-threaded tree * root * root balance * rooted tree * rotate left * rotate right * rotation * rough graph * RP (complexity), RP * R+ tree, R+-tree * R* tree, R*-tree * R-tree * Run time (program lifecycle phase), run time

S

* saguaro stack * saturated edge * Self-balancing binary search tree, SBB tree * prefix sum, scan * scapegoat tree * search algorithm * search tree * search tree property * secant search * secondary clustering * memory segment * selection algorithm, select algorithm * select and partition * selection algorithm, selection problem * selection sort * selection algorithm, select kth element * select mode * loop (graph theory), self-loop * self-organizing heuristic * self-organizing list * self-organizing sequential search * semidefinite programming * separate chaining hashing * Planar separator theorem, separator theorem * sequential search * set (abstract data type), set * set cover problem, set cover * set packing * shadow heap * shadow merge * shadow merge insert * cocktail shaker sort, shaker sort * Shannon–Fano coding * shared memory * Shell sort * Shift-Or * Shor's algorithm * shortcutting * shortest common supersequence problem, shortest common supersequence * shortest common superstring * shortest path * shortest spanning tree * shuffle * shuffle sort * sibling * Sierpiński curve * Sierpinski triangle * sieve of Eratosthenes * sift up * signature * Simon's algorithm * simple merge * path (graph theory), simple path * simple uniform hashing * simplex communication * simulated annealing * simulation theorem * single-destination shortest-path problem * single-pair shortest-path problem * single program multiple data * single-source shortest-path problem * singly linked list * singularity analysis * sink * sinking sort * skd-tree * skew-symmetry * skip list * skip search * slope selection * Smith algorithm * Smith–Waterman algorithm * smoothsort * solvable problem * sort algorithm * sorted array * sorted list * in-place algorithm, sort in-place * sort merge * soundex * space-constructible function * spanning tree (mathematics), spanning tree * sparse graph * sparse matrix * sparsification * sparsity * spatial index, spatial access method * spectral test * splay tree * SPMD * square matrix * square root * SST (shortest spanning tree) * Numerical stability, stable * stack (data structure) * stack tree * star-shaped polygon * start state * state (computer science), state * state machine * state transition * static data structure * static Huffman encoding * s-t cut * st-digraph * Steiner minimum tree * Steiner tree problem, Steiner point * Steiner ratio * Steiner tree * Steiner vertex * Steinhaus–Johnson–Trotter algorithm * Stirling's approximation * Stirling's formula * stooge sort * straight-line drawing * strand sort * strictly decreasing * strictly increasing * strictly lower triangular matrix * strictly upper triangular matrix * string (computer science), string * string editing problem * string matching * string matching on ordered alphabets * string matching with errors * string matching with mismatches * string searching * strip packing * strongly connected component * strongly connected graph * strongly NP-hard * subadditive ergodic theorem * subgraph isomorphism * sublinear time algorithm * subsequence * subset *

* subtree * Suffix (computer science), suffix * suffix array * suffix automaton * suffix tree * superimposed code * superset * supersink * supersource * symmetric relation * symmetrically linked list * symmetric binary B-tree * symmetric set difference * symmetry breaking * symmetric min max heap

T

* tail * tail recursion * tango tree * target (CS), target * temporal logic * terminal (see Steiner tree) * leaf node, terminal node * ternary search * ternary search tree (TST) * text searching * theta * threaded binary tree * threaded tree * three-dimensional space, three-dimensional * three-way merge sort * three-way radix quicksort * time-constructible function * time/space complexity * top-down radix sort * top-down tree automaton * top-nodes algorithm, top-node * topological order * topological sort * topology tree * total function * totally decidable language * totally decidable problem * totally undecidable problem * total order * tour * Tournament (graph theory), tournament * towers of Hanoi * tractable problem * transducer * transition (see

) * transition function (of a

or Turing machine) * transitive relation * transitive closure * transitive reduction * transpose sequential search * travelling salesman problem (TSP) * treap * tree data structure, tree * tree automaton * tree contraction * tree editing problem * tree sort * tree transducer * tree traversal * triangle inequality * triconnected graph * trie * trinary function * tripartition * Turbo-BM * Turbo Reverse Factor * Turing machine * Turing reduction * Turing transducer * twin grid file * two-dimensional * two-level grid file * 2–3 tree * 2–3–4 tree * Two Way algorithm * two-way linked list * two-way merge sort

U

* unary function * unbounded knapsack problem (UKP) * uncomputable function * uncomputable problem * undecidable language * undecidable problem * undirected graph * uniform circuit complexity * uniform circuit family * uniform hashing * uniform matrix * union (computer science), union * union of automata * universal hashing * universal state (Turing), universal state * universal Turing machine * universe * unsolvable problem * unsorted list * upper triangular matrix

V

* van Emde Boas tree, van Emde Boas priority queue * vehicle routing problem * Veitch diagram * Venn diagram * vertex (graph theory), vertex * vertex coloring * vertex connectivity * vertex cover * vertical visibility map * virtual hashing * visibility map * visible (geometry) * Viterbi algorithm * VP-tree * VRP (vehicle routing problem)

W

* Glossary of graph theory#Walks, walk * weak cluster * weak-heap * weak-heap sort * weight-balanced tree * weighted, directed graph * weighted graph * window * witness * work-depth model * work-efficient * work-preserving * Best, worst and average case, worst case * Best, worst and average case, worst-case cost * worst-case minimum access * Xiaolin Wu's line algorithm, Wu's line algorithm

X

* Xiaolin Wu's line algorithm * xor

Y

* Yule–Simon distribution

Z

* Zeller's congruence * 0-ary function * 0-based indexing * 0/1 knapsack problem * Zhu–Takaoka string matching algorithm * Zipfian distribution * Zipf's law * Zipper (data structure) * ZPP (complexity), ZPP

References

{{DEFAULTSORT:Algorithms Lists of computer terms, Algorithms and data structures Mathematics-related lists, Algorithms and data structures Algorithms and data structures, zh:数据结构与算法列表