Dictionary of Algorithms and Data Structures

α

ω

Ω

ρ-approximation algorithm

Θ

A

absolute performance guarantee

abstract data type

(a,b)-tree

accepting state

Ackermann's function

active data structure

acyclic directed graph

acyclic graph

adaptive heap sort

adaptive Huffman coding

adaptive k-d tree

adaptive sort

address-calculation sort

adjacency-list representation

adjacency-matrix representation

adjacent

admissible vertex

ADT

adversary

Aho-Corasick

algorithm

algorithm BSTW

algorithm FGK

algorithmically solvable

all pairs shortest path

all simple paths

alphabet

Alpha Skip Search algorithm

alternating path

alternating Turing machine

alternation

American flag sort

amortized cost

ancestor

and

ANSI

antichain

antisymmetric

Apostolico-Crochemore

Apostolico-Giancarlo algorithm

approximate string matching

approximation algorithm

arborescence

arc

arithmetic coding

array

array index

array merging

array search

articulation point

assignment problem

association list

associative

associative array

asymptotically tight bound

asymptotic bound

asymptotic lower bound

asymptotic space complexity

asymptotic time complexity

asymptotic upper bound

augmenting path

automaton

average case

average-case cost

AVL tree

axiomatic semantics

B

backtracking

bag

balance

balanced binary search tree

balanced binary tree

balanced k-way merge sort

balanced merge sort

balanced multiway merge

balanced multiway tree

balanced quicksort

balanced tree

balanced two-way merge sort

BANG file

Batcher sort

Baum Welch algorithm

BB(α) tree

BBP algorithm

BDD

BD-tree

Bellman-Ford algorithm

Benford's law

best case

best-case cost

best-first search

biconnected component

biconnected graph

bidirectional bubble sort

big-O notation

binary function

binary GCD

binary heap

binary insertion sort

binary knapsack problem

binary priority queue

binary relation

binary search

binary search tree

binary tree

binary tree representation of trees

bingo sort

binomial heap

binomial tree

bin packing problem

bin sort

bintree

bipartite graph

bipartite matching

bisector

bitonic sort

bit vector

B_k tree

block

block addressing index

blocking flow

block search

Bloom filter

blossom

bogosort

boolean

boolean expression

boolean function

border

Boruvka's algorithm

bottleneck traveling salesman

bottom-up tree automaton

boundary-based representation

bounded error probability in polynomial time

bounded queue

bounded stack

Boyer-Moore

Boyer-Moore-Horspool

bozo sort

B+-tree

BPP

Bradford's law

branch and bound

breadth-first search

Bresenham's algorithm

brick sort

bridge

British Museum technique

brute force

brute force string search

brute force string search with mismatches

BSP-tree

B*-tree

B-tree

bubble sort

bucket

bucket array

bucketing method

bucket sort

bucket trie

buddy system

buddy tree

build-heap

Burrows-Wheeler transform

busy beaver

BV-tree

BWT

Byzantine generals

C

cactus stack

Calculus of Communicating Systems

calendar queue

candidate consistency testing

candidate verification

canonical complexity class

capacitated facility location

capacity

capacity constraint

cartesian tree

cascade merge sort

Caverphone

Cayley-Purser

CCS

cell probe model

cell tree

cellular automaton

centroid

certificate

chain

chaining

child

Chinese postman problem

Chinese remainder theorem

Christofides algorithm

Christofides heuristic

chromatic index

chromatic number

Church-Turing thesis

circuit

circuit complexity

circuit value problem

circular list

circular queue

clique

clique problem

clustering

clustering free

coalesced chaining

coarsening

cocktail shaker sort

codeword

coding tree

collective recursion

collision

collision resolution scheme

Colussi

combination

comb sort

Communicating Sequential Processes

commutative

compact DAWG

compact trie

comparison sort

competitive analysis

competitive ratio

complement

complete binary tree

complete graph

completely connected graph

complete tree

complexity

complexity class

computable

concave function

concurrent flow

concurrent read, concurrent write

concurrent read, exclusive write

confluently persistent data structure

conjunction

connected components

connected graph

constant function

continuous knapsack problem

Cook reduction

Cook's theorem

CORDIC

counting sort

covering

CRC

CRCW

CREW

critical path problem

CSP

CTL

cube root

cuckoo hashing

cut

cutting plane

cutting stock problem

cutting theorem

cut vertex

cycle

cyclic redundancy check

D

D-adjacent

DAG

DAG shortest paths

data structure

DAWG

decidable language

decidable problem

decimation

decision problem

decomposable searching problem

degree

dense graph

depoissonization

depth

depth-first search

deque

derangement

descendant

deterministic

deterministic algorithm

deterministic finite automata string search

deterministic finite automaton

deterministic finite state machine

deterministic finite tree automaton

deterministic pushdown automaton

deterministic tree automaton

