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 terms are missing or you can add or correct definitions, please contact me by email (paul.black@nist.gov) or by other means.

Run on Thu May 15 12:22:55 2008

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

• binary knapsack problem [P]
• bin packing problem [P]
• Collatz problem [P]
• combination [A]
• continuous knapsack problem [P]
• covering [D]
• cutting stock problem [P]
• dual linear program [D]
• dynamic [D]
• dynamic programming [T]
• edit distance [D]
• edit operation [D]
• edit script [D]
• 8 queens [P]
• Fisher-Yates shuffle [A]
• forest editing problem [D]
• fractional knapsack problem [P]
• global optimum [D]
• greedy algorithm [T]
• greedy heuristic [T]
• Hungarian algorithm [A]
• integer linear program [D]
• Johnson-Trotter [A]
• K-dominant match [D]
• knapsack problem [P]
• knight's tour [P]
• Las Vegas algorithm [T]
• Levenshtein distance [D]
• linear program [D]
• local optimum [D]
• Master theorem [D]
• matrix-chain multiplication problem [P]
• mixed integer linear program [D]
• Monte Carlo algorithm [T]
• Munkres' assignment algorithm [A]
• n queens [P]
• packing [D]
• partition [D]
• perfect shuffle [A]
• permutation [A]
• principle of optimality [D]
• semidefinite programming [D]
• set cover [P]
• set packing [P]
• shuffle [A]
• static [D]
• Steinhaus-Johnson-Trotter [A]
• string editing problem [D]
• strip packing [P]
• towers of Hanoi [P]
• transitive closure [D]
• tree editing problem [D]
• tripartition [A]
• UKP [P]
• unbounded knapsack problem [P]
• witness [D]
• 0-1 knapsack problem [P]

Cryptography and Compression

• adaptive Huffman coding [A]
• algorithm BSTW [A]
• algorithm FGK [A]
• arithmetic coding [A]
• Burrows-Wheeler transform [A]
• BWT [A]
• codeword [D]
• coding tree [S]
• CRC [A]
• cyclic redundancy check [A]
• dynamic Huffman coding [A]
• Gray code [D]
• Hamming distance [D]
• hsadelta [A]
• Huffman coding [A]
• k-ary Huffman coding [A]
• Lempel-Ziv-Welch [A]
• LZW compression [A]
• order-preserving Huffman coding [A]
• prefix code [D]
• PRNG [A]
• pseudo-random number generator [A]
• Shannon-Fano coding [A]
• star encoding [A]
• static Huffman coding [A]
• superimposed code [D]
• Vitter's algorithm [A]
• Yule distribution [D]
• Zipfian distribution [D]
• Zipf's law [D]

External Memory Algorithms and Data Structures

• external memory algorithm [A]
• external memory data structure [S]

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]
• Christofides heuristic [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]
• 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

• BBP algorithm [A]
• Benford's law [D]
• binary GCD [A]
• centroid [D]
• Chinese remainder theorem [A]
• CORDIC [A]
• cube root [A]
• Euclidean algorithm [A]
• Euclid's algorithm [A]
• extended Euclid's algorithm [A]
• factorial [D]
• fast fourier transform [A]
• Ferguson-Forcade algorithm [A]
• FFT [A]
• Fibonacci number [D]
• finite Fourier transform [A]
• gamma function [D]
• GCD [A]
• greatest common divisor [A]
• highest common factor [A]
• Horner's rule [A]
• kth order Fibonacci numbers [D]
• LCM [D]
• least common multiple [D]
• linear congruential generator [A]
• mean [D]
• median [D]
• midrange [D]
• Miller-Rabin [A]
• mode [D]
• pth order Fibonacci numbers [D]
• random number generator [A]
• repeated squaring [A]
• RNG [A]
• sieve of Eratosthenes [A]
• square root [A]
• Stirling's approximation [D]
• Stirling's formula [D]

Parallel

