Index by Area

Algorithms and Data Structures

This is the web page of terms with definitions organized by area. That is, whether the term deals with graphs, trees, sorting, etc. We also list all entries with links to implementations and entries by type, for instance, whether it is an algorithm, a definition, a problem, or a data structure.

We need people to contribute. If you have suggestions, corrections, or comments, please get in touch with Paul Black. . You are welcome to make suggestions to expand and improve the DADS.

Run on Mon Aug 24 09:38:58 2015

Areas

Automata and State Machines
Basic
Combinatorics
Cryptography and Compression
External Memory Algorithms and Data Structures
Computational Geometry
Graphs
Numeric Computation
Parallel
Quantum Computation
Searching
Sorting
Theory
Trees
Verification and Formal Methods
Entries with No Area

Automata and State Machines

accepting state [D]
alphabet [D]
alternating Turing machine [D]
automaton [D]
bottom-up tree automaton [D]
busy beaver [P]
cellular automaton [D]
deterministic finite automaton [D]
deterministic finite state machine [D]
deterministic finite tree automaton [D]
deterministic pushdown automaton [D]
deterministic tree automaton [D]
DFA [D]
DFTA [D]
DPDA [D]
existential state [D]
finite state automaton [D]
finite state machine [D]
finite state machine minimization [P]
finite state transducer [D]
Kripke structure [D]
Mealy machine [D]
Moore machine [D]
move [D]
next state [D]
NFA [D]
NFTA [D]
nondeterministic finite automaton [D]
nondeterministic finite state machine [D]
nondeterministic finite tree automaton [D]
nondeterministic tree automaton [D]
nondeterministic Turing machine [D]
oracle set [D]
oracle tape [D]
oracle Turing machine [D]
PDA [D]
probabilistic Turing machine [D]
pushdown automaton [D]
recognizer [D]
start state [D]
state [D]
state machine [D]
state transition [D]
suffix automaton [D]
top-down tree automaton [D]
transition [D]
transition function [D]
tree automaton [D]
Turing machine [D]
union of automata [A]
universal state [D]
universal Turing machine [D]

Basic

α [A]
ω [D]
Ω [D]
~ [D]
Θ [D]
abstract data type [D]
Ackermann's function [A]
active data structure [S]
ADT [D]
algorithm [D]
and [D]
ANSI [D]
antichain [D]
antisymmetric [D]
array [S]
array index [D]
array merging [A]
associative [D]
associative array [S]
average case [D]
axiomatic semantics [D]
backtracking [T]
bag [S]
best case [D]
big-O notation [D]
binary function [D]
binary relation [D]
bit vector [S]
boolean [D]
boolean expression [D]
boolean function [D]
bounded queue [S]
bounded stack [S]
Bradford's law [D]
brute force [T]
bucket [D]
buddy system [A]
Byzantine generals [P]
chain [D]
circuit [D]
circuit complexity [D]
circuit value problem [D]
circular list [S]
circular queue [S]
collective recursion [T]
commutative [D]
complement [D]
confluently persistent data structure [D]
conjunction [D]
constant function [D]
data structure [D]
deque [S]
deterministic algorithm [T]
difference [D]
disjoint set [D]
disjunction [D]
divide and conquer [T]
divide and marriage before conquest [T]
domain [D]
Doomsday rule [A]
double metaphone [A]
doubly-ended queue [S]
doubly linked list [S]
dynamic array [S]
dynamization transformation [T]
efficiency [D]
end-of-string [D]
exclusive or [D]
FIFO [S]
first come, first served [D]
first-in, first-out [D]
full array [D]
fully persistent data structure [D]
function [D]
functional data structure [S]
hashbelt [S]
head [D]
heuristic [T]
hybrid algorithm [D]
implication [D]
implies [D]
inclusion-exclusion principle [D]
inclusive or [D]
intersection [D]
inverse Ackermann function [A]
irreflexive [D]
iteration [T]
Karnaugh map [A]
k-dimensional [D]
key [D]
KV diagram [A]
last-in, first-out [D]
lattice [D]
LIFO [S]
linear order [D]
linear product [D]
link [D]
linked list [S]
list [S]
little-o notation [D]
Lotka's law [D]
lower triangular matrix [S]
Marlena [D]
matrix [S]
memoization [T]
monotonically decreasing [D]
monotonically increasing [D]
multi-set [S]
multiway decision [D]
nand [D]
n-ary function [D]
negation [D]
NIST [D]
node [D]
nondeterministic algorithm [T]
nor [D]
not [D]
nullary function [D]
O [D]
omega [D]
omicron [D]
one-based indexing [D]
one-dimensional [D]
optimal [D]
or [D]
order [D]
ordered linked list [S]
partially ordered set [D]
partially persistent data structure [D]
partial order [D]
passive data structure [S]
persistent data structure [D]
polytope [D]
poset [D]
predicate [D]
priority queue [S]
probabilistic algorithm [D]
procedure [D]
proper [D]
proper subset [D]
queue [S]
ragged matrix [S]
randomization [T]
randomized algorithm [D]
range [D]
rectangular matrix [S]
recursion [T]
recursion termination [D]
recursive [S]
recursive data structure [D]
reduced basis [D]
reflexive [D]
relation [D]
set [S]
signature [D]
singly linked list [S]
sparse matrix [S]
square matrix [S]
stable [D]
stack [S]
stack tree [D]
strictly decreasing [D]
strictly increasing [D]
strictly lower triangular matrix [S]
strictly upper triangular matrix [S]
string [S]
subset [D]
superset [D]
symmetric [D]
symmetrically linked list [S]
symmetric set difference [D]
tail [D]
tail recursion [T]
text [D]
theta [D]
three-dimensional [D]
topological order [D]
total order [D]
transitive [D]
trinary function [D]
two-dimensional [D]
two-way linked list [S]
unary function [D]
uniform matrix [S]
union [D]
universe [D]
upper triangular matrix [S]
Veitch diagram [A]
xor [D]
Zeller's congruence [A]
0-ary function [D]
0-based indexing [D]

