main memory, 434
MAKE-BINOMIAL-HEAP, 461
MAKE-HEAP, 455
MAKE-SET, 498
disjoint-set-forest implementation of, 508
linked-list implementation of, 501
MAKE-TREE, 519 pr.
Manhattan distance, 194 pr., 962 ex.
Markov's inequality, 1111 ex.
master method for solving a recurrence, 73-76
master theorem, 73
matched vertex, 664
matching
maximum, 1051 pr.
weighted bipartite, 497
matric matroid, 393
adjacency, 529
conjugate transpose of, 759 ex.
Hermitian, 759 ex.
predecessor, 621
pseudoinverse of, 764
sorting the entries of, 721 ex.
symmetric positive-definite, 760-762
Toeplitz, 844 pr.
see also matrix inversion, matrix multiplication
matrix-chain multiplication, 331-339
MATRIX-CHAIN-MULTIPLY
MATRIX-CHAIN-ORDER, 336
matrix multiplication
for all-pairs shortest paths, 622-629
boolean, 759 ex.
and computing the determinant, 759 ex.
and LUP decomposition, 759 ex.
Pan's method for, 741 ex.
Strassen's algorithm for, 735-742
matroid, 393-399, 403 pr., 579
MAX-CNF satisfiability, 1043 ex.
MAX-CUT problem, 1043 ex.
MAX-FLOW-BY-SCALING, 694 pr.
max-flow min-cut theorem, 657
max-heap, 128
deletion from, 142 ex.
extracting the maximum key from, 139
insertion into, 140
maximum key of, 139
as a max-priority queue, 138-142
mergeable, see mergeable max-heap
MAX-HEAPIFY, 130
MAX-HEAP-INSERT, 140
building a heap with, 142 pr.
max-heap property, 128
maximal element of a partially ordered set, 1076
maximal layers, 962 pr.
maximal matching, 1026, 1051 pr.
maximal point, 962 pr.
maximal subset in a matroid, 394
maximization linear program, 773
and minimization linear programs, 779
maximum, 183
in binary search trees, 258
of a binomial distribution, 1117 ex.
in heaps, 139
in order-statistic trees, 310 ex.
in red-black trees, 276
maximum bipartite matching, 664-669, 680 ex.
Hopcroft-Karp algorithm for, 696 pr.
maximum degree in a Fibonacci heap, 479, 488 ex., 493-496
Edmonds-Karp algorithm for, 660-663
Ford-Fulkerson method for, 651-664
as a linear program, 786
and maximum bipartite matching, 664-669
with negative capacities, 695 pr.
push-relabel algorithms for, 669-692
relabel-to-front algorithm for, 681-692
scaling algorithm for, 694 pr.
updating, 694 pr.
maximum matching, 1051 pr.
max-priority queue, 138
MAX-3-CNF satisfiability, 1039-1040
MAYBE-MST-A, 578 pr.
MAYBE-MST-B, 578 pr.
MAYBE-MST-C, 578 pr.
mean, see expected value
mean weight of a cycle, 617 pr.
of sorted lists, 193 ex.
weighted, 194 pr.
median key of a B-tree node, 443
median-of-3 method, 162 pr.
member of a set (∈), 1070
MEMOIZED-MATRIX-CHAIN, 348
memory, 434
memory hierarchy, 22
merge
of k sorted lists, 142 ex.
lower bounds for, 180 pr.
of two sorted arrays, 28
using a comparison network, 716-718
MERGE, 29
and comparison sorts, 489 ex.
linked-list implementation of, 217 pr.
relaxed heaps, 497
running times of operations on, 456 fig.
2-3-4 heaps, 473 pr.
see also binomial heap, Fibonacci heap
mergeable max-heap, 217 n., 431 n., 455 n.
mergeable min-heap, 217 n., 431 n., 455
MERGE-LISTS, 1044
MERGER, 717
compared to insertion sort, 13 ex.
sorting-network implementation of, 719-721
use of insertion sort in, 37 pr.
MERGE-SORT, 32
recursion tree for, 349 ex.
odd-even, 721 pr.
MILLER-RABIN, 892
Miller-Rabin primality test, 890-896
MIN-GAP, 317 ex.
min-heap, 129
analyzed by potential method, 416 ex.
in Dijkstra's algorithm, 599
in Huffman's algorithm, 388
in Johnson's algorithm, 640
mergeable, see mergeable min-heap
as a min-priority queue, 141 ex.
in Prim's algorithm, 573
MIN-HEAPIFY, 132 ex.
MIN-HEAP-INSERT, 141 ex.
min-heap-ordered, 459
maintenance of, 132 ex.
vs. binary-search-tree property, 256 ex.
minimization linear program, 773
and maximization linear programs, 779
minimum, 183
in binary search trees, 258
in binomial heaps, 462
in B-trees, 447 ex.
in Fibonacci heaps, 481
off-line, 518 pr.
in order-statistic trees, 310 ex.
in red-black trees, 276
minimum-cost multicommodity flow, 790 ex.
minimum-cost spanning tree, see minimum spanning tree
minimum cut, 655
minimum degree of a B-tree, 439
minimum key in 2-3-4 heaps, 473 pr.
minimum mean-weight cycle, 617 pr.
minimum node of a Fibonacci heap, 478
minimum path cover, 692 pr.
minimum spanning tree, 561-579
in approximation algorithm for traveling-salesman problem, 1028
Bor uvka's algorithm for, 578
constructed using binomial heaps, 474 pr.
on dynamic graphs, 574 ex.
generic algorithm for, 562-567
Kruskal's algorithm for, 568-570
relation to matroids, 393, 395
second-best, 575 pr.
minimum-weight spanning tree, see minimum spanning tree
minimum-weight vertex cover, 1040-1043
minor of a matrix, 732
min-priority queue, 138, 141 ex.
in constructing Huffman codes, 387
in Dijkstra's algorithm, 598
mirroring, 833 n.
missing child, 1089
modular arithmetic, 51-52, 862-869
modular exponentiation, 879
MODULAR-EXPONENTIATION, 879
modular linear equations, 869-872
MODULAR-LINEAR-EQUATION-SOLVER, 871
Monge array, 88 pr.
monotone sequence, 144
monotonically decreasing, 51
monotonically increasing, 51
MST, 474 pr.
MST-KRUSKAL, 569
MST-PRIM, 572
MST-REDUCE, 576 pr.
minimum-cost, 790 ex.
multidimensional Fast Fourier Transform, 845 pr.
multigraph, 1083
converting to equivalent undirected graph, 530 ex.
of an element modulo n, 869-872
least common, 861 ex.
multiple assignment, 19
multiple sources and sinks, 647
multiplication
of complex numbers, 741 ex.
divide-and-conquer method for, 844 pr.
of a matrix chain, see matrix-chain multiplication
modulo n (·n), 863
of polynomials, 823
multiplication method, 231-232
multiplicative group modulo n, 864
multiplicative inverse, modulo n, 871
multiply instruction, 22
MULTIPOP, 406
MULTIPUSH, 409 ex.
multiset, 1070 n.
mutually exclusive events, 1100
mutually independent events, 1103