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