Index

E

e, 53

E [] (expected value), 1108

early-first form, 399

early task, 399

edge, 1080

admissible, 681

back, 546

bridge, 558 pr.

capacity of, 644

classification in breadth-first search, 558 pr.

classification in depth-first search, 546-547

critical, 662

cross, 546

forward, 546

inadmissible, 681

light, 563

negative-weight, 582-583

residual, 652

safe, 562

saturated, 672

tree, 538, 540, 546

weight of, 529

edge connectivity, 664 ex.

edge set, 1080

edit distance, 364 pr.

Edmonds-Karp algorithm, 660-663

elementary event, 1100

element of a set (∈), 1070

ellipsoid algorithm, 776

elliptic-curve factorization method, 905

else, in pseudocode, 19

empty language (Ø), 976

empty set (Ø), 1070

empty set laws, 1071

empty stack, 201

empty string (∈), 907, 975

empty tree, 1089

encoding of problem instances, 973-975

endpoint

of an interval, 311

of a line segment, 934

ENQUEUE, 203

entering a vertex, 1080

entering variable, 793

entropy function, 1098

∈-dense graph, 641 pr.

equality

of functions, 1078

linear, 772

of sets, 1070

equality constraint, 606 ex., 778

and inequality constraints, 780

tight, 791

violation of, 791

equation

and asymptotic notation, 46-47

normal, 764

recurrence, see recurrence

equivalence, modular (≡), 52, 1077 ex.

equivalence class, 1075

modulo n ([a]_n), 851

equivalence relation, 1075-1076

and modular equivalence, 1077 ex.

equivalent linear programs, 779

escape problem, 692 pr.

essential term, 738

EUCLID, 858

Euclid's algorithm, 856-862, 902 pr.

euclidean distance, 957

euclidean norm, 730

Euler's phi function, 865

Euler's theorem, 877, 896 ex.

Euler tour, 559 pr., 966

and hamiltonian cycles, 966

∈-universal hash function, 236 ex.

evaluation of a polynomial, 39 pr., 824, 829 ex.

and its derivatives, 845 pr.

at multiple points, 846 pr.

event, 1100

event point, 942

event-point schedule, 942

EXACT-SUBSET-SUM, 1045

excess flow, 669

exchange property, 393

exclusion and inclusion, 1074 ex.

execute a subroutine, 23 n.

expansion of a dynamic table, 417-418

expectation, see expected value

expected running time, 26

expected value, 1108-1109

of a binomial distribution, 1114

of a geometric distribution, 1112

of an indicator random variable, 95

explored vertex, 542

exponential function, 52-53

exponential height, 265

exponential search tree, 182, 433

exponential series, 1060

exponentiation

modular, 879

exponentiation instruction, 22

EXTENDED-EUCLID, 860

EXTEND-SHORTEST-PATHS, 624

extension of a set, 394

exterior of a polygon, 939 ex.

external node, 1088

external path length, 1091 ex.

extracting the maximum key

from d-ary heaps, 143 pr.

from max-heaps, 139

extracting the minimum key

from binomial heaps, 468-469

from Fibonacci heaps, 482-488

from 2-3-4 heaps, 473 pr.

from Young tableaus, 143 pr.

EXTRACT-MAX, 138-139

EXTRACT-MIN, 138, 455