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, 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

L_m, 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