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

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

Types

• Algorithms
• Data Structures
• Algorithmic Techniques
• Classic Problems
• Definitions
• Entries with No Type

Algorithms

• α
• Ackermann's function
• adaptive heap sort
• adaptive Huffman coding
• address-calculation sort
• Aho-Corasick
• algorithm BSTW
• algorithm FGK
• Alpha Skip Search algorithm
• American flag sort
• Apostolico-Crochemore
• Apostolico-Giancarlo algorithm
• approximate string matching
• arithmetic coding
• array merging
• balanced k-way merge sort
• balanced merge sort
• balanced multiway merge
• balanced quicksort
• balanced two-way merge sort
• Batcher sort
• Baum Welch algorithm
• BBP algorithm
• Bellman-Ford algorithm
• best-first search
• bidirectional bubble sort
• binary GCD
• binary insertion sort
• binary search
• bingo sort
• bin sort
• bitonic sort
• blind sort
• block search
• Bloom filter
• bogosort
• Boruvka's algorithm
• Boyer-Moore
• Boyer-Moore-Horspool
• bozo sort
• breadth-first search
• Bresenham's algorithm
• brick sort
• brute force string search
• brute force string search with mismatches
• bubble sort
• bucket sort
• buddy system
• build-heap
• Burrows-Wheeler transform
• BWT
• Caverphone
• Chinese remainder theorem
• Christofides algorithm
• cocktail shaker sort
• collision resolution scheme
• Colussi
• combination
• comb sort
• Commentz-Walter
• CORDIC
• counting sort
• CRC
• cube root
• cyclic redundancy check
• DAG shortest paths
• depth-first search
• derangement
• deterministic finite automata string search
• deterministic random bit generator
• Deutsch-Jozsa algorithm
• DFS
• Dijkstra's algorithm
• diminishing increment sort
• distribution sort
• distributive partitioning sort
• dominance tree sort
• Doomsday rule
• double-direction bubble sort
• double hashing
• double metaphone
• DRBG
• dynamic Huffman coding
• Euclidean algorithm
• Euclid's algorithm
• exchange sort
• extended Euclid's algorithm
• external memory algorithm
• external merge
• external quicksort
• external radix sort
• extrapolation search
• fast fourier transform
• Ferguson-Forcade algorithm
• FFT
• Fibonaccian search
• Find
• finite Fourier transform
• Fisher-Yates shuffle
• flash sort
• Floyd-Warshall algorithm
• Ford-Bellman
• Ford-Fulkerson method
• frequency count heuristic
• Galil-Giancarlo
• Galil-Seiferas
• GCD
• gnome sort
• greatest common divisor
• Grover's algorithm
• hash function
• hash table delete
• heapify
• heapsort
• highest common factor
• histogram sort
• Horner's rule
• Horspool
• hsadelta
• Huffman coding
• Hungarian algorithm
• ideal merge
• ideal random shuffle
• in-order traversal
• in-place sort
• insertion sort
• interpolation search
• interpolation-sequential search
• interpolation sort
• introsort
• introspective sort
• inverse Ackermann function
• Jaro-Winkler
• Johnson's algorithm
• Johnson-Trotter
• JSort
• J sort
• jump search
• Karnaugh map
• Karp-Rabin
• k-ary Huffman coding
• KMP
• KmpSkip Search
• Knuth-Morris-Pratt algorithm
• Kruskal's algorithm
• KV diagram
• k-way merge sort
• left rotation
• Lempel-Ziv-Welch
• level-order traversal
• linear congruential generator
• linear hash
• linear insertion sort
• linear probing sort
• linear search
• locality-sensitive hashing
• lucky sort
• LZW compression
• Malhotra-Kumar-Maheshwari blocking flow
• Maximal Shift
• merge sort
• metaphone
• Miller-Rabin
• minimal perfect hashing
• minimax
• model checking
• MODIFIND
• Morris-Pratt algorithm
• move-to-front heuristic
• move-to-root heuristic
• multiplication method
• multiprefix
• Munkres' assignment algorithm
• naive string search
• nonbalanced merge
• nonbalanced merge sort
• Not So Naive
• NYSIIS
• open addressing
• optimal hashing
• optimal merge
• optimal mismatch
• optimal polyphase merge
• optimal polyphase merge sort
• order-preserving hash
• order-preserving Huffman coding
• order-preserving minimal perfect hashing
• oscillating merge sort
• parallel prefix computation
• Pearson's hash
• perfect hashing
• perfect shuffle
• permutation
• pigeonhole sort
• polyphase merge
• polyphase merge sort
• postfix traversal
• postman's sort
• postorder traversal
• prefix sums
• prefix traversal
• preorder traversal
• Prim-Jarnik algorithm
• PRNG
• pseudo-random number generator
• p-way merge sort
• qm sort
• q sort
• quadratic probing
• quick search
• quicksort
• Rabin-Karp
• radix sort
• Raita
• randomized rounding
• random number generator
• random search
• range sort
• rapid sort
• Ratcliff/Obershelp pattern recognition
• rebalance
• rehashing
• repeated squaring
• reservoir sampling
• Reverse Colussi
• Reverse Factor
• right rotation
• RNG
• rotate left
• rotate right
• scan
• scapegoat tree
• Schorr-Waite graph marking algorithm
• search
• secant search
• Select
• selection sort
• select mode
• self-organizing sequential search
• sequential search
• shadow merge
• shadow merge insert
• shaker sort
• Shannon-Fano coding
• Shell sort
• Shift-Or
• Shor's algorithm
• shuffle
• shuffle sort
• sieve of Eratosthenes
• sift up
• Simon's algorithm
• simple merge
• simulated annealing
• sinking sort
• skip search
• Smith algorithm
• Smith-Waterman algorithm
• smoothsort
• sort
• sort in place
• soundex
• space ordering method
• square root
• star encoding
• static Huffman coding
• Steinhaus-Johnson-Trotter
• stooge sort
• strand sort
• string matching on ordered alphabets
• string matching with errors
• string matching with mismatches
• stupid sort
• taco sort
• three-way merge sort
• top-down radix sort
• tournament
• tournament sort
• transpose sequential search
• treesort (1)
• treesort (2)
• tripartition
• Turbo-BM
• Turbo Reverse Factor
• Two Way algorithm
• two-way merge sort
• uniform hashing
• union of automata
• UnShuffle sort
• Veitch diagram
• Viterbi algorithm
• Vitter's algorithm
• weak-heap sort
• Zeller's congruence
• Zhu-Takaoka

