Index
Note: Italicized page locators indicate figures.
A
Ackermann’s function, 226
Addition
in polynomial calculations, 110, 111
Additive operators (additions), 11
Adjacency lists, 147, 149 , 228
Adjacency matrix, 147, 148
form, 207
for fully connected weighted graph, 234
Algorithms
analysis of, 2, 3-10
common classes of, 21
divide and conquer, 24-31
greedy approximation, 232-239
growth rate of, 20-23
probabilistic, 240-250
for sequential search, 43
Strassen’s, 115-116
Winograd’s, 114. See also Graph algo-
rithms; Matching algorithms; Parallel
algorithms; Sorting algorithms
Analysis/analysis basics, 1-39
defined/discussed, 3-10
divide and conquer algorithms, 24-31
input classes, 7-8
mathematical background, 13-18
program analysis, 38-39
rates of growth, 20-23
recurrence relations, 32-37
space complexity, 9-10
what to count and consider, 10-13
Approximate string matching, 136-138, 252
Approximation algorithms, 232-239
backpack, 236
bin packing, 235-236
graph coloring, 238-239
subset sum, 236-238
traveling salesperson, 233-234
Arbitrary model, 185
Arithmetic operators, 11
Arrays
for buckets, 76
majority element in, 245
methods based on, 252-255
Articulation points
of graphs, 169
Art of Computer Programming, The (Knuth), 71
Average-case analysis, 12
for binary search, 49-51
of bubble sort, 65-66
for heapsort, 82
for insertion sort, 60-62