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
endpointof an interval, 311
of a line segment, 934
ENQUEUE, 203
entering a vertex, 1080
entering variable, 793
entropy function, 1098
∈-dense graph, 641 pr.equalityof functions, 1078
linear, 772
of sets, 1070
equality constraint, 606 ex., 778
and inequality constraints, 780
tight, 791
violation of, 791
equationand 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
exponentiationmodular, 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 keyfrom d-ary heaps, 143 pr.from max-heaps, 139
extracting the minimum keyfrom 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