Data Structures

• (a,b)-tree
• active data structure
• adaptive k-d tree
• adjacency-list representation
• adjacency-matrix representation
• array
• association list
• associative array
• AVL tree
• bag
• balanced binary search tree
• balanced binary tree
• balanced multiway tree
• balanced tree
• BANG file
• BB(α) tree
• BDD
• BD-tree
• binary heap
• binary priority queue
• binary search tree
• binary tree
• binary tree representation of trees
• binomial heap
• binomial tree
• bintree
• bit vector
• B_k tree
• blind trie
• block addressing index
• bounded queue
• bounded stack
• B⁺-tree
• BSP-tree
• B*-tree
• B-tree
• bucket array
• bucket trie
• buddy tree
• BV-tree
• cactus stack
• calendar queue
• cartesian tree
• cell tree
• chaining
• circular list
• circular queue
• coalesced chaining
• coding tree
• compact DAWG
• compact trie
• complete binary tree
• complete tree
• cuckoo hashing
• DAWG
• deque
• dictionary
• diet
• digital search tree
• digital tree
• digraph
• direct chaining
• directed acyclic word graph
• directed graph
• discrete interval encoding tree
• double-ended priority queue
• doubly-chained tree
• doubly-ended queue
• doubly linked list
• D-tree
• dyadic tree
• dynamic array
• dynamic hashing
• elastic-bucket trie
• enfilade
• EXCELL
• extended binary tree
• extended k-d tree
• extendible hashing
• external chaining
• external index
• external memory data structure
• Fibonacci heap
• Fibonacci tree
• FIFO
• filial-heir chain
• finitary tree
• first child-next sibling binary tree
• forward index
• full binary tree
• full inverted index
• functional data structure
• GBD-tree
• graph
• grid file
• hashbelt
• hash heap
• hash table
• hB-tree
• heap
• height-balanced binary search tree
• height-balanced tree
• hidden Markov model
• HMM
• huge sparse array
• hypergraph
• incremental hashing
• index file
• inverse suffix array
• inverted file index
• inverted index
• jelly-fish
• jump list
• k-ary heap
• k-ary tree
• k-d-B-tree
• k-d tree
• k-way tree
• leftist tree
• LIFO
• linear hashing
• linear probing
• linear quadtree
• linked list
• list
• lower triangular matrix
• map
• Markov chain
• matrix
• monotone priority queue
• multigraph
• multilayer grid file
• multi-set
• multi suffix tree
• multiway search tree
• multiway tree
• octree
• ordered array
• ordered linked list
• ordered tree
• oriented graph
• orthogonal lists
• pagoda
• passive data structure
• Patricia tree
• pile
• PLOP-hashing
• priority queue
• proper binary tree
• property list
• P-tree
• quadtree
• quad trie
• queue
• radix tree
• ragged matrix
• randomized binary search tree
• randomized search tree
• RBST
• rectangular matrix
• recursive
• red-black tree
• reduced ordered binary decision diagram
• relational structure
• R-file
• right-threaded tree
• ROBDD
• R⁺-tree
• R^*-tree
• R-tree
• saguaro stack
• SBB tree
• scatter storage
• search tree
• self-organizing list
• separate chaining
• set
• shadow heap
• singly linked list
• skd-tree
• skip list
• sorted array
• sorted list
• sparse matrix
• spiral storage
• splay tree
• square matrix
• stack
• st-digraph
• strictly lower triangular matrix
• strictly upper triangular matrix
• string
• suffix array
• suffix tree
• symmetrically linked list
• symmetric binary B-tree
• ternary search tree
• threaded binary tree
• threaded tree
• treap
• tree
• trie
• TST
• twin grid file
• 2-choice hashing
• 2-left hashing
• two-level grid file
• 2-3-4 tree
• 2-3 tree
• two-way linked list
• UB-tree
• undirected graph
• uniform matrix
• universal B-tree
• unlimited branching tree
• upper triangular matrix
• van Emde-Boas priority queue
• weak-heap
• weight-balanced tree
• zipper

