L

| < Day Day Up > |

# Index

### L

Lagrange's formula, 826
Lagrange's theorem, 866
Lam 's theorem, 859
language, 975
completeness of, 994 ex.
proving NP-completeness of, 995– 996
verification of, 980
last-in, first-out, 200
see also stack
late task, 399
layers
convex, 962 pr.
maximal, 962 pr.
LCA, 521 pr.
lcm (least common multiple), 861 ex.
LCS, see longest common subsequence
LCS-LENGTH, 353
leading submatrix, 760
leaf, 1088
least common ancestor, 521 pr.
least common multiple, 861 ex.
least-squares approximation, 762– 765
leaving a vertex, 1080
leaving variable, 793
LEFT, 128
left child, 1089
left-child, right-sibling representation, 214, 217 ex.
LEFT-ROTATE, 278, 316 ex.
left rotation, 277
left spine, 296 pr.
left subtree, 1089
Legendre symbol , 903 pr.
length
of a path, 1081
of a sequence, 1078
of a spine, 296 pr.
of a string, 907, 1095
level of a function, 510
lexicographically less than, 269 pr.
lexicographic sorting, 269 pr.
lg (binary logarithm), 53
lg* (iterated logarithm function), 55– 56
lgk (exponentiation of logarithms), 53
lg lg (composition of logarithms), 53
LIFO (last-in, first-out), 200
see also stack
light edge, 563
linear constraint, 772
linear dependence, 731
linear equality, 772
linear equations
solving modular, 869– 872
solving systems of, 742– 755
solving tridiagonal systems of, 767 pr.
linear function, 25, 772
linear independence, 731
linear inequality, 772
linear-inequality feasibility problem, 818 pr.
linearity of expectation, 1108
linearity of summations, 1059
linear order, 1077
linear probing, 239
linear programming, 770– 821
algorithms for, 776– 777
applications of, 776
duality in, 804– 811
finding an initial solution for, 811– 816
fundamental theorem of, 816
interior-point methods for, 776, 820
Karmarkar's algorithm for, 777, 820
and maximum flow, 786
and minimum-cost flow, 787– 788
and minimum-cost multicommodity flow, 790 ex.
and multicommodity flow, 788– 789
simplex algorithm for, 790– 804
and single-pair shortest path, 785– 786
and single-source shortest paths, 601– 607
slack form for, 781– 783
standard form for, 777– 781
see also integer linear-programming problem, 0-1 integer-programming problem
linear-programming relaxation, 1041
linear search, 21 ex.
line segment, 934
determining turn of, 936
determining whether any intersect, 940– 947
determining whether two intersect, 936– 938
link
of binomial trees, 457
of Fibonacci-heap roots, 483
LINK, 508
linked list, 204– 209
compact, 213 ex., 218 pr.
deletion from, 206
to implement disjoint sets, 501– 505
insertion into, 205– 206
neighbor list, 683
searching, 205, 236 ex.
list, see linked list
LIST-DELETE, 206
LIST-DELETE', 206
LIST-INSERT, 206
LIST-INSERT', 207
LIST-SEARCH, 205
LIST-SEARCH', 207
literal, 999
little-oh notation, 47– 48
little-omega notation, 48
Lm-distance, 962 ex.
ln (natural logarithm), 53
load factor
of a dynamic table, 417
of a hash table, 226
load instruction, 22
local variable, 19
logarithm function (log), 53– 54
discrete, 877
iterated (lg*), 55– 56
logic gate, 987
longest common subsequence, 350– 356, 369
LONGEST-PATH, 978 ex.
LONGEST-PATH-LENGTH, 978 ex.
longest-simple-cycle problem, 1017 ex.
longest simple path, 966
in an unweighted graph, 342
LOOKUP-CHAIN, 348
looping constructs in pseudocode, 19
loop invariant, 17
for breadth-first search, 534
for building a heap, 133
for consolidating the root list in extracting the minimum node from a Fibonacci heap, 486
for determining the rank of an element in an order-statistic tree, 305
for Dijkstra's algorithm, 597
for the generic minimum-spanning-tree algorithm, 562
for the generic push-relabel algorithm, 676
for heapsort, 136 ex.
for Horner's rule, 39 pr.
for increasing a key in a heap, 142 ex.
initialization of, 18
for insertion sort, 17– 19
and for loops, 18 n.
maintenance of, 18
for merging, 30
for modular exponentiation, 879– 880
origin of, 40
for partitioning, 146
for Prim's algorithm, 572
for the Rabin-Karp algorithm, 914
for randomly permuting an array, 103
for red-black tree insertion, 283
for the relabel-to-front algorithm, 687
for searching an interval tree, 315
for simplex algorithm, 798
for string-matching automata, 919, 921
and termination, 18
for uniting binomial heaps, 472 ex.
low endpoint of an interval, 311
lower bounds
for average sorting, 180 pr.
for convex hull, 956 ex.
for median finding, 195
for merging, 180 pr.
for minimum-weight vertex cover, 1042
and potential functions, 429
for size of a merging network, 718 ex.
for size of optimal vertex cover, 1026
for sorting, 165– 168
lower median, 183
lower-triangular matrix, 728
LU decomposition, 747– 750
LU-DECOMPOSITION, 749
LUP decomposition, 743
computation of, 750– 754
of a diagonal matrix, 754 ex.
in matrix inversion, 755– 756
and matrix multiplication, 759 ex.
of a permutation matrix, 754 ex.
use of, 743– 747
LUP-DECOMPOSITION, 752
LUP-SOLVE, 745

| < Day Day Up > |