Index

This index uses the following conventions. Numbers are alphabetized as if spelled out; for example, "2-3-4 tree" is indexed as if it were "two-three-four tree." When an entry refers to a place other than the main text, the page number is followed by a tag: ex. for exercise, pr. for problem, fig. for figure, and n. for footnote. A tagged page number often indicates the first page of an exercise, problem, figure, or footnote; this is not necessarily the page on which the reference actually appears.

Symbols

α(n), 511

o-notation, 47-48

O-notation, 43 fig., 44-45

O'-notation, 59 pr.

õ-notation, 59 pr.

ω-notation, 48

Ω-notation, 43 fig., 45-46

-notation, 59 pr.

-notation, 59 pr.

ρ(n)-approximation algorithm, 1022

Θ-notation, 42-44, 43 fig.

-notation, 59 pr.

{ } (set), 1070

∈ (set member), 1070

∉ (not a set member), 1070

Ø (empty set), 1070

⊆ (subset), 1071

⊂ (proper subset), 1071

: (such that), 1071

∩ (set intersection), 1071

∪ (set union), 1071

- (set difference), 1071

||

(flow value), 644

(length of a string), 907

(set cardinality), 1073

×

(Cartesian product), 1074

(cross product), 934

〈〉

(sequence), 1078

(standard encoding), 975

(choose), 1096

!(factorial), 54

⌈;⌉; (ceiling), 51

⌊⌋ (floor), 51

Σ (sum), 1058

Π (product), 1061

→ (adjacency relation), 1080

(reachability relation), 1081

⊥ (AND), 633, 987

¬ (NOT), 987

⊦ (OR), 633, 987

⊕ (group operator), 862

⊗ (convolution operator), 825

*(closure operator), 976

| (divides relation), 850

∤ (does-not-divide relation), 850

≡ (equivalent modulo n), 52, 1077 ex.

≢ (not equivalent modulo n), 52

[a]_n (equivalence class modulo n), 851

+_n (addition modulo n), 863

·_n (multiplication modulo n), 863

(Legendre symbol), 903 pr.

ε (empty string), 907, 976

⊏ (prefix relation), 907

⊐ (suffix relation), 907

>_x (above relation), 941

⊳ (comment symbol), 19

≤_P (polynomial-time reducibility relation), 984, 994 ex.