M

| < Day Day Up > |

# Index

### M

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.
marked node, 478, 490
Markov's inequality, 1111 ex.
master method for solving a recurrence, 73- 76
master theorem, 73
proof of, 76- 84
matched vertex, 664
matching
maximal, 1026, 1051 pr.
maximum, 1051 pr.
and maximum flow, 664- 669
of strings, 906- 932
weighted bipartite, 497
matric matroid, 393
matrix, 725- 734
adjacency, 529
conjugate transpose of, 759 ex.
Hermitian, 759 ex.
incidence, 403 pr., 531 ex.
predecessor, 621
pseudoinverse of, 764
sorting the entries of, 721 ex.
symmetric positive-definite, 760- 762
Toeplitz, 844 pr.
transpose of, 529, 726
see also matrix inversion, matrix multiplication
matrix-chain multiplication, 331- 339
MATRIX-CHAIN-MULTIPLY
MATRIX-CHAIN-ORDER, 336
matrix inversion, 755- 758
matrix multiplication
for all-pairs shortest paths, 622- 629
boolean, 759 ex.
and computing the determinant, 759 ex.
and LUP decomposition, 759 ex.
and matrix inversion, 756- 758
Pan's method for, 741 ex.
Strassen's algorithm for, 735- 742
MATRIX-MULTIPLY, 332, 625
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
building, 132- 135
deletion from, 142 ex.
extracting the maximum key from, 139
in heapsort, 135- 138
increasing a key in, 139- 140
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
maintenance of, 130- 132
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.
finding, 184- 185
in heaps, 139
in order-statistic trees, 310 ex.
in red-black trees, 276
MAXIMUM, 138- 139, 198
maximum bipartite matching, 664- 669, 680 ex.
Hopcroft-Karp algorithm for, 696 pr.
maximum degree in a Fibonacci heap, 479, 488 ex., 493- 496
maximum flow, 643- 698
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.
median, 183- 195
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
memoization, 347- 349
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
mergeable heap, 431, 455
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
merge sort, 11, 28- 36
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.
merging network, 716- 718
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.
building, 132- 135
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
min-heap property, 129, 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
finding, 184- 185
off-line, 518 pr.
in order-statistic trees, 310 ex.
in red-black trees, 276
MINIMUM, 138, 184, 198, 455
minimum-cost flow, 787- 788
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
Prim's algorithm for, 570- 573
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
in Prim's algorithm, 572- 573
mirroring, 833 n.
missing child, 1089
mod, 51, 851
modular arithmetic, 51- 52, 862- 869
modular exponentiation, 879
MODULAR-EXPONENTIATION, 879
modular linear equations, 869- 872
MODULAR-LINEAR-EQUATION-SOLVER, 871
modulo, 51, 851
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.
multicommodity flow, 788- 789
minimum-cost, 790 ex.
multidimensional Fast Fourier Transform, 845 pr.
multigraph, 1083
converting to equivalent undirected graph, 530 ex.
multiple, 729, 850
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 matrices, 729, 734 ex.
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

| < Day Day Up > |