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

lg^k (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

L_m-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