Combinatorics

Cryptography and Compression

External Memory Algorithms and Data Structures

Computational Geometry

bintree [S]
bisector [D]
boundary-based representation [D]
Bresenham's algorithm [A]
bucketing method [D]
capacitated facility location [P]
concave function [D]
cutting plane [D]
cutting theorem [D]
decimation [T]
decomposable searching problem [D]
discrete p-center [P]
Euclidean distance [D]
expander graph [D]
extreme point [D]
facility location [P]
fixed-grid method [D]
geometric optimization problem [D]
Hausdorff distance [D]
horizontal visibility map [D]
integer polyhedron [D]
interior-based representation [D]
L_m distance [D]
Manhattan distance [D]
Minkowski distance [D]
nearest neighbor [P]
optimal polygon triangulation problem [P]
optimal triangulation problem [P]
orthogonally convex rectilinear polygon [D]
parametric searching [T]
polyhedron [D]
prune and search [T]
quadtree complexity theorem [D]
regular decomposition [D]
simplex [D]
slope selection [P]
star-shaped polygon [D]
vertical visibility map [D]
visibility map [D]
visible [D]

Graphs

acyclic directed graph [D]
acyclic graph [D]
adjacency-list representation [S]
adjacency-matrix representation [S]
adjacent [D]
admissible vertex [D]
all pairs shortest path [P]
all simple paths [P]
alternating path [D]
arc [D]
articulation point [D]
assignment problem [P]
augmenting path [D]
Baum Welch algorithm [A]
Bellman-Ford algorithm [A]
best-first search [A]
biconnected component [D]
biconnected graph [D]
bipartite graph [D]
bipartite matching [D]
blocking flow [D]
blossom [D]
Boruvka's algorithm [A]
bottleneck traveling salesman [P]
breadth-first search [A]
bridge [D]
capacity [D]
capacity constraint [D]
certificate [D]
Chinese postman problem [P]
Christofides algorithm [A]
chromatic index [D]
chromatic number [D]
clique [D]
clique problem [P]
complete graph [D]
completely connected graph [D]
concurrent flow [D]
connected components [D]
connected graph [D]
critical path problem [P]
cut [D]
cut vertex [D]
cycle [D]
DAG [D]
DAG shortest paths [A]
degree [D]
dense graph [D]
depth-first search [A]
DFS [A]
DFS forest [D]
diameter [D]
digraph [S]
Dijkstra's algorithm [A]
directed acyclic graph [D]
directed graph [S]
dual [D]
edge [D]
edge coloring [D]
edge connectivity [D]
edge crossing [D]
edge-weighted graph [D]
Euclidean Steiner tree [D]
Euler cycle [D]
Eulerian graph [D]
Eulerian path [D]
feedback edge set [D]
feedback vertex set [D]
flow [D]
flow conservation [D]
flow function [D]
flow network [D]
Floyd-Warshall algorithm [A]
Ford-Bellman [A]
Ford-Fulkerson method [A]
free edge [D]
free vertex [D]
fully dynamic graph problem [D]
graph [S]
graph coloring [D]
graph drawing [P]
graph isomorphism [P]
graph partition [P]
grid drawing [D]
Hamiltonian cycle [D]
Hamiltonian path [D]
hidden Markov model [S]
HMM [S]
homeomorphic [D]
hyperedge [D]
hypergraph [S]
in-degree [D]
independent set [D]
integer multi-commodity flow [D]
isomorphic [D]
Johnson's algorithm [A]
k-coloring [D]
k-connected graph [D]
Königsberg bridges problem [D]
Kruskal's algorithm [A]
k^th shortest path [P]
labeled graph [D]
layered graph [D]
Malhotra-Kumar-Maheshwari blocking flow [A]
Markov chain [S]
marriage problem [P]
matched edge [D]
matched vertex [D]
matching [D]
maximal independent set [P]
maximally connected component [D]
maximum bipartite matching [D]
maximum-flow problem [P]
minimum cut [D]
minimum spanning tree [D]
minimum vertex cut [D]
MST [D]
multi-commodity flow [D]
multigraph [S]
network flow [D]
network flow problem [P]
oriented acyclic graph [D]
oriented graph [S]
orthogonal drawing [D]
out-degree [D]
partially dynamic graph problem [D]
path [D]
perfect matching [D]
planar graph [D]
planarization [D]
planar straight-line graph [D]
Prim-Jarnik algorithm [A]
proper coloring [D]
reachable [D]
rectilinear [D]
rectilinear Steiner tree [D]
reduced digraph [D]
rough graph [D]
saturated edge [D]
Schorr-Waite graph marking algorithm [A]
self-loop [D]
shortest path [P]
shortest spanning tree [D]
simple path [D]
single-destination shortest-path problem [P]
single-pair shortest-path problem [P]
single-source shortest-path problem [P]
sink [D]
skew symmetry [D]
source [D]
sparse graph [D]
sparsification [T]
SST [D]
s-t cut [D]
st-digraph [S]
Steiner point [D]
Steiner ratio [D]
Steiner tree [D]
Steiner vertex [D]
straight-line drawing [D]
strongly connected component [D]
strongly connected graph [D]
subgraph [D]
subgraph isomorphism [P]
supersink [D]
supersource [D]
target [D]
terminal [D]
tour [D]
transitive reduction [D]
traveling salesman [P]
triangle inequality [D]
triconnected graph [D]
TSP [P]
undirected graph [S]
vehicle routing problem [P]
vertex [D]
vertex coloring [D]
vertex connectivity [D]
vertex cover [P]
Viterbi algorithm [A]
VRP [P]
walk [D]
weighted, directed graph [D]
weighted graph [D]