Deutsch-Jozsa algorithm

DFA

DFS

DFS forest

DFTA

diagonalization

diameter

dichotomic search

dictionary

diet

difference

digital search tree

digital tree

digraph

Dijkstra's algorithm

diminishing increment sort

dining philosophers

direct chaining

directed acyclic graph

directed acyclic word graph

directed graph

discrete interval encoding tree

discrete p-center

disjoint set

disjunction

distributional complexity

distribution sort

divide and conquer

divide and marriage before conquest

division method

domain

don't care

Doomsday rule

double-direction bubble sort

double-ended priority queue

double hashing

double left rotation

double metaphone

double right rotation

doubly-chained tree

doubly-ended queue

doubly linked list

DPDA

dual

dual linear program

Dutch national flag

dyadic tree

dynamic

dynamic array

dynamic hashing

dynamic Huffman coding

dynamic programming

dynamization transformation

E

easy split, hard merge

edge

edge coloring

edge connectivity

edge crossing

edge-weighted graph

edit distance

edit operation

edit script

efficiency

8 queens

elastic-bucket trie

element uniqueness

end-of-string

enfilade

ERCW

EREW

Euclidean algorithm

Euclidean distance

Euclidean Steiner tree

Euclidean traveling salesman problem

Euclid's algorithm

Euler cycle

Eulerian graph

Eulerian path

exact string matching

EXCELL

exchange sort

exclusive or

exclusive read, concurrent write

exclusive read, exclusive write

exhaustive search

existential state

expandable hashing

expander graph

exponential

extended binary tree

extended Euclid's algorithm

extended k-d tree

extendible hashing

external chaining

external index

external memory algorithm

external memory data structure

external merge

external node

external quicksort

external radix sort

external sort

extrapolation search

extremal

extreme point

F

facility location

factor

factorial

fast fourier transform

fathoming

feasible region

feasible solution

feedback edge set

feedback vertex set

Ferguson-Forcade algorithm

FFT

Fibonaccian search

Fibonacci heap

Fibonacci number

Fibonacci tree

FIFO

filial-heir chain

Find

find k^th least element

finitary tree

finite Fourier transform

finite state automaton

finite state machine

finite state machine minimization

finite state transducer

first child-next sibling binary tree

first come, first served

first-in, first-out

Fisher-Yates shuffle

fixed-grid method

flash sort

flow

flow conservation

flow function

flow network

Floyd-Warshall algorithm

Ford-Bellman

Ford-Fulkerson method

forest

forest editing problem

formal language

formal methods

formal verification

forward index

fractional knapsack problem

fractional solution

free edge

free tree

free vertex

frequency count heuristic

full array

full binary tree

full inverted index

fully dynamic graph problem

fully persistent data structure

fully polynomial approximation scheme

function

functional data structure

G

Galil-Giancarlo

Galil-Seiferas

gamma function

GBD-tree

GCD

geometric optimization problem

global optimum

gnome sort

graph

graph coloring

graph concentration

graph drawing

graph isomorphism

graph partition

Gray code

greatest common divisor

greedy algorithm

greedy heuristic

grid drawing

grid file

Grover's algorithm

H

halting problem

Hamiltonian cycle

Hamiltonian path

Hamming distance

hard split, easy merge

hash function

hash heap

hash table

hash table delete

Hausdorff distance

hB-tree

head

heap

heapify

heap property

heapsort

heaviest common subsequence

height

height-balanced binary search tree

height-balanced tree

heuristic

hidden Markov model

highest common factor

histogram sort

HMM

homeomorphic

horizontal visibility map

Horner's rule

Horspool

Huffman coding

Hungarian algorithm

hybrid algorithm

hyperedge

hypergraph

I

ideal merge

implication

implies

inclusion-exclusion principle

inclusive or

incompressible string

incremental hashing

in-degree

independent set

index file

information theoretic bound

in-order traversal

in-place sort

insertion sort

integer linear program

integer multi-commodity flow

integer polyhedron

interactive proof system

interior-based representation

internal node

internal sort

interpolation search

interpolation-sequential search

interpolation sort

intersection

interval tree

intractable

introsort

introspective sort

inverse Ackermann function

inverted file index

inverted index

irreflexive

isomorphic

iteration

J

Jaro-Winkler

Johnson's algorithm

Johnson-Trotter

J sort

jump list

jump search

K

Karmarkar's algorithm

Karnaugh map

Karp-Rabin

Karp reduction

k-ary heap

k-ary Huffman coding

k-ary tree

k-clustering

k-coloring

k-connected graph

k-d-B-tree

k-dimensional

K-dominant match

k-d tree

key

KMP

KmpSkip Search

knapsack problem

knight's tour

Knuth-Morris-Pratt algorithm

Königsberg bridges problem

Kolmogorov complexity

Kraft's inequality

