Index

T

TABLE-DELETE, 422

TABLE-INSERT, 418

tail

of a binomial distribution, 1118-1125

of a linked list, 204

of a queue, 202

tail recursion, 162 pr., 376

target, 1013

Tarjan's off-line least-common-ancestors algorithm, 521 pr.

task, 399

task scheduling, 399-402, 404 pr.

tautology, 983 ex., 1002 ex.

Taylor series, 271 pr.

telescoping series, 1061

telescoping sum, 1061

testing

of primality, 887-896, 904

of pseudoprimality, 889-890

text in string matching, 906

then, in pseudocode, 19

3-CNF, 999

3-CNF-SAT, 999

3-CNF satisfiability, 998-1002

approximation algorithm for, 1039-1040

and 2-CNF satisfiability, 967

3-COLOR, 1019 pr.

3-conjunctive normal form, 999

tight constraint, 791

time, see running time

time domain, 822

timestamp, 540, 548 ex.

Toeplitz matrix, 844 pr.

TOP, 949

top of a stack, 200

topological sort, 549-552

in computing single-source shortest paths in a dag, 592

TOPOLOGICAL-SORT, 550

total net flow, 645

total order, 1077

total path length, 270 pr.

total positive flow, 645

tour

bitonic, 364 pr.

Euler, 559 pr., 966

of a graph, 1012

track, 435

tractability, 966

transition function, 916, 921-922

transitive closure, 632-635

and boolean matrix multiplication, 759 ex.

of dynamic graphs, 641 pr.

TRANSITIVE-CLOSURE, 633

transitive relation, 1075

transitivity of asymptotic notation, 49

transpose

conjugate, 759 ex.

of a directed graph, 530 ex.

of a matrix, 529, 726

transpose symmetry of asymptotic notation, 49

transposition network, 721 pr.

traveling-salesman problem

approximation algorithm for, 1027-1033

bitonic euclidean, 364 pr.

bottleneck, 1033 ex.

NP-completeness of, 1012-1013

with the triangle inequality, 1028-1031

without the triangle inequality, 1031-1032

traversal of a tree, see tree walk

treap, 296 pr.

TREAP-INSERT, 296 pr.

tree, 1085-1091

AA-trees, 301

AVL, 296 pr.

binary, see binary tree binomial, 457-459, 479

bisection of, 1092 pr.

breadth-first, 532, 538

B-trees, 434-454

decision, 166-167

depth-first, 540

diameter of, 539 ex.

dynamic, 432

free, 1083, 1085-1087

full walk of, 1030

fusion, 182, 433

heap, 127-144

height-balanced, 296 pr.

height of, 1088

interval, 311-317

k-neighbor, 301

minimum spanning, see minimum spanning tree

optimal binary search, 356-363, 369

order-statistic, 302-308

parse, 999

recursion, 36, 67-72

red-black, see red-black tree

rooted, 214-217, 1087

scapegoat, 301

search, see search tree

shortest-paths, 584, 610-613

spanning, see minimum spanning tree, spanning tree

splay, 301, 432

treap, 296 pr.

2-3, 300, 454

2-3-4, 439, 453 pr.

walk, see tree walk

weight-balanced trees, 301

TREE-DELETE, 262, 288

tree edge, 538, 540, 546

TREE-INSERT, 261, 280

TREE-MAXIMUM, 258

TREE-MINIMUM, 258

TREE-PREDECESSOR, 259

TREE-SEARCH, 257

TREE-SUCCESSOR, 259

tree walk, 254, 260 ex., 305, 1030

trial, Bernoulli, 1112

trial division, 888

triangle inequality, 1028

and negative-weight edges, 1032 ex.

for shortest paths, 587, 607-608

triangular matrix, 727-728, 733 ex.

trichotomy, interval, 311

trichotomy property of real numbers, 49

tridiagonal linear systems, 767 pr.

tridiagonal matrix, 727

trie, see radix tree

TRIM, 1046

trimming of a list, 1045

trivial divisor, 851

truth assignment, 988, 996

truth table, 987

TSP, 1012

tuple, 1074

twiddle factor, 836

2-CNF-SAT, 1003 ex.

2-CNF satisfiability, 1003 ex.

and 3-CNF satisfiability, 967

two-pass method, 508

2-3-4 heap, 473 pr.

2-3-4 tree, 439

joining, 453 pr.

and red-black trees, 441 ex.

splitting, 453 pr.

2-3 tree, 300, 454