O

| < Day Day Up > |

# Index

### O

o-notation, 47– 48
O-notation, 43 fig., 44– 45
O'-notation, 59 pr.
õ-notation, 59 pr.
object, 20
allocation and freeing of, 210– 212
array implementation of, 209– 213
passing as parameter, 20
objective function, 601, 606– 607 ex., 773, 777
objective value, 774, 778
optimal, 778
occurrence of a pattern, 906
odd-even merging network, 721 pr.
odd-even sorting network, 721 pr.
OFF-LINE-MINIMUM, 519 pr.
off-line problem
least common ancestors, 521 pr.
minimum, 518 pr.
Omega-notation, 43 fig., 45– 46
1-approximation algorithm, 1023
one-pass method, 522
one-to-one correspondence, 1079
one-to-one function, 1079
one-way hash function, 886
on-line convex-hull problem, 957 ex.
on-line hiring problem, 114– 117
ON-LINE-MAXIMUM, 115
ON-SEGMENT, 937
onto, 1079
open-address hash table, 237– 245
double hashing, 240– 241, 244 ex.
linear probing, 239
quadratic probing, 239– 240, 250 pr.
open interval, 311
optimal binary search tree, 356– 363, 369
OPTIMAL-BST, 361
optimal objective value, 778
optimal solution, 778
optimal subset of a matroid, 395
optimal substructure
of activity selection, 371– 373
of assembly-line scheduling, 325– 327
of binary search trees, 359
in dynamic programming, 339– 344
of the fractional knapsack problem, 382
in greedy algorithms, 381– 382
of Huffman codes, 391
of longest common subsequences, 351– 352
of matrix-chain multiplication, 333– 334
of shortest paths, 581– 582, 623, 629
of unweighted shortest paths, 342
of weighted matroids, 397
of the 0-1 knapsack problem, 382
optimal vertex cover, 1024
optimization problem, 323, 968, 972
approximation algorithms for, 1022– 1054
and decision problems, 969
OR function (∨), 633, 987
or, in pseudocode, 20
order
of a group, 867
linear, 1077
partial, 1076
total, 1077
ordered pair, 1073
ordered tree, 1088
order of growth, 26
order statistics, 183– 195
dynamic, 302– 308
order-statistic tree, 302– 308
querying, 310 ex.
OR gate, 987
origin, 934
orthonormal, 769
OS-KEY-RANK, 307 ex.
OS-RANK, 305
OS-SELECT, 304
out-degree, 1081
outer product, 730
output
of an algorithm, 5
of a combinational circuit, 988
of a logic gate, 987
output sequence, 705
output wire, 705
overdetermined system of linear equations, 743
overflow
of a queue, 202
of a stack, 201
overflowing vertex, 670
overlapping intervals, 311
finding all, 317 ex.
point of maximum overlap, 318 pr.
overlapping rectangles, 317 ex.
overlapping subproblems, 344– 346
overlapping-suffix lemma, 908

| < Day Day Up > |