S[ Top ]
S-box substitutions, 430, 434-443
scatter plots, 344
scientific computing, 344
scrolled lists, 52
searching
applications of, 142, 259
with binary search, 333-339
with binary search trees, 203-230
in graphs
breadth-first search, 264, 284-290
depth-first search, 266-267
with hash tables, 143-177
linear, 301
second-chance page replacement, 91-94
semaphores, 98
semiweak key pairs, 457
send_comp function, 396
set covering, 116, 133-138
Set structure, 122
set_destroy, 119, 124
set_difference, 121, 125, 131, 139
set_init, 119, 123, 126, 134
set_insert, 120, 124, 127
set_intersection, 121, 125, 130, 138-139
set_is_equal, 122, 126, 133, 138
set_is_member, 121, 125, 131
set_is_subset, 121, 125, 132, 138
set_remove, 120, 124, 127
sets, 115-140
absorption laws, 118
sets (continued)
applications of, 115-116
associative laws, 118
bit-vector representation, 140
commutative laws, 118
covering, 133
DeMorgan's laws, 119
description of, 116-119
destroy, 119, 124
determine membership, 121, 125
difference, 117, 121, 125
distributive laws, 118
empty, 117
empty set laws, 118
equal, 117, 122, 126
idempotency laws, 118
implementation and analysis of, 122-133
initialize, 119, 123
insert member, 120, 124, 140
interface for, 119-122
intersection, 117-119, 121, 125
linked list implementation, 122
membership, 117
multisets, 140
remove member, 120, 124
size of, 122, 126
subsets, 117, 121, 125
symmetric difference, 139
union, 117-118, 120, 124
Venn diagrams, 119, 140
set_size, 122, 126
set_union, 120, 124, 128
Shannon-Fano coding, 421
shortest function, 474
shortest path first (SPF) routing, 482
shortest paths, 460, 472-485
description of, 472-474
example of, 481-485
implementation and analysis of, 475-481
interface for, 474
list returned by shortest function, 476
relaxation, 476
SPF routing, 482
sibling nodes, 180, 230
simplicity of code, 9
single-pair shortest-path problem, 472
single-source shortest-paths problem, 472
singly-linked lists, 51-68
sliding window, 399
slope, 356
smart cards, 424
software distribution, 366
solution of equations, 343, 355-362
convergence, 363
derivatives of functions, 356
implementation and analysis of, 360
initial point selection, 357
interval size effects, 363
Newton's method, 355, 357, 359-361
roots, 355
sorting, 301, 303, 307, 317, 324, 329-333
applications of, 302
bubble sort, 341
bucket sort, 342
comparison sorts, 301
counting sort, 302
heapsort, 235, 341
insertion sort, 302
introsort, 341
linear-time sorts, 301, 324, 329
merge sort, 302
priority queues, 180, 254
quicksort, 302
radix sort, 302, 339
single element insertions, 339
stable attribute, 324, 330
successors, finding, 341
topological, 260, 290-295
tournament sort, 341
sparse graphs, 264
spell checkers, 303, 337-339
spell function, 337
spherical coordinate system, 513
spherical surfaces, 512-520
SPoint structure, 499, 515
spreadsheets, 303
SQL (Structured Query Language), 116
stable sorts, 324
stack frame, 30
Stack structure, 102, 113
stack_destroy, 100, 103
stack_init, 100, 103
stack_peek, 101, 104
stack_pop, 101, 103
stack_push, 101, 103
stack_size, 101
stacks, 30, 98, 100-105
applications of, 98
data structure, 102
description of, 99
destroy, 100, 103
frame pointer, 36
implementation and analysis of, 102-105
initialize, 100, 103
interface for, 100-101, 113
overflow, 36
peek, 100-101, 104
pop, 99, 101, 103
push, 99, 101, 103
recursion, 31
size of, 101, 104
tail recursion, 34
starvation, 258
statistical modeling, 421
statistical relationship, 352
storage allocation, 13
straddle test, 501
stream ciphers, 459
strongly connected components, 262
strongly connected graphs, 262
Structured Query Language (SQL), 116
structures, 9, 15
subkey computation, 426
subsets, 117, 121, 125
summation formulas, 48
Symbol structure, 158
symbol tables, 142, 157-160
lexemes, 157
lexical analyzers, 157
parsers, 157
tokens, 157
symbol tokens, 400, 404
symmetric ciphers, 425
system states model, 296
T[ Top ]
tagged buffers, 142
tail recursion, 32
tail recursion elimination, 37
task scheduling, 236
terminal values (expression trees), 199
terminating condition, 28
testing line segment intersection (see line segment intersection, testing)
tokens, 157, 399-418
compiler, 157
Lempel-Ziv-1977 (LZ77), 399, 403
phrase tokens, 404
symbol tokens, 404
top-heavy heaps, 236
topological sorting, 260, 290-295
topology of networks, 481
tournament sort, 341
traffic monitoring, 462
transpose of a graph, 297
traveling-salesman problem, 8, 260, 461, 485, 487-493
closed transport systems, 461
description of, 485-487
exchange heuristic, 495
implementation and analysis of, 488-493
interface for, 487
minimum spanning tree approximation, 493
nearest-neighbor heuristic, 486-487
traversal methods, 178, 180-182, 201-202
expression trees, 199
inorder traversal, 182, 199
level-order traversal, 182
postorder traversal, 182, 199, 231
preorder traversal, 181, 199, 231
recursive, 201
trees, 178, 235
applications of, 179
Bx-, 233
B+-, 231, 233
B-, 232-233
balancing, 178
binary, 178, 180-234
binary search, 179, 203-230
decision, 179
k-ary, 233
partially ordered, 236
red-black, 233
traversal of (see traversal methods)
tries, 233
tsp function, 487, 489
TspVertex structure, 463, 488
typedef, 102
U[ Top ]
undirected graphs, 261
uniform hashing, 143
union of sets, 120, 124
universal hashing, 177
unwinding phase, 28
user interfaces, 179
V[ Top ]
variables
automatic, 13
casts, 23
storage allocation, 13
types, 23
vector components, 523
vectors, 502, 523
Venn diagrams, 119, 140
vertices, 259, 261
virtual addresses, 65
virtual memory, 65
page-replacement algorithm, 91
versus physical memory, 65
virtual reality systems, 497
void pointers, 21
W[ Top ]
weak keys, 456
weighted graphs, 460
winding phase, 28
wiring circuit boards, 462
worst-case analysis, 39
wrapper function, 340
X[ Top ]
X Window System, 110