D

| < Day Day Up > |

# Index

### D

dag, see directed acyclic graph
DAG-SHORTEST-PATHS, 592
d-ary heap, 143 pr.
in shortest-paths algorithms, 641 pr.
data-movement instructions, 22
data structure, 8, 197– 318, 431– 522
AA-trees, 301
augmentation of, 302– 318
AVL trees, 296 pr.
binary search trees, 253– 272
binomial heaps, 455– 475
bit vectors, 222 ex.
B-trees, 434– 454
deques, 204 ex.
dictionaries, 197
direct-address tables, 222– 223
for disjoint sets, 498– 522
for dynamic graphs, 433
dynamic sets, 197– 199
dynamic trees, 432
exponential search trees, 182, 433
Fibonacci heaps, 476– 497
fusion trees, 182, 433
hash tables, 224– 229
heaps, 127– 144
interval trees, 311– 317
k-neighbor trees, 301
linked lists, 204– 209
order-statistic trees, 302– 308
persistent, 294 pr., 432
potential of, 413
priority queues, 138– 142
queues, 200– 203
radix trees, 269 pr.
red-black trees, 273– 301
relaxed heaps, 497
rooted trees, 214– 217
scapegoat trees, 301
on secondary storage, 434– 437
skip lists, 301
splay trees, 301, 432
stacks, 200– 201
treaps, 296 pr.
2-3-4 heaps, 473 pr.
2-3-4 trees, 439, 453 pr.
2-3 trees, 300, 454
van Emde Boas, 433
weight-balanced trees, 301
deadline, 399
deallocation of objects, 210– 212
decision by an algorithm, 976
decision problem, 969, 972
and optimization problems, 969
decision tree, 166– 167
zero-one principle for, 712 ex.
DECREASE-KEY, 138, 455
decreasing a key
in binomial heaps, 470
in Fibonacci heaps, 489– 492
in 2-3-4 heaps, 473 pr.
DECREMENT, 409 ex.
degeneracy, 802
degree
of a binomial-tree root, 457
maximum, of a Fibonacci heap, 479, 488 ex., 493– 496
minimum, of a B-tree, 439
of a node, 1088
of a polynomial, 52, 822
of a vertex, 1081
degree-bound, 822
DELETE, 198, 455
DELETE-LARGER-HALF, 416 ex.
deletion
from binary search trees, 262– 263
from binomial heaps, 470– 471
from B-trees, 449– 452
from chained hash tables, 226
from direct-address tables, 222
from dynamic tables, 422
from Fibonacci heaps, 492, 496 pr.
from heaps, 142 ex.
from interval trees, 313
from linked lists, 206
from open-address hash tables, 238
from order-statistic trees, 307
from queues, 201
from red-black trees, 288– 294
from stacks, 200
from sweep-line statuses, 942
from 2-3-4 heaps, 473 pr.
demand paging, 22
DeMorgan's laws, 1072
dense graph, 527
∈-dense, 641 pr.
density of prime numbers, 887– 888
dependence
and indicator random variables, 96
linear, 731
see also independence
depth
average, of a node in a randomly built binary search tree, 270 pr.
of a comparison network, 707
of a node in a rooted tree, 1088
of quicksort recursion tree, 153 ex.
of SORTER, 720 ex.
of a sorting network, 708 ex.
of a stack, 162 pr.
depth-determination problem, 519 pr.
depth-first forest, 540
depth-first search, 540– 549
in finding articulation points, bridges, and biconnected components, 558 pr.
in finding strongly connected components, 552– 557
in topological sorting, 549– 552
depth-first tree, 540
deque, 204 ex.
DEQUEUE, 203
derivative of series, 1060
descendant, 1087
destination vertex, 581
det, see determinant
determinant, 732
and matrix multiplication, 759 ex.
deterministic, 99
DETERMINISTIC-SEARCH, 118 pr.
DFS, 541
DFS-VISIT, 541
DFT (Discrete Fourier Transform), 833
diagonal matrix, 726
LUP decomposition of, 754 ex.
diameter of a tree, 539 ex.
dictionary, 197
difference constraints, 601– 607
difference equation, see recurrence
difference of sets (-), 1071
symmetric, 696 pr.
differentiation of series, 1060
digital signature, 883
digraph, see directed graph
DIJKSTRA, 595
Dijkstra's algorithm, 595– 601
for all-pairs shortest paths, 620, 639
implemented with a Fibonacci heap, 599
implemented with a min-heap, 599
with integer edge weights, 600– 601 ex.
in Johnson's algorithm, 639
similarity to breadth-first search, 599, 600 ex.
similarity to Prim's algorithm, 570, 599
DIRECT-ADDRESS-DELETE, 222
direct addressing, 222– 223
DIRECT-ADDRESS-INSERT, 222
DIRECT-ADDRESS-SEARCH, 222
direct-address table, 222– 223
directed acyclic graph (dag), 1083
and back edges, 550
and component graphs, 554
and hamiltonian-path problem, 983 ex.
single-source shortest-paths algorithm for, 592– 595
topological sort of, 549– 552
directed graph, 1080
all-pairs shortest paths in, 620– 642
constraint graph, 603
Euler tour of, 559 pr., 966
hamiltonian cycle of, 967
and longest paths, 966
path cover of, 692 pr.
PERT chart, 594, 594 ex.
semiconnected, 557 ex.
shortest path in, 580
single-source shortest paths in, 580– 619
singly connected, 549 ex.
square of, 530 ex.
transitive closure of, 632
transpose of, 530 ex.
see also circuit, directed acyclic graph, graph, network
directed segment, 934– 935
directed version of an undirected graph, 1082
DIRECTION, 937
DISCHARGE, 683
discharge of an overflowing vertex, 683
discovered vertex, 531, 540
discovery time, in depth-first search, 541
Discrete Fourier Transform, 833
discrete logarithm, 877
discrete logarithm theorem, 877
discrete probability distribution, 1101
discrete random variable, 1106– 1111
disjoint-set data structure, 498– 522
analysis of, 512– 517, 518 ex.
in depth determination, 519 pr.
disjoint-set-forest implementation of, 505– 509
in Kruskal's algorithm, 569
linear-time special case of, 522
linked-list implementation of, 501– 505
in off-line least common ancestors, 521 pr.
in off-line minimum, 518 pr.
in task scheduling, 404 pr.
disjoint-set forest, 505– 509
analysis of, 512– 517, 518 ex.
rank properties of, 511– 512, 518 ex.
see also disjoint-set data structure
disjoint sets, 1073
disjunctive normal form, 1000
disk, 947 ex.
see also secondary storage
DISK-READ, 437
DISK-WRITE, 437
distance
edit, 364 pr.
euclidean, 957
Lm, 962 ex.
Manhattan, 194 pr., 962 ex.
of a shortest path, 534
distribution
binomial, 1113– 1116
geometric, 1112
of inputs, 93, 99
of prime numbers, 888
probability, 1100– 1102
sparse-hulled, 964 pr.
distributive laws for sets, 1072
divergent series, 1059
divide-and-conquer method, 28– 33
analysis of, 32– 33
for binary search, 37 ex.
for conversion of binary to decimal, 856 ex.
for Fast Fourier Transform, 834– 836
for finding the closest pair of points, 958– 961
for finding the convex hull, 948
for matrix inversion, 756– 758
for merge sort, 28– 36
for multiplication, 844 pr.
for quicksort, 145– 164
and recursion trees, 67
relation to dynamic programming, 323
for selection, 185– 193
solving recurrences for, 62– 90
for Strassen's algorithm, 735– 742
divide instruction, 22
divides relation (|), 850
division method, 230– 231
division theorem, 851
divisor, 850– 851
common, 852
see also greatest common divisor
DNA, 350, 364 pr.
DNF (disjunctive normal form), 1000
does-not-divide relation (∤), 850
domain, 1077
dominates relation, 962 pr.
double hashing, 240– 241, 244 ex.
doubly linked list, 204
see also linked list
d-regular graph, 669 ex.
duality, 804– 811
weak, 805
dual linear program, 805
dynamic graph, 499 n.
data structures for, 433
minimum-spanning-tree algorithm for, 574 ex.
transitive closure of, 641 pr.
dynamic order statistics, 302– 308
dynamic-programming method, 323– 369
for activity selection, 378 ex.
for all-pairs shortest paths, 622– 632
for assembly-line scheduling, 324– 331
for bitonic euclidean traveling-salesman problem, 364 pr.
compared to greedy algorithms, 341, 350 ex., 373– 375, 380, 382– 383
for edit distance, 364 pr.
elements of, 339– 350
for Floyd-Warshall algorithm, 629– 632
for longest common subsequence, 350– 356
for matrix-chain multiplication, 331– 339
and memoization, 347– 349
for optimal binary search trees, 356– 363
optimal substructure in, 339– 344
overlapping subproblems in, 344– 346
for printing neatly, 364 pr.
reconstructing an optimal solution in, 346– 347
for scheduling, 369 pr.
for transitive closure, 632– 635
for Viterbi algorithm, 367 pr.
for 0-1 knapsack problem, 384 ex.
dynamic set, 197– 199
see also data structure
dynamic table, 416– 425
analyzed by accounting method, 419
analyzed by aggregate analysis, 418– 419
analyzed by potential method, 419– 420, 422– 424
load factor of, 417
dynamic tree, 432

| < Day Day Up > |