Algorithms and Data Structures Glossary (Starting with "M")
By
www.nist.gov,
Gaithersburg, Maryland, U.S.A.
paul
. black [at] nist . gov
http://www.nist.gov/dads
Become a member of TranslationDirectory.com at just
$12 per month (paid per year)
Advertisements:
Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously
M
 MalhotraKumarMaheshwari blocking flow
 Manhattan distance
 manyone reduction
 map: see dictionary
 Markov chain
 Marlena
 marriage problem: see assignment problem
 Master theorem
 matched edge
 matched vertex
 matching
 matrix
 matrixchain multiplication problem
 maxheap property
 maximal independent set
 maximally connected component
 Maximal Shift
 maximum bipartite matching: see bipartite matching
 maximumflow problem
 MAXSNP
 MBB: see minimum bounding box
 Mealy machine
 mean
 median
 meld
 memoization
 merge
 merge sort
 metaheuristic
 metaphone
 midrange
 MillerRabin
 minheap property
 minimal perfect hashing
 minimax
 minimum bounding box
 minimum cut
 minimum path cover
 minimum spanning tree
 minimum vertex cut
 Minkowski distance: see L_{m} distance
 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
 MorrisPratt algorithm
 move: see transition
 movetofront heuristic
 movetoroot heuristic
 MST: see minimum spanning tree
 multicommodity flow
 multigraph
 multikey Quicksort
 multilayer grid file
 multiplication method
 multiprefix
 multiprocessor model
 multiset: see bag
 multi suffix tree
 multiway decision
 multiway merge
 multiway search tree
 multiway tree
 Munkres' assignment algorithm
MalhotraKumarMaheshwari blocking flow
(algorithm)
Definition:
Given a flow function and its corresponding residual graph (a maximumflow problem), select a vertex with the least throughput and greedily push the maximum flow from it to the sink. This is repeated until all vertices are deleted.
Note:
From Algorithms and Theory of Computation Handbook, page 713, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
Manhattan distance
(definition)
Definition:
The distance between two points measured along axes at right angles. In a plane with p_{1} at (x_{1}, y_{1}) and p_{2} at (x_{2}, y_{2}), it is x_{1}  x_{2} + y_{1}  y_{2}.
Generalization (I am a kind of ...)
L_{m} distance.
Note:
This is easily generalized to higher dimensions. Manhattan distance is often used in integrated circuits where wires only run parallel to the X or Y axis. See links at L_{m} distance for more detail. Also known as rectilinear distance, Minkowski's L_{1} distance, taxi cab metric, or city block distance. Hamming distance can be seen as Manhattan distance between bit vectors.
Author: PEB
More information
Wikipedia entry for Taxicab geometry. Comparison between Manhattan and Euclidean distance. Weisstein's World of Math calls it taxicab metric.
manyone reduction
(definition)
Definition:
A reduction that maps an instance of one problem into an equivalent instance of another problem.
Note:
From Algorithms and Theory of Computation Handbook, page 2419, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
Markov chain
(data structure)
Definition:
A finite state machine with probabilities for each transition, that is, a probability that the next state is s_{j} given that the current state is s_{i}.
Note:
Equivalently, a weighted, directed graph in which the weights correspond to the probability of that transition. In other words, the weights are nonnegative and the total weight of outgoing edges is positive. If the weights are normalized, the total weight, including selfloops, is 1. After [Leda98].
Author: PEB
More information
Named after Andrei Andreyevich Markov (1856  1922), who studied poetry and other texts as stochastic sequences of characters.
Marlena
(definition)
Definition:
A wonderful wife. Every man should have such an incredible wife. We got married in 1976, too, and life's only gotten better.
Note:
After Harry Newton "Newton's Telecom Dictionary" (Miller Freeman, New York, 1999).
Author: PEB
Master theorem
(definition)
Definition:
A theorem giving a solution in asymptotic terms for recurrence relations of the form T(n) = aT(n/b) + f(n) where a ≥ 1 and b > 1 are constants and n/b means either n/b or n/b.
Author: SKS
matched edge
(definition)
Definition:
An edge which is in a matching.
Author: PEB
matched vertex
(definition)
Definition:
A vertex on an matched edge in a matching, or, one which has been matched.
Author: PEB
matching
(definition)
Definition:
(1) A subgraph in which every vertex has a degree at most one. In other words, no two edges share a common vertex. (2) The problem of finding such a subgraph.
Note:
From Algorithms and Theory of Computation Handbook, page 721, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
matrix
(data structure)
Definition:
A twodimensional array. By convention, the first index is the row, and the second index is the column.
Specialization (... is a kind of me.)
square matrix, rectangular matrix, sparse matrix, lower triangular matrix, upper triangular matrix, ragged matrix, uniform matrix.
Note:
Often implemented as an array.
Author: PEB
matrixchain multiplication problem
(classic problem)
Definition:
Given a sequence of matrices such that any matrix may be multiplied by the previous matrix, find the best association such that the result is obtained with the minimum number of arithmetic operations. One may use dynamic programming to find the best association.
Author: SKS
More information
Dan Hirschberg's example of using dynamic programming for matrix multiplication, including pseudocode.
maxheap property
(definition)
Definition:
Each node in a tree has a key which is less than or equal to the key of its parent.
Note:
The root node has the largest, or maximum, key. After LK.
Author: PEB
maximal independent set
(classic problem)
Definition:
A set of vertices in a graph such that for any pair of vertices, there is no edge between them and such that no more vertices can be added and it still be an independent set.
Note:
It is NPcomplete to decide if there is maximal independent set of size k in a graph.
Author: SKS
maximally connected component
(definition)
Definition:
A connected subgraph of a graph to which no vertex can be added and it still be connected.
Formal Definition: Given a graph G=(V, E), a subgraph S=(V', E') is a maximally connected component if
 S is connected, and
 for all vertices u such that u∈ V and u∉ V' there is no vertex v∈ V' for which (u, v)∈ E.
