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