﻿ Algorithms and Data Structures Glossary (Starting with "M")    Home Free Glossaries Free Dictionaries Post Your Translation Job! Free Articles Jobs for Translators  #### Algorithms and Data Structures Glossary(Starting with "M")

By www.nist.gov,
Gaithersburg, Maryland, U.S.A.

paul . black [at] nist . gov

Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously

 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

### M

Malhotra-Kumar-Maheshwari blocking flow
Manhattan distance
many-one reduction
map: see dictionary
Markov chain
Marlena
marriage problem: see assignment problem
Master theorem
matched edge
matched vertex
matching
matrix
matrix-chain multiplication problem
max-heap property
maximal independent set
maximally connected component
Maximal Shift
maximum bipartite matching: see bipartite matching
maximum-flow problem
MAX-SNP
MBB: see minimum bounding box
Mealy machine
mean
median
meld
memoization
merge
merge sort
metaheuristic
metaphone
midrange
Miller-Rabin
min-heap property
minimal perfect hashing
minimax
minimum bounding box
minimum cut
minimum path cover
minimum spanning tree
minimum vertex cut
Minkowski distance: see Lm 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
Morris-Pratt algorithm
move: see transition
move-to-front heuristic
move-to-root heuristic
MST: see minimum spanning tree
multi-commodity flow
multigraph
multikey Quicksort
multilayer grid file
multiplication method
multiprefix
multiprocessor model
multi-set: see bag
multi suffix tree
multiway decision
multiway merge
multiway search tree
multiway tree
Munkres' assignment algorithm

#### Malhotra-Kumar-Maheshwari blocking flow

(algorithm)

Definition: Given a flow function and its corresponding residual graph (a maximum-flow 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 7-13, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### Manhattan distance

(definition)

Definition: The distance between two points measured along axes at right angles. In a plane with p1 at (x1, y1) and p2 at (x2, y2), it is |x1 - x2| + |y1 - y2|.

Generalization (I am a kind of ...)
Lm 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 Lm distance for more detail.

Also known as rectilinear distance, Minkowski's L1 distance, taxi cab metric, or city block distance.

Hamming distance can be seen as Manhattan distance between bit vectors.

Author: PEB

Wikipedia entry for Taxicab geometry. Comparison between Manhattan and Euclidean distance. Weisstein's World of Math calls it taxicab metric.

#### many-one 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 24-19, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### Markov chain

(data structure)

Definition: A finite state machine with probabilities for each transition, that is, a probability that the next state is sj given that the current state is si.

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 self-loops, is 1. After [Leda98].

Author: PEB

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 7-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### matrix

(data structure)

Definition: A two-dimensional 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

#### matrix-chain 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

Dan Hirschberg's example of using dynamic programming for matrix multiplication, including pseudocode.

#### max-heap 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 NP-complete 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

(C++, C, Pascal, Mathematica, and Fortran)

#### maximum-flow 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

#### MAX-SNP

(definition)

Definition: The class of problems having constant-factor approximation algorithms, but no approximation schemes unless P=NP.

Note: From Algorithms and Theory of Computation Handbook, page 34-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### Mealy machine

(definition)

Definition: A finite state machine which produces an output for each transition.

Author: PEB

George H. Mealy, A method for synthesizing sequential circuits, Bell System Technical Journal, 34(5):1045-1079, 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(n-1) + fib(n-2); } `
Because fib() is recomputed over and over for the same argument, run time for the above is Ω(1.6n). 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(n-1) + fib(n-2);    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={a1, ..., an} and B={b1, ..., bm}, each sorted according to some total order, ≤. The output is a single sequence, merge(A,B), which is a sorted permutation of {a1, ..., an, b1, ..., bm}.

merge(A, B) is

1. A, if B is empty,
2. B, if A is empty,
3. {a1}.merge({a2, ..., an}, B) if a1 <= b1, and
4. {b1}.merge(A, {b2, ..., bm}) otherwise.
The symbol "." stands for concatenation, for example, {a1, ..., an}.{b1, ..., bm} = {a1, ..., an, b1, ..., bm}.

Formalization by Mustafa Ege <ege@eti.cc.hun.edu.tr>.

Specialization (... is a kind of me.)
multiway merge, k-way merge, simple merge, ideal merge, optimal merge.

#### 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.)
k-way merge sort, balanced k-way 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 linear-time in-place merging; look for papers by Geffert, Katajainen & Pasanen.

Author: PEB

animation (Java). Comparison of quicksort, heapsort, and merge sort on modern processors.

#### metaheuristic

(algorithmic technique)

Definition: (1) A high-level algorithmic framework or approach that can be specialized to solve optimization problems. (2) A high-level 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

Andrew Binstock and John Rex. Metaphone: A Modern Soundex. Practical Algorithms For Programmers. Addison-Wesley, 1995 pages 160-169.

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

#### Miller-Rabin

(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 an-1 ≠ 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 838-844].

Author: PEB

#### min-heap 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.)
order-preserving minimal perfect hashing.

Note: After BJ.

Author: PEB

Edward A. Fox, Lenwood S. Heath, Qi Fan Chen and Amjad M. Daoud, Practical minimal perfect hash functions for large databases, CACM, 35(1):105-121, 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 ...)
depth-first 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 depth-first search. Time complexity is O(bd) 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 minimum-weight 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 near-optimal 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

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 NP-hard.

Note: From Algorithms and Theory of Computation Handbook, pages 32-39 and 34-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### 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, work-depth model, parallel random-access 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 nk, but less than any exponential cn where c > 1. Formally, m(n) is of moderately exponential growth if ∀ k > 0 m(n)=Ω(nk) and ∀ ε > 0 m(n)=o((1+ε)n).

Author: PEB

#### MODIFIND

(algorithm)

Definition: An algorithm to select the kth smallest element of an array and partition the array around it. It partitions around the value of the kth 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

Vladimir Zabrodsky, MODIFIND, Elektronika, No. 6, pages 33-34, 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, 15-21, 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: CRC-A

An excellent tutorial introduction with history.

Nicholas Metropolis and Stanislaw Ulam, The Monte Carlo method, Journal of the American Statistical Association, 44(247):335-341, 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

#### move-to-front 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

#### move-to-root 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

#### multi-commodity flow

(definition)

Definition: A maximum-flow problem involving multiple commodities, in which each commodity has an associated demand and source-sink pairs.

Note: From Algorithms and Theory of Computation Handbook, page 7-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### 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 self-loops.

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 three-way 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 3-way partition algorithm.

Author: PEB

Jon L. Bentley and Robert Sedgewick, Fast Algorithms for Sorting and Searching Strings, Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 360-369, 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 2p 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 47-40, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### 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 47-40, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### 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.)
k-way merge.

#### 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

James Munkres, 1957.

 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

Published - April 2009

Find free glossaries at TranslationDirectory.com

Find free dictionaries at TranslationDirectory.com

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

 Use More Glossaries Use Free Dictionaries Use Free Translators Submit Your Glossary Read Translation Articles Register Translation Agency Submit Your Resume Obtain Translation Jobs Subscribe to Free Newsletter Buy Database of Translators Obtain Blacklisted Agencies Vote in Polls for Translators Read News for Translators Advertise Here Read our FAQ Read Testimonials Use Site Map       