free list, 212

free tree, 90, 91

function, 83

function/boolean, 104

function/generating, 71

function/inverse, 85

function/linear, 17

function/monotonically decreasing (increasing), 34

function / polylogarithmically bounded, 37

function / polynomially bounded, 36

function/quadratic, 17

function/strictly decreasing (increasing), 34

garbage collector, 211 generating function, 71 geometric distribution, 117 geometric series, 44 golden ratio, 39 graph/bipartite, 90 graph/complete, 90 graph/connected, 88 graph/directed, 86 graph/isomorphic, 88 graph/simple directed, 88 graph/strongly connected, 88 graph/undirected, 86 graphic matroid, 346 greedoid, 356 greedy algorithm, 331 greedy-choice property, 335

handshaking lemma, 90 harmonic series, 45 hash function, 221, 224 hash table, 221, 224 hash value, 224 hashing/simple uniform, 226 head (of a list), 205 head (of a queue), 203 heap property, 141 heap/<i-ary, 151

heap/binary, 138, 140 heapsort, 138, 140, 147 height, 141 height of a tree, 94 hereditary family, 346 high endpoint, 292 hyperedge, 90 hypergraph, 90

idempotency laws, 76 image, 84 in-degree, 87

incidence matrix, 354, 355 incident from, 87 incident on, 87 incident to, 87 incremental approach, 19 independent events, 109 independent random variables, 113

independent subset, 346, 352 induced subgraph, 89 inequality/Booles, 111 inequality/Markovs, 116 infinite sequence, 83 infinite set, 78 injection, 84 inorder tree walk, 247 input, 11 input size, 16 insertion sort, 12 Insertion-Sort, 16 instance, 11 integers, 75 interior, 321 internal node, 94 internal path length, 97 intersection, 76 interval tree, 292 interval-graph coloring problem, 334 interval/closed, 292 interval/half-closed, 292 interval/open, 292 inverse function, 85 inversions, 25

isomorphic graphs, 88 iterated logarithm, 38 iteration method, 53

join, 282

joint probability density function, 113 Josephus permutation, 298

key, 137, 148, 197 knapsack problem, 336 Kraft inequality, 97

late task, 351

LCS (longest common subsequence), 316

leaf, 94

left child, 95

left subtree, 95

left-child, right-sibling representation, 215 length, 87

lexicographically less, 261 LIFO, 201 linear function, 17 linear order, 82 linear probing, 237 linear programming, 329 linear search, 15 linked list, 205 List-Delete, 207 List-DeleteList-Delete[], 207

List-Insert, 208 List-InsertLiST-lNSERT[], 208 List-Search, 208 List-SearchList-Search[], 208

list/circular, 205 list/doubly linked, 205 list/linked, 205 list/singly linked, 205 list/sorted, 205 logarithm, 37 logarithm/iterated, 38 longest common subsequence, 316

low endpoint, 292

Markovs inequality, 116 master theorem, 53, 61 matric matroid, 346 matrix-chain multiplication

problem, 305 matroid, 346 maximal element, 82 maximum, 184 maximum overlap, 297 mean, 113 median, 184

median-of-3 method, 169

member, 75

memoization, 314

merge, 20

merge sort, 20

mergeable heaps, 218

minimum, 184

minimum spanning tree, 348

modifying operation, 198

monotonically decreasing (increasing) function, 34

multigraph, 90

multiplication method, 231

mutually exclusive events, 106

mutually independent events, 109

natural number, 75 neighbor, 89 node, 93

node/external, 94 node/internal, 94 null event, 106

objects, 14

one-to-one correspondence, 85 one-to-one function, 84 open addressing, 235 optimal subset, 348 optimal substructure, 311, 335 optimal tiangulation problem, 322

optimization problem, 303 order of growth, 18

order statistic, 184 order statistics, 139 order-statistic tree, 284 ordered pair, 78 ordered tree, 95 out-degree, 87 output, 11 overflow, 202

overlapping segments, 292 overlapping subproblems, 312

pair/ordered, 78 pair/unordered, 86 pairwise disjoint sets, 78 pairwise independent events, 109

paragraph, 326

parameters, 14

parent, 94

partial order, 81

partially ordered set, 81

partition, 77

Pascal triangle, 105

path, 87

path/simple, 87

penalty, 351

permutation, 85, 101

persistent data structure, 281

point/of maximum overlap, 297

polygon, 321

polylogarithmically bounded

function, 37 polynomially bounded function,

36

position, 221 positional tree, 96 post-office location problem, 193

postorder tree walk, 248 power set, 78 prefis code, 339 prefix, 317

preorder tree walk, 248 primary clustering, 237 principle of inclusion and exclusion, 80

priority queue, 148 probabilistic counting, 133 probability axioms, 106 probability density function, 112

probability distribution, 106

probability distribution function, 180

probability theory, 100

probability/conditional, 109

probe sequnce, 235

problem/computational, 11, 12

problem/solution to, 12

product, 46

proper ancestor, 93

proper descendant, 93

proper subset, 76

pseudocode, 12, 14

pseudorandom-number generator, 159

quadratic function, 17 quadratic probing, 238 quantiles, 191 query, 198 queue, 201, 203 queue/priority, 148 quicksort, 138, 152 Quicksort, 168 QuicksortQuiCKSORT[], 168

radix sort, 138, 175 radix trees, 261 RAM, 15

random variable/discrete, 112 random-access machine, 15 random-number generator, 159 randomized algorithm, 159 randomly built seacrh tree, 256 range, 84 rank, 162, 286 rate of growth, 18 RB-свойства, 266 reachable vertex, 87 real number, 75 record, 137