Unified Index of the Dictionary of Algorithms and Data Structures
This is a unified index of all terms in the
Dictionary, including many created only for web searches. For
instance, TSP is listed under "traveling salesman" (one "l" in
"traveling"), the American spelling, and "travelling salesman" (two
"l"s), the British spelling. Other variants are "quick sort" and
"quicksort", and "sort" and "sorting algorithm".
Doubly linked list and its synonyms appears four times: as
doubly linked list, symmetrically linked list, two-way linked list,
and two-way list. The last two would occur close to each other in the
main index , so "two-way list" is only in
this index, which is for
robots
to find and index.
This page was never intended for human use. If you find a use for
this page and have a suggestion to make it more usable, don't hesitate to contact us. If you have suggestions, corrections, or comments, please get in touch
with Vadim Okun .
Run on Fri Feb 7 12:45:33 2025
α ω Ω ρ-approximation algorithm ∼ Θ ABKU hashing absolute performance guarantee abstract data type (a,b)-tree accepting state Ackermann-Peter function Ackermann's function Ackerman's function active data structure acyclic digraph acyclic directed graph acyclic graph adaptive heapsort adaptive heap sort adaptive Huffman coding adaptive Hufman coding adaptive k-d tree adaptive sort address-calculation sort adjacency list adjacency-list representation adjacency matrix adjacency-matrix representation adjacent admissible tree admissible vertex ADT adversary aglorithm Aho-Corasick algarhythm algarithm algolrythm algorhythm algoritham algorithim algorithm algorithm BSTW algorithm FGK algorithmically solvable algorithms Algorithm V algorithum algorithym algorythm all pairs shortest path all paths all simple paths alphabet Alpha Skip Search algorithm alternating path alternating Turing machine alternation always-go-left hashing American flag sort amortized cost amortized worst case ancestor and ANSI antichain antisymmetric Apostolico-Crochemore Apostolico-Giancarlo algorithm approximate string matching approximation algorithm arborescence arc arithmetic coding arithmetic encoding array array index array merging array search articulation point articulation vertex assignment problem association list associative associative array assoc list asymptotically equal to asymptotically tight bound asymptotic bound asymptotic space complexity asymptotic tight bound asymptotic time complexity asymptotic upper bound augmenting path automaton average case average-case cost AVL tree axiomatic semantics 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 Batcher's sort Baum Welch algorithm Bayer tree BB(α) tree BBP algorithm BDD BD-tree Bellman-Ford algorithm Benford's law best case best-case cost best-first search BFS biconnected component biconnected graph bidirectional bubble sort big-O notation binary decision diagram 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 queue binomial tree bin packing problem bin sort bintree bipartite graph bipartite matching bisector bitonic sort bit vector BKP Bk tree blind sort blind trie block block addressing index blocking flow block search block searching Bloom filter blossom bogo-sort bogosort bogus sort Bond Sequential Search boolean boolean expression boolean function border Boruvka's algorithm bottleneck traveling salesman boundary-based representation bounded error probability in polynomial time bounded queue bounded stack Boyer-Moore Boyer-Moore-Horspool bozo sort BP B+ -tree BPP Bradford's law branch and bound branching program breadth-first search Bresenham's algorithm bridge British Museum algorithm British Museum technique brute force brute force string search brute force string search with mismatches bsearch BSP-tree BSS 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 Agreement Problem Byzantine generals Byzantine generals problem cactus stack Calculus of Communicating Systems calendar queue candidate consistency testing candidate verification canonical complexity class capacitated facility location capacity capacity constraint cartesian tree Caverphone CBT 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 circuit circuit complexity circuit value problem circular list circular queue city block norm clique clique problem closed hashing closed path clustering clustering free coalesced chaining coalesced hashing coarsening cocktail shaker sort code word codeword coding tree Collatz problem collective recursion collision collision resolution scheme Colussi combination comb sort Commentz-Walter Communicating Sequential Processes commutative compact data structure compact DAWG compact trie comparison sort competitive analysis competitive ratio complement complete binary tree complete graph complete k -ary tree completely connected graph complete tree complexity complexity class compliment compound algorithm computable computable function concave function concurrent data structure 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 COrdinate Rotation DIgital Computer counting sort covering CPP CRC CRCW CREW critical path problem Crochemore-Perrin string matching CSP CTL cube root cuckoo hashing Cupif-Giannini tree traversal Cupif-Giannini tree walk cut cutting plane cutting stock problem cutting theorem cut vertex cycle cyclic redundancy check D-adjacent DAG DAG shortest paths database data base data structure data structure persistance data structure persistence DAWG decidable language decidable problem decimation decision problem decomposable searching problem decreasing increment sort 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 automaton deterministic finite state machine deterministic finite tree automaton deterministic pushdown automaton deterministic random bit generator deterministic tree automaton Deutsch-Jozsa algorithm Deutsch-Schorr-Waite algorithm DFA DFS DFS forest DFTA diagonalization diameter Dianna 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 directory discrete interval encoding tree discrete p-center disjoint set disjunction distributional complexity distribution sort distributive partitioning sort divide and conquer divide and marriage before conquest Dobosiewicz sort domain dominance tree sort don't care doomsday algorithm 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 d-random scheme DRBG DSW D-tree dual dual linear program dual-pivot quicksort Dutch national flag dyadic tree dynamic dynamic array dynamic hashing dynamic hash table dynamic Huffman coding dynamic programming dynamization transformation Easter date easy split, hard merge edge edge coloring edge connectivity edge crossing edge-weighted graph edit distance edit operation edit script efficiency eight queens 8 queens elastic-bucket trie element uniqueness EM data structure 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 Euler's formula Euler tour 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 exponentiation by repeated squaring 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 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 search Fibonacci tree Fibonnaci heap Fibonnaci numbers FIFO filial-heir chain Find find kth least element finitary tree finite automaton 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 inverted index fully persistent data structure fully polynomial approximation scheme function functional data structure Galil-Giancarlo Galil-Seiferas gamma function GBD-tree GCD geometric optimization problem globally optimal global optimum gnome sort graph graph coloring graph concentration graph drawing graph isomorphism graph partition Gray code greatest common denominator greatest common divisor greedy algorithm greedy heuristic grey code grid drawing grid file Grover's algorithm halting problem Hamiltonian circuit Hamiltonian cycle Hamiltonian path Hamming distance hard split, easy merge hash hashbelt hash function hash heap hash table hash table delete hash tree Hausdorff distance hB-tree HCF head heap heap condition heapify heap ordered heap property heap sort 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 hsadelta hueristic Huffman coding Huffman encoding Huffmann compression Hufman encoding huge sparse array Hungarian algorithm hybrid algorithm hyperedge hypergraph HyperLogLog IBLT ideal merge ideal random shuffle implication implies inclusion-exclusion principle inclusive or incompressible string incremental hashing in-degree independent set index file infix traversal information theoretic bound inorder traversal in-order traversal in-place sort insertion sort integer linear program integer multi-commodity flow integer polyhedron interactive proof system interior-based representation interior node internal node internal sort interpolation search interpolation-sequential search interpolation sort intersection interval tree intractable introsort intro sort introspection sort introspective sort inverse Ackermann function inverse Ackerman's function inverse suffix array inversion list inverted file inverted file index inverted index invertible Bloom lookup table irreflexive isomorphic iteration Jaro-Winkler jelly-fish jellyfish data structure jelly fish structure Johnson's algorithm Johnson-Trotter jsort JSort j sort J sort jump list jump search Karnaugh map Karp-Rabin Karp reduction k-ary heap k-ary Huffman coding k-ary Hufman encoding 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 Knuth-Pratt-Morris algorithm Königsberg bridges problem Koenigsberg bridges problem Kolmogorov complexity KPM Kraft's inequality Kripke structure Kruskal's algorithm kth order Fibonacci numbers kth shortest path kth shortest path kth smallest element k²-tree KV diagram k-way merge k-way merge sort k-way tree labeled graph Landau symbol language Last-Come First-Served Last-Come First-Served Hashing last-in, first-out Las Vegas algorithm lattice layered digraph layered graph LCFS LCFS hashing LCM LCRS binary tree LCS LDS leaf least common multiple left child-right sibling binary tree leftist tree left rotation left single rotation Lempel-Ziv Lempel-Ziv-Welch Lempel-Ziv-Welch data compression level level-order traversal Levenshtein distance Levenshtein string 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 data signature linked list list list contraction little-o notation Lm distance load factor local alignment locality-sensitive hashing locally optimal local optimum logarithmic longest common subsequence longest common substring Lotka's law lower bound lower triangular matrix lowest common ancestor l-reduction LSH lucksort luckysort lucky sort LZW compression 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 matrix multiplication max-heap property maximal independent set maximally connected component Maximal Shift maximum bipartite matching maximum-flow problem maximum-heap property MBB Mealy machine mean median meld memoization memoize merge merge exchange sort mergesort merge sort Merkle tree metaheuristic metaphone midrange Miller-Rabin Miller-Rabin probabilistic primality test min-heap property minimal code spanning tree minimal perfect hashing minimax minimum bounding box minimum cost spanning tree minimum cut minimum spanning tree minimum Steiner tree minimum vertex cut Minkowski distance minmax 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 algorithm move move-to-front heuristic move-to-root heuristic MST multi-commodity flow multigraph multikey Quicksort multilayer grid file multiplication method multiplicative hashing multiprefix multiprocessor model multi-set multiset multi suffix tree multiway decision multiway merge multiway search tree multiway tree Munkres' assignment algorithm naive string search nand nap sack napsack 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 NPC NP-complete NP-complete language NP-hard n queens nullary function null tree NYSIIS O OBDD objective function oblivious algorithm oblivious binary decision diagram occurrence octree octtree odd shaped array off-line algorithm offset Oh notation omega omicron 1-based array one-based indexing 1-based indexing one-dimensional on-line algorithm O notation o notation 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 Huffman coding order preserving Huffman compression 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 packing padding argument pagoda pairing heap PAM parallel computation thesis parallel prefix computation parallel random-access machine parallel search 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 PD PDA Pearson's hash perfect binary tree perfect hashing perfect k -ary tree perfect match perfect matching perfect shuffle performance guarantee performance ratio permutation permutation sort permute persistant data structure persistent data structure persistent data structure with confluence phonetic coding phonetic encoding phonetic matching phonetic string match pigeonhole sort pile pipelined divide and conquer planar graph planarity 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 algorithm polynomial-time approximation scheme polynomial-time reduction polyphase merge polyphase merge sort polytope poset postfix traversal Post machine postman sort postman's sort postorder traversal Post's correspondence problem potential function PRAM predicate prefix prefix code prefix sums prefix traversal preorder traversal primary clustering primitive algorithm primitive recursive Prim-Jarník Prim-Jarnik algorithm Prim's algorithm principle of optimality priority queue priority queue ordering 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 prop list prune and search pseudorandom number pseudo-random number generator PTAS pth order Fibonacci numbers P-tree purely functional language pushdown pushdown automaton push-down store pushdown transducer p-way merge sort qmsort qm sort qsort q sort quadratic hashing quadratic probing quadtree quadtree complexity theorem quad trie quantum computation queue quick-er sort quick search quickselect quick select quick sort quicksort Rabin-Karp 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 random search range range sort rank rapid sort Ratcliff/Obershelp pattern recognition RBST reachability reachable rebalance recognizer rectangular matrix rectilinear rectilinear distance rectilinear Steiner tree recurrence equations recurrence relation recurrences 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 r.e. language relation relational structure relative performance guarantee relaxation relaxed balance repeated squaring rescalable reservoir sampling restricted universe sort Reverse Colussi Reverse Factor R-file rho-approximation algorithm Rice's method right rotation right single rotation right-threaded tree RNG ROBDD Robin-hood hashing robinhood hashing Robin Hood hashing root root balance rooted tree rotate left rotate right rotation rough graph RP R+ -tree R* -tree R-tree run time saguaro stack SAM saturated edge SBB tree scan scapegoat tree scatter storage Schorr-Waite graph marking algorithm search search tree search tree property secant search secondary clustering segment Select select and partition selection problem selection sort select kth element select mode self-adjusting binary search tree self-loop self-organizing list self-organizing sequential search semidefinite programming separate chaining separation theorem sequential search set set complement set cover set covering problem set difference set intersection set packing set union shadow heap shadow merge shadow merge insert shaker sort Shannon-Fano coding shared memory Shell-Metzner sort shellsort Shell sort Shift-Or Shor's algorithm shortcutting short cutting shortest common supersequence shortest common superstring shortest path shortest spanning tree shuffle shuffle sort shuttle sort sibling sieve of Eratosthenes sift up signature Simon algorithm Simon's algorithm simple merge simple path simple tabulation hash function 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 sink sort skd-tree skew symmetry skiplist skip list skip search slope selection Smith algorithm Smith-Waterman algorithm smoothsort solvable sort sorted array sorted list sorted-string table sorting algorithm sort in place sort in-place soundex source source-target directed acyclic graph space-constructible function space ordering method spanning tree sparse array sparse graph sparse matrix sparsification sparsity spatial access method spiral storage splaying splay tree SPMD square matrix square root SST SSTable stable stack stack tree star encoding star-shaped polygon start state state state machine state transition static static Huffman coding s-t cut st-digraph Steiner minimum tree 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 search string searching string similarity search strip packing strongly connected component strongly connected graph strongly NP-hard strsrch stupid sort subadditive ergodic theorem subgraph subgraph isomorphism sublinear time algorithm subsequence subset substring subtree subword suffix suffix array suffix automaton suffix tree superimposed code superset supersink supersource symmetric symmetrically linked list symmetrical traversal symmetric binary B-tree symmetric set difference symmetric traversal symmetry breaking tabulation hashing tacosort taco sort tail tail recursion target taxi cab metric temporal logic terminal terminal node ternary search tree text text match 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 top sort 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 traveling salesman problem travelling salesman problem treap tree tree automaton tree contraction tree editing problem tree sort treesort (1) treesort (2) tree traversal triangle inequality triconnected graph trie trinary function tripartition Trotter-Johnson TSP TST Turbo-BM Turbo Reverse Factor Turing machine Turing reduction Turing transducer twin grid file twisted tabulation hashing 2-choice hashing two-dimensional 2-left hashing 2-left scheme two-level grid file two-terminal dag 2-3-4 tree 2-3 tree Two Way algorithm 2-way chaining two-way linked list two-way list two-way merge sort UB UB-tree UKP unary function unbiased coin flipping algorithm unbounded knapsack problem uncomputable function uncomputable problem undecidable language undecidable problem undirected graph uniform circuit complexity uniform circuit family uniform greedy algorithm uniform hashing uniform matrix union union of automata universal B-tree universal hashing universal state universal Turing machine universe unlimited branching tree unranking UnShuffle sort unsolvable problem unsorted list upper triangular matrix van Emde-Boas priority queue vehicle routing problem Veitch diagram Venn diagram vertex vertex coloring vertex connectivity vertex cover vertex covering problem vertical visibility map virtual hashing visibility map visible Viterbi algorithm Viterbi search Vitter's algorithm von Neumann's coin flip algorithm VRP walk WCET weak-heap weak-heap sort weight-balanced tree weighted digraph 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 Zeller's algorithm Zeller's congruence 0-ary function zero-based array 0-based indexing zero error probability in polynomial time 0-1 knapsack problem Zhu-Takaoka Zipfian distribution Zipf's law zipper Zobrist hashing ZPP
Dictionary of Algorithms and Data
Structures home page.
Created
Thu Jan 17 10:55:24 2002
by Vadim Okun
([email protected]
This Trailer
Updated
Mon Sep 18 10:16:45 2017
by Paul E. Black
This page's URL is
https://www.nist.gov/dads/ui.html
This web site is hosted by
the
Software and Systems Division ,
Information Technology Laboratory ,
NIST .
NIST is an agency of the
U.S. Department of Commerce .
PRIVACY
POLICY/SECURITY NOTICE/ACCESSIBILITY STATEMENT