• Batcher sort [A]
• bitonic sort [A]
• concurrent read, concurrent write [D]
• concurrent read, exclusive write [D]
• CRCW [D]
• CREW [D]
• ERCW [D]
• EREW [D]
• exclusive read, concurrent write [D]
• exclusive read, exclusive write [D]
• graph concentration [D]
• list contraction [D]
• multiprefix [A]
• multiprocessor model [D]
• parallel computation thesis [D]
• parallel prefix computation [A]
• parallel random-access machine [D]
• path system problem [P]
• pipelined divide and conquer [T]
• pointer jumping [D]
• PRAM [D]
• prefix sums [A]
• random sampling [T]
• recursive doubling [D]
• scan [A]
• shortcutting [D]
• single program multiple data [D]
• SPMD [D]
• symmetry breaking [T]
• tournament [A]
• tree contraction [D]
• work [D]
• work-depth model [D]
• work-efficient [D]
• work-preserving [D]

Quantum Computation

• Deutsch-Jozsa algorithm [A]
• Grover's algorithm [A]
• quantum computation [D]
• Shor's algorithm [A]

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]
• 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]
• 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]
• rank [D]
• Ratcliff/Obershelp pattern recognition [A]
• rehashing [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 heuristic [T]
• 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

• adaptive heap sort [A]
• adaptive sort [D]
• address-calculation sort [A]
• American flag sort [A]
• balanced k-way merge sort [A]
• balanced merge sort [A]
• balanced multiway merge [A]
• balanced quicksort [A]
• balanced two-way merge sort [A]
• bidirectional bubble sort [A]
• binary insertion sort [A]
• bingo sort [A]
• bin sort [A]
• blind sort [A]
• bogosort [A]
• bozo sort [A]
• brick sort [A]
• bubble sort [A]
• bucket sort [A]
• cocktail shaker sort [A]
• comb sort [A]
• comparison sort [D]
• counting sort [A]
• derangement [A]
• diminishing increment sort [A]
• distribution sort [A]
• distributive partitioning sort [A]
• dominance tree sort [A]
• double-direction bubble sort [A]
• Dutch national flag [P]
• easy split, hard merge [T]
• exchange sort [A]
• external merge [A]
• external quicksort [A]
• external radix sort [A]
• external sort [D]
• flash sort [A]
• gnome sort [A]
• hard split, easy merge [T]
• heapsort [A]
• histogram sort [A]
• ideal merge [A]
• in-place sort [A]
• insertion sort [A]
• internal sort [D]
• interpolation sort [A]
• introsort [A]
• introspective sort [A]
• JSort [A]
• J sort [A]
• k-way merge [D]
• k-way merge sort [A]
• linear insertion sort [A]
• linear probing sort [A]
• lucky sort [A]
• merge [D]
• merge sort [A]
• multiway merge [D]
• nonbalanced merge [A]
• nonbalanced merge sort [A]
• optimal merge [A]
• optimal polyphase merge [A]
• optimal polyphase merge sort [A]
• oscillating merge sort [A]
• pigeonhole sort [A]
• pile [S]
• polyphase merge [A]
• polyphase merge sort [A]
• postman's sort [A]
• p-way merge sort [A]
• qm sort [A]
• q sort [A]
• quicksort [A]
• radix sort [A]
• range sort [A]
• rapid sort [A]
• restricted universe sort [D]
• selection sort [A]
• shaker sort [A]
• Shell sort [A]
• shuffle sort [A]
• simple merge [A]
• sinking sort [A]
• smoothsort [A]
• sort [A]
• sort in place [A]
• stooge sort [A]
• strand sort [A]
• three-way merge sort [A]
• top-down radix sort [A]
• topological sort [D]
• tournament sort [A]
• treesort (1) [A]
• treesort (2) [A]
• two-way merge sort [A]
• UnShuffle sort [A]
• unsorted list [D]
• weak-heap sort [A]

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]
• worst case [D]
• worst-case cost [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]
• k-ary heap [S]
• k-ary tree [S]
• k-way tree [S]
• leaf [D]
• leftist tree [S]
• left rotation [A]
• 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]
• van Emde-Boas priority queue [S]
• weight-balanced tree [S]
• zipper [S]

Verification and Formal Methods

• CTL [D]
• formal methods [D]
• formal verification [D]

Entries with No Area

• cascade merge sort
• division method
• double left rotation
• double right rotation
• expandable hashing
• interval tree
• Karmarkar's algorithm
• k-clustering
• minimum path cover
• multikey Quicksort
• OBDD
• oblivious algorithm
• ordered binary decision diagram
• orthogonal lists
• 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/termsArea.html