Note:
Informally, (one of) the biggest connected subgraph(s) of a graph. Also know as "connected component", with the "maximal" property understood.
Author: AL
More information
(C++, C, Pascal, Mathematica, and Fortran)
maximumflow problem
(classic problem)
Definition:
The problem of finding the maximum flow between any two vertices of a directed graph.
Also known as network flow problem.
Note:
After [CLR90, page 580].
Author: PEB
MAXSNP
(definition)
Definition:
The class of problems having constantfactor approximation algorithms, but no approximation schemes unless P=NP.
Note:
From Algorithms and Theory of Computation Handbook, page 3417, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
Mealy machine
(definition)
Definition:
A finite state machine which produces an output for each transition.
Author: PEB
More information
George H. Mealy, A method for synthesizing sequential circuits, Bell System Technical Journal, 34(5):10451079, 1955.
mean
(definition)
Definition:
The (arithmetic) mean of some values is the sum of all values divided by the number of values.
Note:
The mean of 1, 1, 3, 50, and 60 is 23. (1 + 1 + 3 + 50 + 60) / 5 = 23.
Author: PEB
median
(definition)
Definition:
The value which has an equal number of values greater and less than it. For an even number of values, it is the mean of the two middle values.
Note:
The median is the "middle" value. The median of 1, 1, 3, 50, and 60 is 3 since two elements (1 and 1) are less than it and two elements (50 and 60) are greater. The median of 1, 1, 2, 3, 3, and 4 is 2.5, the mean of 2 and 3.
Author: PEB
meld
(definition)
Definition:
Joining several data structures with particular properties into one large data structure having those properties. For instance, some priority queue implementations support the operation of joining two priority queues into a larger one.
Aggregate parent (I am a part of or used in ...)
pagoda.
Author: PEB
memoization
(algorithmic technique)
Definition:
Save (memoize) a computed answer for possible later reuse, rather than recomputing the answer.
Note:
The term comes from "memo": "A short note written as a reminder." [The American Heritage Dictionary of the English Language, © 1970, American Heritage Publishing] A naive program to compute Fibonacci numbers is
fib(n) { if n is 1 or 2, return 1; return fib(n1) + fib(n2); } Because fib() is recomputed over and over for the same argument, run time for the above is Ω(1.6^{n}). If instead we memoize (save) the value of fib(n) the first time we compute it, the run time is Θ(n).
allocate array for memo; set all elements of memo to zero; fib(n) { if n is 1 or 2, return 1; if memo[n] is not zero, return memo[n]; memo[n] = fib(n1) + fib(n2); return memo[n]; } Of course, computing Fibonacci numbers can be easily done in logarithmic time (see Fibonacci numbers), but this illustrates memoization.
Author: PEB
merge
(definition)
Definition:
Combine two or more sorted sequences of data into a single sorted sequence.
Formal Definition: For simplicity, let input be two sequences, A={a_{1}, ..., a_{n}} and B={b_{1}, ..., b_{m}}, each sorted according to some total order, ≤. The output is a single sequence, merge(A,B), which is a sorted permutation of {a_{1}, ..., a_{n}, b_{1}, ..., b_{m}}.
merge(A, B) is  A, if B is empty,
 B, if A is empty,
 {a_{1}}.merge({a_{2}, ..., a_{n}}, B) if a_{1} <= b_{1}, and
 {b_{1}}.merge(A, {b_{2}, ..., b_{m}}) otherwise.