Kripke structure

Kruskal's algorithm

kth order Fibonacci numbers

k^th shortest path

k^th smallest element

KV diagram

k-way merge

k-way merge sort

k-way tree

L

labeled graph

language

last-in, first-out

Las Vegas algorithm

lattice

layered graph

LCM

LCS

leaf

least common multiple

leftist tree

left rotation

Lempel-Ziv-Welch

level-order traversal

Levenshtein distance

lexicographical order

LIFO

linear

linear congruential generator

linear hash

linear hashing

linear insertion sort

linear order

linear probing

linear probing sort

linear product

linear program

linear quadtree

linear search

link

linked list

list

list contraction

little-o notation

L_m distance

load factor

local alignment

local optimum

logarithmic

longest common subsequence

longest common substring

Lotka's law

lower bound

lower triangular matrix

lowest common ancestor

l-reduction

lucky sort

LZW compression

M

Malhotra-Kumar-Maheshwari blocking flow

Manhattan distance

many-one reduction

map

Markov chain

Marlena

marriage problem

Master theorem

matched edge

matched vertex

matching

matrix

matrix-chain multiplication problem

max-heap property

maximal independent set

maximally connected component

Maximal Shift

maximum bipartite matching

maximum-flow problem

MAX-SNP

MBB

Mealy machine

mean

median

meld

memoization

merge

merge sort

metaheuristic

metaphone

midrange

Miller-Rabin

min-heap property

minimal perfect hashing

minimum bounding box

minimum cut

minimum path cover

minimum spanning tree

minimum vertex cut

mixed integer linear program

mode

model checking

model of computation

moderately exponential

MODIFIND

monotone priority queue

monotonically decreasing

monotonically increasing

Monte Carlo algorithm

Moore machine

Morris-Pratt

move

move-to-front heuristic

move-to-root heuristic

MST

multi-commodity flow

multigraph

multilayer grid file

multiplication method

multiprefix

multiprocessor model

multi-set

multi suffix tree

multiway decision

multiway merge

multiway search tree

multiway tree

Munkres' assignment algorithm

N

naive string search

nand

n-ary function

NC many-one reducibility

nearest neighbor

negation

network flow

network flow problem

next state

NFA

NFTA

NIST

node

nonbalanced merge

nonbalanced merge sort

nondeterministic

nondeterministic algorithm

nondeterministic finite automaton

nondeterministic finite state machine

nondeterministic finite tree automaton

nondeterministic polynomial time

nondeterministic tree automaton

nondeterministic Turing machine

nonterminal node

nor

not

Not So Naive

NP

NP-complete

NP-complete language

NP-hard

n queens

nullary function

null tree

NYSIIS

O

O

OBDD

objective function

occurrence

octree

off-line algorithm

offset

omega

omicron

one-based indexing

one-dimensional

on-line algorithm

open addressing

optimal

optimal cost

optimal hashing

optimal merge

optimal mismatch

optimal polygon triangulation problem

optimal polyphase merge

optimal polyphase merge sort

optimal solution

optimal triangulation problem

optimal value

optimization problem

or

oracle set

oracle tape

oracle Turing machine

order

ordered array

ordered binary decision diagram

ordered linked list

ordered tree

order preserving hash

order preserving minimal perfect hashing

oriented acyclic graph

oriented graph

oriented tree

orthogonal drawing

orthogonal lists

orthogonally convex rectilinear polygon

oscillating merge sort

out-degree

P

P

packing

padding argument

pagoda

pairing heap

PAM

parallel computation thesis

parallel prefix computation

parallel random-access machine

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

passive data structure

path

path cover

path system problem

Patricia tree

pattern

pattern element

P-complete

PCP

PDA

Pearson's hash

perfect binary tree

perfect hashing

perfect k-ary tree

perfect matching

perfect shuffle

performance guarantee

performance ratio

permutation

persistent data structure

phonetic coding

pile

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 approximation scheme

polynomial hierarchy

polynomial time

polynomial-time reduction

polyphase merge

polyphase merge sort

polytope

poset

postfix traversal

Post machine

postman's sort

postorder traversal

Post's correspondence problem

potential function

PRAM

predicate

prefix

prefix code

prefix computation

prefix sums

prefix traversal

preorder traversal

primary clustering

primitive recursive

Prim-Jarnik algorithm

principle of optimality

priority queue

prisoner's dilemma

PRNG

probabilistic algorithm

probabilistically checkable proof

probabilistic Turing machine

probe sequence

procedure

process algebra

proper

proper binary tree

proper coloring

proper subset

property list

prune and search

pseudo-random number generator

PTAS

pth order Fibonacci numbers

P-tree

purely functional language

pushdown automaton

pushdown transducer

p-way merge sort

Q

qm sort

q sort

quadratic probing

quadtree

quadtree complexity theorem

quad trie

quantum computation

