A hub of online professional and topical glossaries/dictionaries
Items 1→50 of 1100. Page 1 of 22. items/page.
(A,B)-TREE  look up translate image
A search tree with the restrictions that all leaves are at the same depth and all internal nodes have between a and b children, where a and b are integers such that 2 ≤ a ≤ (b+1)/2. The root may have as few as 2 children.
~  look up translate image
(1) Proportional to. (2) Asymptotically equal to. A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) ~ g(n) means it grows at the same rate as g(n). More formally, it means limx → ∞f(x)/g(x) = 1.
0-ARY FUNCTION  look up translate image
A function that takes no arguments.
0-BASED INDEXING  look up translate image
Indexing (an array) beginning with 0.
2-3 TREE  look up translate image
A B-tree of order 3, that is, internal nodes have two or three children.
2-3-4 TREE  look up translate image
A B-tree of order 4, that is, internal nodes have two, three, or four children.
2-CHOICE HASHING  look up translate image
A variant of a hash table in which keys are added by hashing with two hash functions. The key is put in the array position with the fewer (colliding) keys. Some collision resolution scheme is needed, unless keys are kept in buckets. The average-case cost of a successful search is O(2 + (m-1)/n), where m is the number of keys and n is the size of the array. The most collisions is log2 ln n + Θ(m/n) with high probability.
2-LEFT HASHING  look up translate image
A dictionary implemented with two hash tables of equal size, T1 and T2, and two different hash functions, h1 and h2. A new key is put in table 2 only if there are fewer (colliding) keys at T2[h2(key)] than at T1[h1(key)], otherwise it is put in table 1. With n keys and two tables of size n/2, the most collisions is 0.69... log2 ln n + O(1) with high probability.
8 QUEENS  look up translate image
Place eight chess queens on an 8 × 8 board such that no queen can attack another. Efficiently find all possible placements.
An approximation algorithm will return a solution at most a bounded amount more (or less, as appropriate) than the optimum.
ABSTRACT DATA TYPE  look up translate image
A set of data values and associated operations that are precisely specified independent of any particular implementation.
ACCEPTING STATE  look up translate image
If a finite state machine finishes an input string and is in an accepting state, the string is accepted or considered to be valid.
ACKERMANN'S FUNCTION  look up translate image
A function of two parameters whose value grows very fast.
ACTIVE DATA STRUCTURE  look up translate image
A data structure with an associated thread or process that performs internal operations to give the external behavior of another, usually more general, data structure.
ACYCLIC GRAPH  look up translate image
A graph with no path that starts and ends at the same vertex.
ADAPTIVE HEAP SORT  look up translate image
A variant of heapsort that uses a randomized binary search tree (RBST) to structure the input according to any preexisting order. The RBST is used to select candidates that are put into the heap so the heap doesn't need to keep track of all elements.
ADAPTIVE HUFFMAN CODING  look up translate image
A near-minimal variable-length character coding that changes based on the frequency of characters processed. As characters are processed, frequencies are updated and codes are changed (or, the coding tree is modified).
ADAPTIVE K-D TREE  look up translate image
A tree for multidimensional points where successive levels may be split along different dimensions.
ADAPTIVE SORT  look up translate image
A sorting algorithm that can take advantage of existing order in the input, reducing its requirements for computational resources as a function of the disorder in the input.
ADDRESS-CALCULATION SORT  look up translate image
A sort algorithm which uses knowledge of the domain of the items to calculate the position of each item in the sorted array.
ADJACENCY-LIST REPRESENTATION  look up translate image
A representation of a directed graph with n vertices using an array of n lists of vertices. List i contains vertex j if there is an edge from vertex i to vertex j. A weighted graph may be represented with a list of vertex/weight pairs. An undirected graph may be represented by having vertex j in the list for vertex i and vertex i in the list for vertex j.
A representation of a directed graph with n vertices using an n × n matrix, where the entry at (i,j) is 1 if there is an edge from vertex i to vertex j; otherwise the entry is 0. A weighted graph may be represented using the weight as the entry. An undirected graph may be represented using the same entry in both (i,j) and (j,i) or using an upper triangular matrix.
ADJACENT  look up translate image
Could not load http://xlinux.nist.gov/dads/HTML/adjacent.html
ADMISSIBLE VERTEX  look up translate image
See the explanation at path system problem.
ADVERSARY  look up translate image
A theoretical agent that uses information about the past moves of an on-line algorithm to choose inputs that force the worst-case cost of the algorithm.
AHO-CORASICK  look up translate image
A multiple string matching algorithm that constructs a finite state machine from a pattern (list of keywords), then uses the machine to locate all occurrences of the keywords in a body of text.
ALGORITHM  look up translate image
A computable set of steps to achieve a desired result.
ALGORITHM BSTW  look up translate image
(no definition here, yet, but you can help.)
ALGORITHM FGK  look up translate image
An adaptive Huffman coding scheme. Coding is never much worse than twice optimal.
ALL PAIRS SHORTEST PATH  look up translate image
Find the weight (or length) of the shortest paths between all pairs of vertices in a weighted, directed graph.
ALL SIMPLE PATHS  look up translate image
Find all simple paths from a starting vertex (source) to a destination vertex (sink) in a directed graph. In an undirected graph, find all simple paths between two vertices.
ALPHA SKIP SEARCH ALGORITHM  look up translate image
(no definition here, yet, but you can help.)
ALPHABET  look up translate image
The set of all possible symbols in an application. For instance, input characters used by a finite state machine, letters making up strings in a language, or symbols in a pattern element. In some cases, an alphabet may be infinite.
ALTERNATING PATH  look up translate image
A path with alternating free and matched edges.
ALTERNATING TURING MACHINE  look up translate image
A nondeterministic Turing machine having universal states, from which the machine accepts only if all possible moves out of that state lead to acceptance.
ALTERNATION  look up translate image
A model of computation proposed by A. K. Chandra, L. Stockmeyere, and D. Kozen, which has two kinds of states, AND and OR. The definition of accepting computation is adjusted accordingly.
AMERICAN FLAG SORT  look up translate image
An efficient, in-place variant of radix sort that distributes items into hundreds of buckets. The first step counts the number of items in each bucket, and the second step computes where each bucket will start in the array. The last step cyclically permutes items to their proper bucket. Since the buckets are in order in the array, there is no collection step. The name comes by analogy with the Dutch national flag problem in the last step: efficiently partition the array into many "stripes". Using some efficiency techniques, it is twice as fast as quicksort for large sets of strings.
AMORTIZED COST  look up translate image
The theoretical speed of a given set of operations. It is O(f(n)) when the execution time of the worst case of all sequences of n operations never exceeds O(n*f(n)).
ANCESTOR  look up translate image
A parent of a node in a tree, the parent of the parent, etc.
AND  look up translate image
Conjunction: 0 AND 0 = 0, 0 AND 1 = 0, 1 AND 0 = 0, 1 AND 1 = 1.
ANSI  look up translate image
American National Standards Institute.
ANTICHAIN  look up translate image
A subset of mutually incomparable elements in a poset.
ANTISYMMETRIC  look up translate image
A binary relation R for which a R b and b R a implies a = b.
APOSTOLICO-CROCHEMORE  look up translate image
(no definition here, yet, but you can help.)
(no definition here, yet, but you can help.)
APPROXIMATION ALGORITHM  look up translate image
An algorithm to solve an optimization problem that runs in polynomial time in the length of the input and outputs a solution that is guaranteed to be close to the optimal solution. "Close" has some well-defined sense called the performance guarantee.
ARBORESCENCE  look up translate image
Informally, a directed tree.
ARITHMETIC CODING  look up translate image
A minimal variable-length message coding based on the frequency of each character. The message is represented by a fraction which is the repeated offset-plus-product reduction of the range (offset) and probability (product) of each character.
ARRAY  look up translate image
An assemblage of items that are randomly accessible by integers, the index.
ARRAY INDEX  look up translate image
The location of an item in an array.
first prev Page of 22 next last
Back to Top
Dictionary of Algorithms and Data Structures
Visibility Public
Created by admin
Created on 2012-08-18 06:53:25
Number of terms 1100
Last added ZPP by admin
2012-08-18 07:16:54
  • Algorithms Glossary
  • Dictionary of Algorithms and Data Structures
    Definitions of algorithms, data structures, and classical Computer Science problems. Some entries have links to implementations and more information.