Algorithmic Techniques

• ρ-approximation algorithm
• approximation algorithm
• backtracking
• branch and bound
• British Museum technique
• brute force
• collective recursion
• decimation
• deterministic algorithm
• divide and conquer
• divide and marriage before conquest
• dynamic programming
• dynamization transformation
• easy split, hard merge
• exhaustive search
• fathoming
• fully polynomial approximation scheme
• greedy algorithm
• greedy heuristic
• hard split, easy merge
• heuristic
• iteration
• Las Vegas algorithm
• memoization
• metaheuristic
• Monte Carlo algorithm
• nondeterministic algorithm
• parametric searching
• pipelined divide and conquer
• polynomial approximation scheme
• prune and search
• PTAS
• randomization
• random sampling
• recursion
• sparsification
• symmetry breaking
• tail recursion

Classic Problems

• all pairs shortest path
• all simple paths
• array search
• assignment problem
• binary knapsack problem
• bin packing problem
• bottleneck traveling salesman
• busy beaver
• Byzantine generals
• capacitated facility location
• Chinese postman problem
• clique problem
• Collatz problem
• continuous knapsack problem
• critical path problem
• cutting stock problem
• dining philosophers
• discrete p-center
• Dutch national flag
• 8 queens
• element uniqueness
• Euclidean traveling salesman problem
• exact string matching
• facility location
• find k^th least element
• finite state machine minimization
• fractional knapsack problem
• graph drawing
• graph isomorphism
• graph partition
• halting problem
• heaviest common subsequence
• knapsack problem
• knight's tour
• k^th shortest path
• k^th smallest element
• LCS
• longest common subsequence
• longest common substring
• marriage problem
• matrix-chain multiplication problem
• maximal independent set
• maximum-flow problem
• nearest neighbor
• network flow problem
• n queens
• optimal polygon triangulation problem
• optimal triangulation problem
• path system problem
• PCP
• phonetic coding
• Post's correspondence problem
• prisoner's dilemma
• select and partition
• selection problem
• select k^th element
• set cover
• set packing
• shortest common supersequence
• shortest common superstring
• shortest path
• single-destination shortest-path problem
• single-pair shortest-path problem
• single-source shortest-path problem
• slope selection
• string matching
• string searching
• strip packing
• subgraph isomorphism
• text searching
• towers of Hanoi
• traveling salesman
• TSP
• UKP
• unbounded knapsack problem
• vehicle routing problem
• vertex cover
• VRP
• 0-1 knapsack problem

