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

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