I

| < Day Day Up > |

# Index

### I

idempotency laws for sets, 1071
identity, 862
identity matrix, 727
if, in pseudocode, 19
image, 1078
implicit summation notation, 648
inadmissible edge, 681
incidence, 1080
incidence matrix
and difference constraints, 603
of a directed graph, 403 pr., 531 ex.
of an undirected graph, 403 pr.
inclusion and exclusion, 1074 ex.
INCREASE-KEY, 138
increasing a key in a max-heap, 139– 140
INCREMENT, 408
incremental design method, 27
for finding the convex hull, 948
in-degree, 1081
indentation in pseudocode, 19
independence
of events, 1103, 1106 ex.
of random variables, 1107
of subproblems in dynamic programming, 343– 344
independent family of subsets, 393
independent set, 1018 pr.
of tasks, 400
index of an element of , 877
indicator random variable, 94– 98
in analysis of expected height of a randomly built binary search tree, 265– 267
in analysis of inserting into a treap, 296 pr.
in analysis of streaks, 113– 114
in analysis of the birthday paradox, 108– 109
in approximation algorithm for MAX-3-CNF satisfiability, 1040
in bounding the right tail of the binomial distribution, 1122– 1123
in bucket sort analysis, 175– 177
in hashing analysis, 227– 228
in hiring-problem analysis, 97– 98
in quicksort analysis, 157– 158, 160 pr.
in randomized selection analysis, 187– 189, 189 ex.
in universal-hashing analysis, 233– 234
induced subgraph, 1082
inequality, linear, 772
inequality constraint, 778
and equality constraints, 780
infeasible linear program, 778
infeasible solution, 778
infinite sequence, 1078
infinite set, 1073
infinite sum, 1058
infinity, arithmetic with, 587
INITIALIZE-PREFLOW, 673
INITIALIZE-SIMPLEX, 796, 812
INITIALIZE-SINGLE-SOURCE, 585
injective function, 1079
inner product, 730
inorder tree walk, 254, 260 ex., 305
INORDER-TREE-WALK, 255
input
to an algorithm, 5
to a combinational circuit, 988
distribution of, 93, 99
to a logic gate, 987
size of, 23
input alphabet, 916
input sequence, 705
input wire, 705
INSERT, 138, 198, 416 ex., 455
insertion
into binary search trees, 261
into binomial heaps, 468
into B-trees, 443– 447
into chained hash tables, 226
into d-ary heaps, 143 pr.
into direct-address tables, 222
into dynamic tables, 418
into Fibonacci heaps, 480– 481
into heaps, 140
into interval trees, 313
into linked lists, 205– 206
into open-address hash tables, 237– 238
into order-statistic trees, 306– 307
into queues, 201
into red-black trees, 280– 287
into stacks, 200
into sweep-line statuses, 942
into 2-3-4 heaps, 473 pr.
into Young tableaus, 143 pr.
insertion sort, 11, 15– 19, 24– 25
in bucket sort, 174– 177
compared to merge sort, 13 ex.
compared to quicksort, 153 ex.
decision tree for, 166 fig.
in merge sort, 37 pr.
in quicksort, 159 ex.
sorting-network implementation of, 708 ex.
using binary search, 37 ex.
INSERTION-SORT, 17, 24
instance
of an abstract problem, 969, 972
of a problem, 5
instructions of the RAM model, 21
integer data type, 22
integer linear-programming problem, 777, 819 pr., 1017 ex.
integers (Z), 1070
integer-valued flow, 666
integral, to approximate summations, 1067
integrality theorem, 667
integration of series, 1060
interior of a polygon, 939 ex.
interior-point method, 776
intermediate vertex, 629
internal node, 1088
internal path length, 1091 ex.
interpolation by a cubic spline, 767 pr.
interpolation by a polynomial, 825, 830 ex.
at complex roots of unity, 836– 837
intersection
of chords, 308 ex.
determining, for a set of line segments, 940– 947
determining, for two line segments, 936– 938
of languages, 976 of sets (∩), 1071
interval, 311
fuzzy sorting of, 163 pr.
INTERVAL-DELETE, 312
interval-graph coloring problem, 379 ex.
INTERVAL-INSERT, 312
INTERVAL-SEARCH, 312, 314
INTERVAL-SEARCH-EXACTLY, 317 ex.
interval tree, 311– 317
interval trichotomy, 311
intractability, 966
invalid shift, 906
inverse
of a bijective function, 1079
in a group, 862
of a matrix, 730, 733 ex.
of a matrix from an LUP decomposition, 755– 756
multiplicative, modulo n, 871
inversion in a sequence, 39 pr., 99 ex.
inverter, 987
invertible matrix, 730
isolated vertex, 1081
isomorphic graphs, 1082
iterated function, 60 pr.
iterated logarithm function, 55– 56
ITERATIVE-FFT, 841
ITERATIVE-TREE-SEARCH, 257

| < Day Day Up > |