Definitions

• ω
• Ω
• ~
• Θ
• absolute performance guarantee
• abstract data type
• accepting state
• acyclic directed graph
• acyclic graph
• adaptive sort
• adjacent
• admissible vertex
• ADT
• adversary
• algorithm
• algorithmically solvable
• alphabet
• alternating path
• alternating Turing machine
• alternation
• amortized cost
• ancestor
• and
• ANSI
• antichain
• antisymmetric
• arborescence
• arc
• array index
• articulation point
• associative
• 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
• axiomatic semantics
• balance
• Benford's law
• best case
• best-case cost
• biconnected component
• biconnected graph
• big-O notation
• binary function
• binary relation
• bipartite graph
• bipartite matching
• bisector
• block
• blocking flow
• blossom
• boolean
• boolean expression
• boolean function
• border
• bottom-up tree automaton
• boundary-based representation
• bounded error probability in polynomial time
• BPP
• Bradford's law
• bridge
• bucket
• bucketing method
• Calculus of Communicating Systems
• candidate consistency testing
• candidate verification
• canonical complexity class
• capacity
• capacity constraint
• CCS
• cell probe model
• cellular automaton
• centroid
• certificate
• chain
• child
• chromatic index
• chromatic number
• circuit
• circuit complexity
• circuit value problem
• clique
• clustering
• clustering free
• coarsening
• codeword
• collision
• Communicating Sequential Processes
• commutative
• comparison sort
• competitive analysis
• competitive ratio
• complement
• complete graph
• completely connected graph
• 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
• Cook reduction
• Cook's theorem
• covering
• CRCW
• CREW
• CSP
• CTL
• cut
• cutting plane
• cutting theorem
• cut vertex
• cycle
• D-adjacent
• DAG
• data structure
• decidable language
• decidable problem
• decision problem
• decomposable searching problem
• degree
• dense graph
• depoissonization
• depth
• descendant
• deterministic
• deterministic finite automaton
• deterministic finite state machine
• deterministic finite tree automaton
• deterministic pushdown automaton
• deterministic tree automaton
• DFA
• DFS forest
• DFTA
• diagonalization
• diameter
• dichotomic search
• difference
• directed acyclic graph
• disjoint set
• disjunction
• distributional complexity
• domain
• don't care
• DPDA
• dual
• dual linear program
• dynamic
• edge
• edge coloring
• edge connectivity
• edge crossing
• edge-weighted graph
• edit distance
• edit operation
• edit script
• efficiency
• end-of-string
• ERCW
• EREW
• Euclidean distance
• Euclidean Steiner tree
• Euler cycle
• Eulerian graph
• Eulerian path
• exclusive or
• exclusive read, concurrent write
• exclusive read, exclusive write
• existential state
• expander graph
• exponential
• external node
• external sort
• extremal
• extreme point
• factor
• factorial
• feasible region
• feasible solution
• feedback edge set
• feedback vertex set
• Fibonacci number
• finite state automaton
• finite state machine
• finite state transducer
• first come, first served
• first-in, first-out
• fixed-grid method
• flow
• flow conservation
• flow function
• flow network
• forest
• forest editing problem
• formal language
• formal methods
• formal verification
• fractional solution
• free edge
• free tree
• free vertex
• full array
• fully dynamic graph problem
• fully persistent data structure
• function
• gamma function
• geometric optimization problem
• global optimum
• graph coloring
• graph concentration
• Gray code
• grid drawing
• Hamiltonian cycle
• Hamiltonian path
• Hamming distance
• Hausdorff distance
• head
• heap property
• height
• homeomorphic
• horizontal visibility map
• hybrid algorithm
• hyperedge
• implication
• implies
• inclusion-exclusion principle
• inclusive or
• incompressible string
• in-degree
• independent set
• information theoretic bound
• integer linear program
• integer multi-commodity flow
• integer polyhedron
• interactive proof system
• interior-based representation
• internal node
• internal sort
• intersection
• intractable
• irreflexive
• isomorphic
• Karp reduction
• k-coloring
• k-connected graph
• k-dimensional
• K-dominant match
• key
• Königsberg bridges problem
• Kolmogorov complexity
• Kraft's inequality
• Kripke structure
• kth order Fibonacci numbers
• k-way merge
• labeled graph
• language
• last-in, first-out
• lattice
• layered graph
• LCM
• leaf
• least common multiple
• level
• Levenshtein distance
• lexicographical order
• linear
• linear order
• linear product
• linear program
• link
• list contraction
• little-o notation
• L_m distance
• load factor
• local alignment
• local optimum
• logarithmic
• Lotka's law
• lower bound
• lowest common ancestor
• l-reduction
• Manhattan distance
• many-one reduction
• Marlena
• Master theorem
• matched edge
• matched vertex
• matching
• max-heap property
• maximally connected component
• maximum bipartite matching
• MAX-SNP
• MBB
• Mealy machine
• mean
• median
• meld
• merge
• midrange
• min-heap property
• minimum bounding box
• minimum cut
• minimum spanning tree
• minimum vertex cut
• Minkowski distance
• mixed integer linear program
• mode
• model of computation
• moderately exponential
• monotonically decreasing
• monotonically increasing
• Moore machine
• move
• MST
• multi-commodity flow
• multiprocessor model
• multiway decision
• multiway merge
• nand
• n-ary function
• NC many-one reducibility
• negation
• network flow
• next state
• NFA
• NFTA
• NIST
• node
• nondeterministic
• nondeterministic finite automaton
• nondeterministic finite state machine
• nondeterministic finite tree automaton
• nondeterministic polynomial time
• nondeterministic tree automaton
• nondeterministic Turing machine
• nonterminal node
• nor
• not
• NP
• NP-complete
• NP-complete language
• NP-hard
• nullary function
• null tree
• O
• objective function
• occurrence
• off-line algorithm
• offset
• omega
• omicron
• one-based indexing
• one-dimensional
• on-line algorithm
• optimal
• optimal cost
• optimal solution
• optimal value
• optimization problem
• or
• oracle set
• oracle tape
• oracle Turing machine
• order
• oriented acyclic graph
• oriented tree
• orthogonal drawing
• orthogonally convex rectilinear polygon
• out-degree
• P
• packing
• padding argument
• PAM
• parallel computation thesis
• parallel random-access machine
• parent
• partial function
• partially decidable problem
• partially dynamic graph problem
• partially ordered set
• partially persistent data structure
• partial order
• partial recursive function
• partition
• path
• pattern
• pattern element
• P-complete
• PDA
• perfect binary tree
• perfect k-ary tree
• perfect matching
• performance guarantee
• performance ratio
• persistent data structure
• planar graph
• planarization
• planar straight-line graph
• point access method
• pointer jumping
• pointer machine
• poissonization
• polychotomy
• polyhedron
• polylogarithmic
• polynomial
• polynomial hierarchy
• polynomial time
• polynomial-time reduction
• polytope
• poset
• potential function
• PRAM
• predicate
• prefix
• prefix code
• primary clustering
• primitive recursive
• principle of optimality
• probabilistic algorithm
• probabilistically checkable proof
• probabilistic Turing machine
• probe sequence
• procedure
• process algebra
• proper
• proper coloring
• proper subset
• pth order Fibonacci numbers
• purely functional language
• pushdown automaton
• pushdown transducer
• quadtree complexity theorem
• quantum computation
• random access machine
• randomized algorithm
• randomized complexity
• randomized polynomial time
• range
• rank
• reachable
• recognizer
• rectilinear
• rectilinear Steiner tree
• recurrence equations
• recurrence relation
• recursion termination
• recursion tree
• recursive data structure
• recursive doubling
• recursive language
• recursively enumerable language
• recursively solvable
• reduced basis
• reduced digraph
• reduction
• reflexive
• regular decomposition
• relation
• relative performance guarantee
• relaxation
• relaxed balance
• rescalable
• restricted universe sort
• Rice's method
• root
• root balance
• rooted tree
• rotation
• rough graph
• RP
• run time
• SAM
• saturated edge
• search tree property
• secondary clustering
• segment
• self-loop
• semidefinite programming
• separation theorem
• shared memory
• shortcutting
• shortest spanning tree
• sibling
• signature
• simple path
• simple uniform hashing
• simplex
• simulation theorem
• single program multiple data
• singularity analysis
• sink
• skew symmetry
• solvable
• source
• space-constructible function
• spanning tree
• sparse graph
• sparsity
• spatial access method
• SPMD
• SST
• stable
• stack tree
• star-shaped polygon
• start state
• state
• state machine
• state transition
• static
• s-t cut
• Steiner point
• Steiner ratio
• Steiner tree
• Steiner vertex
• Stirling's approximation
• Stirling's formula
• straight-line drawing
• strictly decreasing
• strictly increasing
• string editing problem
• strongly connected component
• strongly connected graph
• strongly NP-hard
• subadditive ergodic theorem
• subgraph
• sublinear time algorithm
• subsequence
• subset
• substring
• subtree
• suffix
• suffix automaton
• superimposed code
• superset
• supersink
• supersource
• symmetric
• symmetric set difference
• tail
• target
• temporal logic
• terminal
• terminal node
• text
• theta
• three-dimensional
• time-constructible function
• time/space complexity
• top-down tree automaton
• topological order
• topological sort
• topology tree
• total function
• totally decidable language
• totally decidable problem
• totally undecidable problem
• total order
• tour
• tractable
• transition
• transition function
• transitive
• transitive closure
• transitive reduction
• tree automaton
• tree contraction
• tree editing problem
• tree traversal
• triangle inequality
• triconnected graph
• trinary function
• Turing machine
• Turing reduction
• Turing transducer
• two-dimensional
• unary function
• uncomputable function
• uncomputable problem
• undecidable language
• undecidable problem
• uniform circuit complexity
• uniform circuit family
• union
• universal hashing
• universal state
• universal Turing machine
• universe
• unsolvable problem
• unsorted list
• Venn diagram
• vertex
• vertex coloring
• vertex connectivity
• vertical visibility map
• visibility map
• visible
• walk
• WCET
• weighted, directed graph
• weighted graph
• window
• witness
• work
• work-depth model
• work-efficient
• work-preserving
• worst case
• worst-case cost
• worst-case execution time
• worst-case minimum access
• xor
• Yule distribution
• 0-ary function
• 0-based indexing
• Zipfian distribution
• Zipf's law
• ZPP

Entries with No Type

• cascade merge sort
• division method
• double left rotation
• double right rotation
• expandable hashing
• interval tree
• k-clustering
• minimum path cover
• multikey Quicksort
• OBDD
• oblivious algorithm
• ordered binary decision diagram
• pairing heap
• path cover
• Post machine
• prefix computation
• Randomized-Select
• result cache
• Robin Hood hashing
• three-way radix quicksort
• virtual hashing

This page's URL is http://www.nist.gov/dads/termsType.html

This web site is hosted by the Software and Systems Division, Information Technology Laboratory, NIST in collaboration with the FASTAR group. NIST is an agency of the U.S. Department of Commerce.
PRIVACY POLICY/SECURITY NOTICE/ACCESSIBILITY STATEMENT