Numeric Computation

Parallel

Quantum Computation

Searching

adaptive k-d tree [S]
Aho-Corasick [A]
Alpha Skip Search algorithm [A]
Apostolico-Crochemore [A]
Apostolico-Giancarlo algorithm [A]
approximate string matching [A]
array search [P]
association list [S]
BANG file [S]
BD-tree [S]
binary search [A]
block [D]
block addressing index [S]
block search [A]
Bloom filter [A]
border [D]
Boyer-Moore [A]
Boyer-Moore-Horspool [A]
branch and bound [T]
brute force string search [A]
brute force string search with mismatches [A]
BSP-tree [S]
bucket array [S]
buddy tree [S]
BV-tree [S]
calendar queue [S]
candidate consistency testing [D]
candidate verification [D]
Caverphone [A]
cell tree [S]
chaining [S]
clustering [D]
clustering free [D]
coalesced chaining [S]
collision [D]
collision resolution scheme [A]
Colussi [A]
Commentz-Walter [A]
cuckoo hashing [S]
D-adjacent [D]
deterministic finite automata string search [A]
dichotomic search [D]
dictionary [S]
direct chaining [S]
don't care [D]
double hashing [A]
dynamic hashing [S]
exact string matching [P]
EXCELL [S]
exhaustive search [T]
extended k-d tree [S]
extendible hashing [S]
external chaining [S]
external index [S]
extrapolation search [A]
extremal [D]
factor [D]
fathoming [T]
Fibonaccian search [A]
Find [A]
find k^th least element [P]
forward index [S]
frequency count heuristic [A]
full inverted index [S]
Galil-Giancarlo [A]
Galil-Seiferas [A]
grid file [S]
hash function [A]
hash heap [S]
hash table [S]
hash table delete [A]
hB-tree [S]
heaviest common subsequence [P]
Horspool [A]
incremental hashing [S]
index file [S]
interpolation search [A]
interpolation-sequential search [A]
inverse suffix array [S]
inverted file index [S]
inverted index [S]
Jaro-Winkler [A]
jump list [S]
jump search [A]
Karp-Rabin [A]
k-d-B-tree [S]
k-d tree [S]
KMP [A]
KmpSkip Search [A]
Knuth-Morris-Pratt algorithm [A]
k^th smallest element [P]
LCS [P]
lexicographical order [D]
linear hash [A]
linear hashing [S]
linear probing [S]
linear quadtree [S]
linear search [A]
load factor [D]
local alignment [D]
locality-sensitive hashing [A]
longest common subsequence [P]
longest common substring [P]
map [S]
Maximal Shift [A]
metaheuristic [T]
metaphone [A]
minimal perfect hashing [A]
minimax [A]
MODIFIND [A]
Morris-Pratt algorithm [A]
move-to-front heuristic [A]
move-to-root heuristic [A]
multilayer grid file [S]
multiplication method [A]
multiway search tree [S]
naive string search [A]
Not So Naive [A]
NYSIIS [A]
occurrence [D]
octree [S]
offset [D]
open addressing [A]
optimal hashing [A]
optimal mismatch [A]
ordered array [S]
order-preserving hash [A]
order-preserving minimal perfect hashing [A]
orthogonal lists [S]
PAM [D]
pattern [D]
pattern element [D]
Pearson's hash [A]
perfect hashing [A]
phonetic coding [P]
PLOP-hashing [S]
point access method [D]
polychotomy [D]
prefix [D]
primary clustering [D]
probe sequence [D]
property list [S]
quadratic probing [A]
quadtree [S]
quick search [A]
Rabin-Karp [A]
Raita [A]
random search [A]
rank [D]
Ratcliff/Obershelp pattern recognition [A]
rehashing [A]
reservoir sampling [A]
Reverse Colussi [A]
Reverse Factor [A]
R-file [S]
R⁺-tree [S]
SAM [D]
scatter storage [S]
search [A]
secant search [A]
secondary clustering [D]
segment [D]
Select [A]
select and partition [P]
selection problem [P]
select k^th element [P]
select mode [A]
self-organizing list [S]
self-organizing sequential search [A]
separate chaining [S]
sequential search [A]
Shift-Or [A]
shortest common supersequence [P]
shortest common superstring [P]
Simon's algorithm [A]
simple uniform hashing [D]
simulated annealing [A]
skip list [S]
skip search [A]
Smith algorithm [A]
Smith-Waterman algorithm [A]
sorted array [S]
sorted list [S]
soundex [A]
space ordering method [A]
sparsity [D]
spatial access method [D]
spiral storage [S]
string matching [P]
string matching on ordered alphabets [A]
string matching with errors [A]
string matching with mismatches [A]
string searching [P]
subsequence [D]
substring [D]
suffix [D]
suffix array [S]
ternary search tree [S]
text searching [P]
transpose sequential search [A]
TST [S]
Turbo-BM [A]
Turbo Reverse Factor [A]
twin grid file [S]
2-choice hashing [S]
2-left hashing [S]
two-level grid file [S]
Two Way algorithm [A]
uniform hashing [A]
universal hashing [D]
weak-heap [S]
window [D]
worst-case minimum access [D]
Zhu-Takaoka [A]