queue

quick search

quicksort

R

Rabin-Karp

radix quicksort

radix sort

radix tree

ragged matrix

Raita

random access machine

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

range sort

rank

Ratcliff/Obershelp pattern recognition

RBST

reachable

rebalance

recognizer

rectangular matrix

rectilinear

rectilinear Steiner tree

recurrence equations

recurrence relation

recursion

recursion termination

recursion tree

recursive

recursive data structure

recursive doubling

recursive language

recursively enumerable language

recursively solvable

red-black tree

reduced basis

reduced digraph

reduced ordered binary decision diagram

reduction

reflexive

regular decomposition

rehashing

relation

relational structure

relative performance guarantee

relaxation

relaxed balance

repeated squaring

rescalable

restricted universe sort

result cache

Reverse Colussi

Reverse Factor

R-file

Rice's method

right rotation

right-threaded tree

RNG

ROBDD

root

root balance

rooted tree

rotate left

rotate right

rotation

rough graph

RP

R⁺-tree

R^*-tree

R-tree

run time

S

saguaro stack

SAM

saturated edge

SBB tree

scan

scapegoat tree

scatter storage

search

search tree

search tree property

secant search

secondary clustering

segment

Select

select and partition

selection problem

selection sort

select k^th element

select mode

self-loop

self-organizing heuristic

self-organizing list

self-organizing sequential search

semidefinite programming

separate chaining

separation theorem

sequential search

set

set cover

set packing

shadow heap

shadow merge

shadow merge insert

shaker sort

Shannon-Fano coding

shared memory

Shell sort

Shift-Or

Shor's algorithm

shortcutting

shortest common supersequence

shortest common superstring

shortest path

shortest spanning tree

shuffle

shuffle sort

sibling

sieve of Eratosthenes

sift up

signature

Simon's algorithm

simple merge

simple path

simple uniform hashing

simplex

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

sort

sorted array

sorted list

sort in place

soundex

source

space-constructible function

spanning tree

sparse graph

sparse matrix

sparsification

sparsity

spatial access method

spiral storage

splay tree

SPMD

square matrix

square root

SST

stable

stack

stack tree

star-shaped polygon

start state

state

state machine

state transition

static

static Huffman coding

s-t cut

st-digraph

Steiner point

Steiner ratio

Steiner tree

Steiner vertex

Steinhaus-Johnson-Trotter

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

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

subgraph isomorphism

sublinear time algorithm

subsequence

subset

substring

subtree

suffix

suffix array

suffix automaton

suffix tree

superimposed code

superset

supersink

supersource

symmetric

symmetrically linked list

symmetric binary B-tree

symmetric set difference

symmetry breaking

T

tail

tail recursion

target

temporal logic

terminal

terminal node

ternary search tree

text

text searching

theta

threaded binary tree

threaded tree

three-dimensional

three-way merge sort

three-way radix quicksort

time-constructible function

time/space complexity

top-down radix sort

top-down tree automaton

topological order

topological sort

topology tree

total function

totally decidable language

totally decidable problem

totally undecidable problem

total order

tour

tournament

tournament sort

towers of Hanoi

tractable

transition

transition function

transitive

transitive closure

transitive reduction

transpose sequential search

traveling salesman

treap

tree

tree automaton

tree contraction

tree editing problem

treesort (1)

treesort (2)

tree traversal

triangle inequality

triconnected graph

trie

trinary function

tripartition

TSP

TST

Turbo-BM

Turbo Reverse Factor

Turing machine

Turing reduction

Turing transducer

twin grid file

2-choice hashing

two-dimensional

2-left hashing

two-level grid file

2-3-4 tree

2-3 tree

Two Way algorithm

two-way linked list

two-way merge sort

U

UB-tree

UKP

unary function

unbounded knapsack problem

uncomputable function

uncomputable problem

undecidable language

undecidable problem

undirected graph

uniform circuit complexity

uniform circuit family

uniform hashing

uniform matrix

union

union of automata

universal B-tree

universal hashing

universal state

universal Turing machine

universe

UnShuffle sort

unsolvable problem

unsorted list

upper triangular matrix

V

van Emde-Boas priority queue

vehicle routing problem

Veitch diagram

Venn diagram

vertex

vertex coloring

vertex connectivity

vertex cover

vertical visibility map

virtual hashing

visibility map

visible

Viterbi algorithm

Vitter's algorithm

VRP

W

walk

weak-heap

weak-heap sort

weight-balanced tree

weighted, directed graph

weighted graph

window

witness

work

work-depth model

work-efficient

work-preserving

worst case

worst-case cost

worst-case minimum access

X

xor

Y

Yule distribution

Z

Zeller's congruence

0-ary function

0-based indexing

0-1 knapsack problem

Zhu-Takaoka

Zipfian distribution

Zipf's law

zipper

ZPP