recurrence, 53

recurrence equation, 21

recursive algorithm, 20

red-black properties, 266

red-black tree, 266

reflexive relation, 80

reflexivity, 33

relation/ra-ary, 80

relation/binary, 80

resursion tree, 58

right child, 95

right subtree, 95

root of a tree, 93

root/of a binary tree, 95

rooted tree, 93, 214

rotation, 269

rule of product, 101

rule of sum, 100

running time, 16

running time/average-case, 18

running time/expexted, 18

running time/worst-case, 18

sample space, 106 satellite data, 137, 197 schedule, 351 scheduling problem, 351 search tree, 246

search tree/randomly built, 256 search/binary, 23 searching problem, 15 searching/linear search, 15 secondary clustering, 238 selection problem, 184 selection sort, 19 self-loop, 86 sentinel, 207, 275 sequence/finite, 83 sequence/infinite, 83 series, 43

series/absolutely convergent, 44 series/arithmetic, 44 series/convergent, 44 series/divergent, 44 series/exponential, 44 series/geometric, 44

series/harmonic, 45 series/telescoping, 45 set, 75

set operations, 76

set/countably infinite, 78

set/dynamic, 197

set/empty, 75, 76

set/finite, 78

set/infinite, 78

set/of integers, 75

set/of natural numbers, 75

set/of real numbers, 75

set/partially ordered, 81

set/uncountable, 78

Shannon entropy, 104

side, 321

simple cycle, 88

simple directed graph, 88

simple path, 87

simple polygon, 321

simple uniform hashing, 226

simulation/event-driven, 149

singleton, 78

singly linked list, 205

size, 78

slot, 221

soblings, 94

solution/to a computational problem, 12

son, 94

sorted list, 205

sorting problem, 11, 137

sorting/in place, 12, 138

spanning tree, 347

splay tree, 283

stable sort, 174

stack, 201

stack/depth, 168

standard deviation, 116

Stirlings approximation, 38

strictly decreasing (increasing)

function, 34 string, 101

strongly connected graph, 88 subgraph, 89 subpath, 87

subsequence, 316 subsequence/common, 316 subsequence/longest common, 316

subset of a set, 76 substitution method, 53, 54 substring, 101 subtree/rooted at ж, 94 success, 117

summation formulas, 43 surjection, 84 symmetric relation, 80 symmetry, 33

tail (of a list), 205 tail (of a queue), 203 tail recursion, 168 tails of the binomial distribution, 123 task, 351

Taylor expansion, 263 telescoping series, 45 theorem/Bayess, 110 top, 202 total order, 82 transitive relation, 80 transitivity, 33

travelling-salesman problem, 326

tree, 90 tree/A;-ary, 96 tree/balanced, 266 tree/binary, 95, 214 tree/complete fc-ary, 96 tree/free, 90, 91 tree/order-statistic, 284 tree/ordered, 95 tree/positional, 96 tree/radix, 261 tree/red-black, 266 tree/rooted, 93, 214 triangulation, 322

uncountable set, 78 underflow, 202 undirected graph, 86

undirected version (of a directed graph), 89

uniform hashing, 236

uniform probability distribution, 108

union, 76

universal hashing, 232 universe, 77 unordered pair, 86

value, 83

variable-length code, 338 variance, 115 vertex, 86, 321 vertex/adjacent to u, 87 vertex/reachable, 87 Viterbi algorithm, 328

weighted matroid, 347 weighted median, 193 worst-case running time, 18

хвост очереди, 203

абзац, разбиение на строки, 326

абсолютно сходящийся ряд, 44 аксиомы вероятности, 106 алгоритм,11

алгоритм/вероятностный, 159

алгоритм/жадный, 331 алгоритм/правильный, 12 алгоритм/рекурсивный, 20 алфавит, 101

антисимметричное отношение, 81 аргумент функции, 83, 84 арифметическая прогрессия, 44

асимптотика, 30

асимптотически неотрицательная функция, 31

асимптотически положительная функция, 36

асимптотически точная оценка, 31

ассоциативность, 76 атрибут объекта, 14 ацикличный подграф, 354

Байеса формула, 110 Бернулли схема, 117 бесконечная последовательность, 83 бесконечное множество, 78 биекция, 84

бинарное отношение, 80

бином Ньютона, 103

биномиальное распределение, 118, 123

биномиальные коэффициенты, 103

битовый вектор, 223

битонический путь, 326

братья, 94

булева функция, 104

Буля/неравенство, 111

быстрая сортировка, 138, 152

вектор/битов, 223 вероятностей распределение, 106

вероятностей/теория, 100 вероятностное пространство, 106

вероятностный алгоритм, 159 вероятностный счётчик, 133 вероятность события, 107 вероятность/условная, 109 версии, сохранение прежних, 281

вершина графа, 86

вершина многоугольника, 321

вершина стека, 202

вершина/внутренняя, 94

вершина/достижимая, 87

вершина/смежная, 87

вершина/соседняя, 89

вещественных чисел множество, 75

взаимно однозначное соответствие, 85

взвешенная медиана, 193 взвешенный матроид, 347 Витерби алгоритм, 328 включений и исключений

формула, 80 вложение, 84

внешность многоугольника, 321

внешняя сумма длин, 97 внутренность многоугольника, 321 внутренняя вершина, 94 внутренняя сумма длин, 97 вращение, 269

время работы алгоритма, 16

время работы/в худшем случае, 18

время работы/среднее, 18

вход алгоритма, 11

вход/задачи сортировки, 11

вход/размер, 16

входящая степень, 87

входящее в вершину ребро, 87

вызов процедуры, 16

выполнение процедуры, 16

выполненный в срок заказ, 351

выпуклый многоугольник, 321

высота вершины, 141 высота дерева, 94 высота/чёрная, 267 выходящее из вершины ребро, 87

вычерпывание, 178 вычислительная задача, 11 вычислительнаязада-

ча/решение, 12

гармонический ряд, 45 генератор псевдослучайных

чисел, 159 генератор случайных чисел,

159

геометрическая прогрессия, 44