Sorting

Theory

ρ-approximation algorithm [T]
absolute performance guarantee [D]
adversary [D]
algorithmically solvable [D]
alternation [D]
amortized cost [D]
approximation algorithm [T]
asymptotically tight bound [D]
asymptotic bound [D]
asymptotic lower bound [D]
asymptotic space complexity [D]
asymptotic time complexity [D]
asymptotic upper bound [D]
average-case cost [D]
best-case cost [D]
bounded error probability in polynomial time [D]
BPP [D]
British Museum technique [T]
Calculus of Communicating Systems [D]
canonical complexity class [D]
CCS [D]
cell probe model [D]
coarsening [D]
Communicating Sequential Processes [D]
competitive analysis [D]
competitive ratio [D]
complexity [D]
complexity class [D]
computable [D]
Cook reduction [D]
Cook's theorem [D]
CSP [D]
decidable language [D]
decidable problem [D]
decision problem [D]
depoissonization [D]
deterministic [D]
diagonalization [D]
dining philosophers [P]
distributional complexity [D]
element uniqueness [P]
Euclidean traveling salesman problem [P]
exponential [D]
feasible region [D]
feasible solution [D]
formal language [D]
fractional solution [D]
fully polynomial approximation scheme [T]
halting problem [P]
huge sparse array [S]
incompressible string [D]
information theoretic bound [D]
interactive proof system [D]
intractable [D]
Karp reduction [D]
Kolmogorov complexity [D]
Kraft's inequality [D]
language [D]
linear [D]
logarithmic [D]
lower bound [D]
l-reduction [D]
many-one reduction [D]
MAX-SNP [D]
MBB [D]
minimum bounding box [D]
model checking [A]
model of computation [D]
moderately exponential [D]
NC many-one reducibility [D]
nondeterministic [D]
nondeterministic polynomial time [D]
NP [D]
NP-complete [D]
NP-complete language [D]
NP-hard [D]
objective function [D]
off-line algorithm [D]
on-line algorithm [D]
optimal cost [D]
optimal solution [D]
optimal value [D]
optimization problem [D]
P [D]
padding argument [D]
partial function [D]
partially decidable problem [D]
partial recursive function [D]
P-complete [D]
PCP [P]
performance guarantee [D]
performance ratio [D]
pointer machine [D]
poissonization [D]
polylogarithmic [D]
polynomial [D]
polynomial approximation scheme [T]
polynomial hierarchy [D]
polynomial time [D]
polynomial-time reduction [D]
Post's correspondence problem [P]
potential function [D]
primitive recursive [D]
prisoner's dilemma [P]
probabilistically checkable proof [D]
process algebra [D]
PTAS [T]
purely functional language [D]
pushdown transducer [D]
random access machine [D]
randomized complexity [D]
randomized polynomial time [D]
randomized rounding [A]
recurrence equations [D]
recurrence relation [D]
recursion tree [D]
recursive language [D]
recursively enumerable language [D]
recursively solvable [D]
reduction [D]
relational structure [S]
relative performance guarantee [D]
relaxation [D]
rescalable [D]
Rice's method [D]
RP [D]
run time [D]
separation theorem [D]
shared memory [D]
simulation theorem [D]
singularity analysis [D]
solvable [D]
space-constructible function [D]
strongly NP-hard [D]
subadditive ergodic theorem [D]
sublinear time algorithm [D]
temporal logic [D]
time-constructible function [D]
time/space complexity [D]
total function [D]
totally decidable language [D]
totally decidable problem [D]
totally undecidable problem [D]
tractable [D]
Turing reduction [D]
Turing transducer [D]
uncomputable function [D]
uncomputable problem [D]
undecidable language [D]
undecidable problem [D]
uniform circuit complexity [D]
uniform circuit family [D]
unsolvable problem [D]
Venn diagram [D]
WCET [D]
worst case [D]
worst-case cost [D]
worst-case execution time [D]
ZPP [D]

