T

| < Day Day Up > |

# 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

| < Day Day Up > |