The symbol "." stands for concatenation, for example, {a_{1}, ..., a_{n}}.{b_{1}, ..., b_{m}} = {a_{1}, ..., a_{n}, b_{1}, ..., b_{m}}. Formalization by Mustafa Ege <ege@eti.cc.hun.edu.tr>.
Specialization (... is a kind of me.)
multiway merge, kway merge, simple merge, ideal merge, optimal merge.
Author: ASK
merge sort
(algorithm)
Definition:
A sort algorithm that splits the items to be sorted into two groups, recursively sorts each group, and merges them into a final, sorted sequence. Run time is Θ(n log n).
Generalization (I am a kind of ...)
sort.
Specialization (... is a kind of me.)
kway merge sort, balanced kway merge sort, polyphase merge sort.
Aggregate child (... is a part of or used in me.)
divide and conquer.
Note:
There seem to be some references to lineartime inplace merging; look for papers by Geffert, Katajainen & Pasanen.
Author: PEB
More information
animation (Java). Comparison of quicksort, heapsort, and merge sort on modern processors.
metaheuristic
(algorithmic technique)
Definition:
(1) A highlevel algorithmic framework or approach that can be specialized to solve optimization problems. (2) A highlevel strategy that guides other heuristics in a search for feasible solutions.
Author: PEB
metaphone
(algorithm)
Definition:
An algorithm to code English words phonetically by reducing them to 16 consonant sounds. A better variant is double metaphone.
Generalization (I am a kind of ...)
phonetic coding algorithm.
Author: PEB
More information
Andrew Binstock and John Rex. Metaphone: A Modern Soundex. Practical Algorithms For Programmers. AddisonWesley, 1995 pages 160169. Gary Parker. A Better Phonetic Search. C Gazette, Vol. 5, No. 4 (June/July), 1990. Lawrence Philips. Hanging on the Metaphone. Computer Language, Vol. 7, No. 12 (December), 1990.
midrange
(definition)
Definition:
The sum of the minimum and maximum values, divided by two.
Note:
The midrange of 1, 1, 3, 50, and 60 is 30.5. (1 + 60) / 2 = 30.5.
Author: PEB
MillerRabin
(algorithm)
Definition:
A heuristic test for prime numbers. It repeatedly checks if the number being tested, n, is pseudoprime to a randomly chosen base, a, and there are only trivial square roots of 1, modulo n. In other words, n is surely composite if a^{n1} ≠ 1 (mod n), where 0 < a < n. Some composites may be incorrectly judged to be prime.
Note:
For k repetitions, the chance of incorrectly judging an odd integer greater than 2 to be prime is 2^{k}. For randomly chosen large integers, a small number of repetitions, say 3, is enough. After [CLR90, pages 838844].
Author: PEB
minheap property
(definition)
Definition:
Each node in a tree has a key which is greater than or equal to the key of its parent.
Note:
After LK.
Author: PEB
minimal perfect hashing
(algorithm)
Definition:
A perfect hashing function that maps each different key to a distinct integer and has the same number of possible integers as keys.
Formal Definition: A function f is a minimal perfect hash function for a set of keys K iff ∀ j, k ∈ K f(j) = f(k) → j = k and the range of f(k) is 1... K.
Generalization (I am a kind of ...)
perfect hashing, hash function.
Specialization (... is a kind of me.)
orderpreserving minimal perfect hashing.
Note:
After BJ.
Author: PEB
More information
Edward A. Fox, Lenwood S. Heath, Qi Fan Chen and Amjad M. Daoud, Practical minimal perfect hash functions for large databases, CACM, 35(1):105121, January 1992.
GPERF: A Perfect Hash Function Generator PDF document.
minimax
(algorithm)
Definition:
Generate all nodes in a game tree. Score each leaf node with its utility value. Score each minimizing node with the smallest of its children's scores, and maximizing node with the largest of its children's scores.
Generalization (I am a kind of ...)
depthfirst search.
Aggregate child (... is a part of or used in me.)
multiway tree, recursion.
Note:
For most games, minimizing nodes alternate levels with maximizing nodes. This corresponds to two opponents taking turns. Conceptually all nodes are generated first, but minimax is normally implemented as a depthfirst search. Time complexity is O(b^{d}) where b is the average branching factor and d is the depth of the move tree. Complete minimax search is impractical for most games.
Author: RS
minimum bounding box
(definition)
Definition:
The smallest rectangle completely enclosing a set of points.
Also known as MBB.
Author: PEB
minimum cut
(definition)
Definition:
The smallest set of edges in an undirected graph which separate two distinct vertices. That is, every path between them includes some member of the set.
Author: PEB
minimum spanning tree
(definition)
Definition:
A minimumweight tree in a weighted graph which contains all of the graph's vertices.
Also known as MST, shortest spanning tree, SST.
Generalization (I am a kind of ...)
spanning tree.
Aggregate parent (I am a part of or used in ...)
Christofides algorithm (1).
Note:
A minimum spanning tree can be used to quickly find a nearoptimal solution to the traveling salesman problem.
The term "shortest spanning tree" may be more common in the field of operations research. A Steiner tree is allowed additional connection points to reduce the total length even more.
Author: JLG
More information
Eppstein's lecture outlining and contrasting MST algorithms.
minimum vertex cut
(definition)
Definition:
The smallest set of vertices in an undirected graph which separate two distinct vertices. That is, every path between them passes through some member of the cut.
Author: PEB
mixed integer linear program
(definition)
Definition:
A linear program with additional constraints that some of the variables must take on integer values. Solving such problems is NPhard.
Note:
From Algorithms and Theory of Computation Handbook, pages 3239 and 3417, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
mode
(definition)
Definition:
The value which occurs most often. If no value is repeated, there is no mode. If more than one value occurs with the same greatest frequency, each value is a mode.
Note:
The mode of 1, 1, 3, 50, and 60 is 1 since it occurs twice and all the other values occur once. The set {1, 1, 2, 3, 3, 4} has two modes, 1 and 3, and is called bimodal. If there are more than two modes, it is multimodal.
Author: PEB
model checking
(algorithm)
Definition:
Efficiently deciding whether a temporal logic formula is satisfied in a finite state machine model.
Note:
Model checking is increasingly used in the formal verification of hardware and software. The decision process often uses some form of binary decision diagram (BDD).
Author: SKS
model of computation
(definition)
Definition:
A formal, abstract definition of a computer. Using a model one can more easily analyze the intrinsic execution time or memory space of an algorithm while ignoring many implementation issues. There are many models of computation which differ in computing power (that is, some models can perform computations impossible for other models) and the cost of various operations.
Specialization (... is a kind of me.)
Turing machine, random access machine, primitive recursive, cellular automaton, finite state machine, cell probe model, pointer machine, alternation, alternating Turing machine, nondeterministic Turing machine, oracle Turing machine, probabilistic Turing machine, universal Turing machine, quantum computation, parallel models: multiprocessor model, workdepth model, parallel randomaccess machine, shared memory.
Author: PEB
moderately exponential
(definition)
Definition:
The measure of computation, m(n) (usually execution time or memory space), is more than any polynomial n^{k}, but less than any exponential c^{n} where c > 1. Formally, m(n) is of moderately exponential growth if ∀ k > 0 m(n)=Ω(n^{k}) and ∀ ε > 0 m(n)=o((1+ε)^{n}).
Author: PEB
MODIFIND
(algorithm)
Definition:
An algorithm to select the k^{th} smallest element of an array and partition the array around it. It partitions around the value of the k^{th} element until one boundary passes element k. If either boundary does not pass element k, that boundary is moved and it partitions again.
Note:
This does fewer swaps than Find.
Author: PEB
More information
Vladimir Zabrodsky, MODIFIND, Elektronika, No. 6, pages 3334, 1992
monotone priority queue
(data structure)
Definition:
A priority queue in which a key being inserted is never higher in priority than a previously deleted node.
Note:
The keys deleted from a monotone priority queue form a monotonically increasing or monotonically decreasing sequence  hence the name. After LK.
Author: PEB
monotonically decreasing
(definition)
Definition:
A function from a partially ordered domain to a partially ordered range such that x ≤ y implies f(x) ≥ f(y).
Note:
After [CLR90, page 32].
Author: PEB
monotonically increasing
(definition)
Definition:
A function from a partially ordered domain to a partially ordered range such that x ≤ y implies f(x) ≤ f(y).
Note:
After [CLR90, page 32].
Author: PEB
Monte Carlo algorithm
(algorithmic technique)
Definition:
A randomized algorithm that may produce incorrect results, but with bounded error probability.
Generalization (I am a kind of ...)
heuristic.
Note:
From Algorithms and Theory of Computation Handbook, 1521, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC. A Monte Carlo algorithm gives more precise results the longer you run it. A Las Vegas algorithm gives exactly the right answer, but the run time is indeterminate.
Author: CRCA
More information
An excellent tutorial introduction with history.
Nicholas Metropolis and Stanislaw Ulam, The Monte Carlo method, Journal of the American Statistical Association, 44(247):335341, 1949.
Moore machine
(definition)
Definition:
A finite state machine that produces an output for each state.
Note:
Named for the originator, Edward F. Moore.
Author: PEB
movetofront heuristic
(algorithm)
Definition:
A heuristic that moves the target of a search to the head of a list so it is found faster next time.
Note:
This technique speeds up linear search performance only if the target item is likely to be searched for again soon.
Author: PEB
movetoroot heuristic
(algorithm)
Definition:
A heuristic that moves the target of a search to the root of the search tree so it is found faster next time.
Aggregate parent (I am a part of or used in ...)
splay tree.
Note:
This technique speeds up search performance only if the target item is likely to be searched for again soon.
Author: PEB
multicommodity flow
(definition)
Definition:
A maximumflow problem involving multiple commodities, in which each commodity has an associated demand and sourcesink pairs.
Note:
From Algorithms and Theory of Computation Handbook, page 721, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
multigraph
(data structure)
Definition:
A graph whose edges are unordered pairs of vertices, and the same pair of vertices can be connected by multiple edges.
Formal Definition: Same as graph, but E is a bag of edges, not a set.
Generalization (I am a kind of ...)
graph.
Aggregate parent (I am a part of or used in ...)
Christofides algorithm.
Note:
A definition of "pseudograph" is a multigraph that may have selfloops.
Author: PEB
multikey Quicksort
Definition:
Pick an element from the array (the pivot). Consider the first character (key) of the string (multikey). Partition the remaining elements into three sets: those whose corresponding character is less than, equal to, and greater than the pivot's character. Recursively sort the "less than" and "greater than" partitions on the same character. Recursively sort the "equal to" partition by the next character (key).
Also known as threeway radix quicksort.
Generalization (I am a kind of ...)
quicksort.
Aggregate child (... is a part of or used in me.)
Dutch national flag, key.
Note:
Especially good for strings. Fast Algorithms ... gives a good 3way partition algorithm.
Author: PEB
More information
Jon L. Bentley and Robert Sedgewick, Fast Algorithms for Sorting and Searching Strings, Proc. 8th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages 360369, January 1997.
multilayer grid file
(data structure)
Definition:
A spatial access method which is two or more simultaneous grid files. Objects reside in the first grid file where it doesn't have to be split across hyperplanes.
Note:
After [GG98].
Author: PEB
multiplication method
(algorithm)
Definition:
A hash function that uses the first p bits of the key times an irrational number.
Formal Definition: h(k) = m(k A (mod 1)), where m is usually an integer 2^{p} and A is an irrational number (or an approximation thereto) 0 < A < 1. The modulo 1 operation removes the integer part of k × A.
Author: PEB
multiprefix
(algorithm)
Definition:
A generalization of scan in which the partial sums are grouped by keys.
Note:
From Algorithms and Theory of Computation Handbook, page 4740, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
multiprocessor model
(definition)
Definition:
A model of parallel computation based on a set of communicating sequential processors.
Note:
From Algorithms and Theory of Computation Handbook, page 4740, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
multi suffix tree
(data structure)
Definition:
A suffix tree extended to multiple strings by concatenating the strings.
Generalization (I am a kind of ...)
suffix tree.
Author: SE
multiway decision
(definition)
Definition:
A decision which has more than two results. For instance, testing if a < b yields two results, but some languages allow a test to return a < b, a=b, or a > b in one operation.
Note:
The standard library function strcmp() in C returns 1, 0, or 1 depending on whether one is less than, equal to, or greater than the other.
Author: PR
multiway merge
(definition)
Definition:
Combine more than two sorted data streams into a single sorted stream.
Generalization (I am a kind of ...)
merge.
Specialization (... is a kind of me.)
kway merge.
Author: ASK
multiway tree
(data structure)
Definition:
A tree with any number of children for each node.
Note:
A typical implementation is to have a list of child nodes at each node, rather than a fixed number of children. A more elaborate implementation is to have a fixed number of children, to handle most nodes efficiently, and a linked list for those rare nodes that have more children. See also the binary tree representation of trees.
Author: PEB
Munkres' assignment algorithm
(algorithm)
Definition:
Solve the assignment problem in polynomial time by marking and unmarking entries and covering and uncovering rows and columns.
Also known as Hungarian algorithm.
Author: PEB
More information
James Munkres, 1957.
Published  April 2009
Find free glossaries at TranslationDirectory.com
Find free dictionaries at TranslationDirectory.com
Subscribe to free TranslationDirectory.com newsletter
Need more translation jobs from translation agencies? Click here!
Translation agencies are welcome to register here  Free!
Freelance translators are welcome to register here  Free!
Submit your glossary or dictionary for publishing at TranslationDirectory.com