Trees

(a,b)-tree [S]
ancestor [D]
arborescence [D]
AVL tree [S]
balance [D]
balanced binary search tree [S]
balanced binary tree [S]
balanced multiway tree [S]
balanced tree [S]
BB(α) tree [S]
BDD [S]
binary heap [S]
binary priority queue [S]
binary search tree [S]
binary tree [S]
binary tree representation of trees [S]
binomial heap [S]
binomial tree [S]
B_k tree [S]
blind trie [S]
B⁺-tree [S]
B*-tree [S]
B-tree [S]
bucket trie [S]
build-heap [A]
cactus stack [S]
cartesian tree [S]
child [D]
compact DAWG [S]
compact trie [S]
complete binary tree [S]
complete tree [S]
DAWG [S]
depth [D]
descendant [D]
diet [S]
digital search tree [S]
digital tree [S]
directed acyclic word graph [S]
discrete interval encoding tree [S]
double-ended priority queue [S]
doubly-chained tree [S]
D-tree [S]
dyadic tree [S]
elastic-bucket trie [S]
enfilade [S]
extended binary tree [S]
external node [D]
Fibonacci heap [S]
Fibonacci tree [S]
filial-heir chain [S]
finitary tree [S]
first child-next sibling binary tree [S]
forest [D]
free tree [D]
full binary tree [S]
GBD-tree [S]
heap [S]
heapify [A]
heap property [D]
height [D]
height-balanced binary search tree [S]
height-balanced tree [S]
in-order traversal [A]
internal node [D]
jelly-fish [S]
k-ary heap [S]
k-ary tree [S]
k-way tree [S]
leaf [D]
leftist tree [S]
left rotation [A]
level [D]
level-order traversal [A]
lowest common ancestor [D]
max-heap property [D]
meld [D]
min-heap property [D]
monotone priority queue [S]
multi suffix tree [S]
multiway tree [S]
nonterminal node [D]
null tree [D]
ordered tree [S]
oriented tree [D]
pagoda [S]
parent [D]
Patricia tree [S]
perfect binary tree [D]
perfect k-ary tree [D]
postfix traversal [A]
postorder traversal [A]
prefix traversal [A]
preorder traversal [A]
proper binary tree [S]
P-tree [S]
quad trie [S]
radix tree [S]
randomized binary search tree [S]
randomized search tree [S]
RBST [S]
rebalance [A]
red-black tree [S]
reduced ordered binary decision diagram [S]
relaxed balance [D]
right rotation [A]
right-threaded tree [S]
ROBDD [S]
root [D]
root balance [D]
rooted tree [D]
rotate left [A]
rotate right [A]
rotation [D]
R^*-tree [S]
R-tree [S]
saguaro stack [S]
SBB tree [S]
scapegoat tree [A]
search tree [S]
search tree property [D]
shadow heap [S]
shadow merge [A]
shadow merge insert [A]
sibling [D]
sift up [A]
skd-tree [S]
spanning tree [D]
splay tree [S]
subtree [D]
suffix tree [S]
symmetric binary B-tree [S]
terminal node [D]
threaded binary tree [S]
threaded tree [S]
topology tree [D]
treap [S]
tree [S]
tree traversal [D]
trie [S]
2-3-4 tree [S]
2-3 tree [S]
UB-tree [S]
universal B-tree [S]
unlimited branching tree [S]
van Emde-Boas priority queue [S]
weight-balanced tree [S]
zipper [S]

Verification and Formal Methods

Entries with No Area

Created Tue Nov 17 13:41:10 1998
by Paul E. Black (paul.black@nist.gov)
This Trailer Updated Wed Oct 16 16:37:38 2013 by Paul E. Black
This page's URL is http://www.nist.gov/dads/termsArea.html