book cover

Index to
Programming Pearls


72, Rule of    69, 74, 203, 216


Abrahams, P. W.    viii
abstract data types    27, 29, 130, 133-142, 152-155, 158
Adams, J. L.    9, 127
Adriance, N.    vii
affix analysis    30, 144, 213
Aho, A. V.    vii, 8, 86, 159, 178, 207, 213
airplanes    6, 98, 183-184
algorithm design    vi, 11-20, 62, 64, 77-86, 91, 115-122, 127-129, 131, 149-157
algorithms, divide-and-conquer    62, 79-81, 84-85, 116
algorithms, multiple-pass    4-5, 7, 207
algorithms, numerical    182
algorithms, randomizing    13, 120
algorithms, scanning    81, 84
algorithms, selection    18, 123, 181, 212, 223
algorithms, string    15-16, 18-20, 98, 123, 144-146, 161-173, 182, 219, 230-231
algorithms, vector    182
allocation, dynamic    105
allocation, storage    87, 137
anagrams    11, 15-20, 209
analysis, affix    30, 144, 213
analysis, big-oh    62, 78
analysis, retrograde    110
Appel, A. W.    61-65, 91
Apple Macintosh    107
Archimedes    201, 212
arrays    12, 22-23, 25-27, 29, 33-55, 77-86, 91, 100-103, 105, 115-125, 135-138, 142-143, 148, 153, 197, 201-202
arrays, cumulative    79, 84, 203, 217
arrays, sparse    8, 100-103
arrays, suffix    165-173
assembly code    62, 95, 107
assertions    37-41, 48-50
automobiles    7, 9, 66, 85, 202
Awk    171, 213


back of the envelope    9, 15, 25, 62, 64, 67-76, 78, 127, 145, 176, 183-184
background data    3, 15, 18, 25, 87, 125, 144, 176
bags, paper    127
Baird, H. S.    vii
Basic    127
Basic, Visual    25, 27-28, 54
Bell, C. G.    65
Bentley, D. T.    viii
Bentley, J. C.    125
Berecz, V.    98
Bible, King James    162, 230
big-oh analysis    62, 78
binary search    12-13, 16, 18, 33-55, 92-95, 97-98, 170-172, 181, 201, 203-204, 208-209, 213-214, 219, 230
binary search trees    13, 138-140, 164, 171, 181, 198
binary trees    62, 147
binary trees, implicit    148
bins    88, 141-143, 200, 229
Birthday Paradox    204, 224
Bitmap Sort    5-8, 140-141, 180, 205-207
bitmaps    5-8, 13, 140-141, 145, 199, 207
blocks, conceptual    3, 9, 21-26, 92
Boolean Variable Elimination    193
boring stuff    37-39
bounds, lower    84-85, 204, 217
Boyer, R. S.    85
Bridge, Brooklyn    72
Bridge, Golden Gate    183-184
Bridge, Tacoma Narrows    72
Brooklyn Bridge    72
Brooks, F. P., Jr.    v, 29, 99-100, 109-110, 220
bugs, performance    72, 89, 91, 119
Butler, S.    166
Buzen, J. P.    73


C    19, 45-55, 87-95, 97, 121, 123-125, 171-172, 177, 206, 224, 231
C++    27, 45, 90, 121, 123-124, 127, 133-143, 158, 171-172, 177, 185, 197-200, 206, 214, 224, 231
C Standard Library    19, 122, 177, 205, 219
C++ Standard Template Library    121-122, 128, 134, 142, 159, 161-162, 164, 172, 177, 197, 205-206, 219, 230
cache-sensitive code    17, 89, 105, 107, 109, 137, 139, 142, 211, 214
Caching    191
calculators    28
canonical forms    16
Cargill, T. A.    16
casting out nines    69, 74
character classification    98, 219
chess    110-111
children    76
Childress, G. L.    viii
classification, character    98, 219
Cleveland, W. S.    vii
Cobol    25
code, cache-sensitive    17, 89, 105, 107, 109, 137, 139, 142, 211, 214
Code Motion Out of Loops    192
code tuning    62, 64-65, 87-98, 116, 120-122, 142
codes, Huffman    158, 229
coding style    33, 45, 54-55, 130-131, 155, 177, 214
Coffee Can Problem    42
Collapsing Function Hierarchies    193
collection, garbage    105
Combining Tests    192
common divisors, greatest    17, 209-210
Common Subexpression Elimination    195
Compile-Time Initialization    194
compression, data    104, 109
conceptual blocks    3, 9, 21-26, 92
Condon, J. H.    110
contract, programming by    40
Cormen, T. H.    86
Coroutines    194
correctness proofs    see program verification
cost models    70-72, 75, 89, 92, 107-108, 185-189
Coughran, W. M.    178
counts, word    162-164
Coupon Collector's Problem    204, 224
Cox, R. S.    viii, 28, 54
cumulative arrays    79, 84, 203, 217


data, background    3, 15, 18, 25, 87, 125, 144, 176
data compression    104, 109
data structures    see arrays, bitmaps, dictionaries, hashing, heaps, linked lists, matrices, priority queues, search, sparse arrays, trees, vectors
data structures, sparse    100-104
data transmission    9, 74, 99, 103-104, 215
data types, abstract    27, 29, 130, 133-142, 152-155, 158
databases    4, 9, 24, 28-29, 64, 72, 110, 161
date functions    26, 30, 109, 212
de Saint-Exupery, A.    7
debugging    12-13, 15, 41, 47-50, 54-57, 72, 87, 117-118, 131, 139
Denning, P. J.    vii, 73-75, 216
Dershowitz, N.    213
design, algorithm    vi, 11-20, 62, 64, 77-86, 91, 115-122, 127-129, 131, 149-157
design levels    59, 61-66, 92, 96, 122
design process    7, 17, 31, 64-65, 67, 72, 83, 100, 106, 129, 144, 175
design space    4-5, 108, 123, 127-130, 145, 176
dictionaries    11, 15, 18-20, 26, 31, 109, 144-146, 161-164, 209
difficentralia    167
Dijkstra, E. W.    144
dimension tests    68
displays, seven-segment    31
divide-and-conquer algorithms    62, 79-81, 84-85, 116
divisors, greatest common    17, 209-210
Dobkin, D.    217
domain-specific languages    28-29
Dromey, R. G.    219
Duff, T.    70, 178
Duncan, R.    178
duplicated substring, longest    165-166, 231
dynamic allocation    105


Ecuador    56
Edison, T. A.    18, 212
Einstein, A.    74
elegance    6-7, 9, 14-15, 20, 24-25, 65, 68, 81, 92, 99-100, 118, 127, 145, 157, 161, 169, 176, 216, 225
engineering techniques    see back of the envelope, background data, debugging, design, elegance, problem definition, prototypes, specifications, testing, tradeoffs
English    11, 15, 18-20, 26, 30, 109, 144-146, 161-173
equivalence relations    16
experiments    8, 17, 51-53, 82, 89, 95-96, 98, 116, 119, 121, 137, 162, 164, 185-189, 206, 210, 214, 221, 230
Exploit Algebraic Identities    193-194
Exploit Common Cases    194
exponentiation    43


factors, safety    72-73
Feldman, S. I.    109, 220
Fermi, E.    75
Fermi problems    75
Fibonacci numbers    1-3, 5, 8, 13, 21, 34, 55, 89, 144
fingerprints    16
Floyd, R. W.    129, 143, 225-226
form letters    23-25, 31
forms, canonical    16
Fortran    102
Fraser, A. G.    178
functions, date    26, 30, 109, 212
functions, trigonometric    91


Galloping Gertie    72
garbage collection    105
Gardner, M.    11
Garey, M. R.    vii
genetic traits    91
Gibbon, P.    61
Golden Gate Bridge    183-184
Gordon, P.    viii
graphical user interfaces    28, 55, 106, 202
greatest common divisors    17, 209-210
Grenander, U.    83
Gries, D.    vii, 14, 42-43, 210, 217
Grosse, E. H.    vii-viii


hand waving    14, 16
harness, test    46
hashing    98, 145, 162-164, 171, 181, 201, 207, 221
Hayes, B.    213
heaps    147-159, 228-230
Heapsort    155-159, 180, 204, 229
Hoare, C. A. R.    50, 116, 223
Holmes, S.    168
Homer    166
Hopcroft, J. E.    8, 86, 207
HTML    28
Huff, D.    75
Huffman codes    158, 229
Huffman, D. A.    158, 229
Hume, A. G.    vii
hypertext    27, 29
hyphenation    30


Iliad    166
implicit binary trees    148
infinite loops    48
initialization, vector    8, 207
Insertion Sort    115-116, 121, 179, 214
integer remainders    88
interfaces, graphical user    28, 55, 106, 202
interpreters    24, 106-107, 192
invariants    34-42, 148-157
Inventor's Paradox    29


Jackson, M. A.    9
Jacob, M.    118
Java    45, 54, 123-124, 171, 202, 224
Jelinski, L. W.    vii, 159
Johnson, D. S.    vii, 158
Johnson, S. C.    vii, 31
Jones, A. K.    63
Juno    166


Kadane, J. B.    83
Kentucky legislature    100
Kernighan, B. W.    vii-viii, 3, 15, 26, 55, 76, 105, 107, 159, 171, 178, 187, 213-214, 226
Kernighan, M. D.    viii
key-indexing search    7, 102, 104, 181, 201, 207
King James Bible    162, 230
Knuth, D. E.    3, 16, 34, 72, 96, 123, 126-129, 131-132, 150, 159, 228
Koestler, A.    127
Kolmogorov, A. M.    72


Lagarias, J. C.    213
Lampson, B. W.    66
languages, domain-specific    28-29
languages, programming    see Awk, Basic, C, C++, Cobol, Fortran, Pascal, Smalltalk, Tcl, Visual Basic
laziness    17, 23
Lazy Evaluation    192
legislature, Kentucky    100
Lehman, A. S.    76
Lehman, N. V.    76
Leiserson, C. E.    86
Lemons, E. W.    28, 56
Lesk, M. E.    18
letters, form    23-25, 31
levels, design    59, 61-66, 92, 96, 122
Library, C Standard    19, 122, 177, 205, 219
Library, C++ Standard Template    121-122, 128, 134, 142, 159, 161-162, 164, 172, 177, 197, 205-206, 219, 230
light bulbs    18
Linderman, J. P.    vii-viii, 221
Lindholm, T.    124
linked lists    15, 88, 101, 136-138, 142-143, 145, 198, 226
Lipton, R. J.    217
lists, linked    15, 88, 101, 136-138, 142-143, 145, 198, 226
Little, J. C. R.    73
Little's Law    73-74, 216
lobsters    76
Lomet, D. B.    98
Lomuto, N.    117, 122, 221
longest duplicated substring    165-166, 231
look at the data    see background data
Loop Fusion    193
loop unrolling    91, 94, 192
loops, infinite    48
lower bounds    84-85, 204, 217
Lynn, S.    vii


Macintosh, Apple    107
macros    89, 188
Maguire, S.    50
Mahaney, S. R.    230
maintainability    6-7, 22, 29, 65-66, 87-88, 92, 94, 96, 102, 107, 142
malloc    70, 87, 97, 101, 189, 218-219, 227
managers    59
maps    91, 100
Markov chain    168
Markov text    167-173, 204, 231
Martin, A. R.    viii
Martin, R. L.    vii, 56, 59, 67
matrices    18, 85, 100-105, 182
maximum subsequence problem    77-86
McConnell, S.    v, viii, 31, 55, 98, 214, 216
McCreight, E. M.    158, 229
McIlroy, M. D.    vii-viii, 14, 26, 42, 108, 123, 144-146, 172, 222
McIlroy, P. M.    viii
Melville, R. C.    vii
Memishian, P.    viii, 110
Merge Sort    5-6, 180
Mills, H. D.    14, 210
Minerva    166
Mississippi River    67-70, 74
models, cost    70-72, 75, 89, 92, 107-108, 185-189
monitors    see profilers
monkeys    167
Moore, J S.    85
multiple-pass algorithms    4-5, 7, 207
Munro, J. I.    230
Musser, D. R.    209


name-value pairs    27, 29
Narasimhan, S.    viii
n-body problem    61-63
need for speed    60
needlessly big programs    3, 21-31, 106, 130
new operator    70, 135-143, 155, 185-186, 227
Newell, A.    63
Nievergelt, J.    96
nightspots, popular    73
Nixon, R. M.    144
numbers, prime    103
numbers, random    120, 125-126, 130, 189, 224
numerical algorithms    182


Olympic games    67
Oppenheimer, R.    75
optimization, premature    96
overlaying    105, 156


Packing    192
Pairing Computation    195
pairs, name-value    27, 29
paper bags    127
Paradox, Inventor's    29
Parallelism    194
Parnas, D. L.    27
partitioning functions    116-123, 221
Pascal    214
Passaic River    74, 215
Paulos, J. A.    75
pencils    208
Penzias, A. A.    vii
performance bugs    72, 89, 91, 119
performance requirements    4, 14, 67, 91
Perl    25, 171
permutations    15
Pfalzner, S.    61
phrases    164-173
pigeons    208
Pike, R.    viii, 55, 107, 171, 178, 214, 226
ping    72
Pinkham, R.    76
pipelines    18-20
Plauger, P. J.    3, 15, 26
pointer to a pointer    227
Polya, G.    29, 68, 130
popular nightspots    73
portability    29
postconditions    40
Potter, H.    76
Precompute Logical Functions    193
preconditions    40
premature optimization    96
prime numbers    103
priority queues    152-155, 159, 181, 230
Problem, Coffee Can    42
problem definition    3, 6, 17, 29, 63, 83, 99-100, 125, 127, 129, 144-145, 176
problem, maximum subsequence    77-86
problem, n-body    61-63
problem, substring searching    164
process, design    7, 17, 31, 64-65, 67, 72, 83, 100, 106, 129, 144, 175
profilers    62, 87-88, 96-97, 108-109
program verification    vi, 33-44, 84, 92-95, 117-120, 147-157
programmer time    3, 6, 63, 66, 87-88, 92, 102, 105, 116, 130, 142
programming by contract    40
programming languages    see Awk, Basic, C, C++, Cobol, Fortran, Pascal, Smalltalk, Tcl, Visual Basic
programs, needlessly big    3, 21-31, 106, 130
programs, reliable    7, 65, 73, 215
programs, robust    7-8, 50, 65, 99, 120, 143
programs, secure    7, 50, 65
programs, subtle    14, 34, 81, 94, 116, 120, 127, 144-146
prototypes    6, 17-18, 46-55, 127, 130, 176
pseudocode    34, 45
Public, J. Q.    23


qsort    19, 121-122, 166, 170, 172, 177, 205-206
queues    73
queues, priority    152-155, 159, 181, 230
quick tests    68
Quicksort    4, 116-123, 156, 179, 203, 223
Quito    56


Radix Sort    180, 222
random numbers    120, 125-126, 130, 189, 224
random samples    125
random sets    8, 103, 125-143, 182, 206, 224-228
randomizing algorithms    13, 120
records, variable-length    105
recurrence relations    30, 81, 85
Reddy, D. R.    63
Reingold, E. M.    13, 208, 213
relations, equivalence    16
reliable programs    7, 65, 73, 215
remainders, integer    88
Reordering Tests    193
Report Program Generator    28
requirements, performance    4, 14, 67, 91
retrograde analysis    110
reversal, vector    14
Ricker, M. E.    viii
Ritchie, D. M.    viii, 99, 214
Rivest, R. L.    86
robust programs    7-8, 50, 65, 99, 120, 143
Roebling, J. A.    72-73
roots, square    71, 92, 189
Roper, M. J.    vii
rotation, vector    11, 13-15, 17, 209-211
Roueche, B.    57
Rule of 72    69, 74, 203, 216
rules of thumb    15, 65, 69-70, 74, 96, 125, 130, 176, 178, 214
run time    6, 8, 12, 17-18, 51-55, 59, 62, 70-72, 82, 87-98, 116, 119, 121, 128, 137, 162, 164, 187-189, 206, 210, 214, 221, 230


safety factors    72-73
Saini, A.    209
samples, random    125
Saxe, J. B.    85, 209
scaffolding    45-55, 85, 95
scanning algorithms    81, 84
Scholten, C.    42
Schryer, N. L.    178
search, binary    12-13, 16, 18, 33-55, 92-95, 97-98, 170-172, 181, 201, 203-204, 208-209, 213-214, 219, 230
search, key-indexing    7, 102, 104, 181, 201, 207
search, sequential    12, 18, 43, 90-91, 96, 98, 102, 145-146, 153, 180, 201
search trees, binary    13, 138-140, 164, 171, 181, 198
searching problem, substring    164
secure programs    7, 50, 65
Sedgewick, R.    121-122, 124, 159, 221
selection algorithms    18, 123, 181, 212, 223
Selection Sort    123, 180, 222
sentinels    90, 98, 135-137, 141, 143, 227
sequential search    12, 18, 43, 90-91, 96, 98, 102, 145-146, 153, 180, 201
Sethi, R.    vii-viii, 178
sets, random    8, 103, 125-143, 182, 206, 224-228
seven-segment displays    31
Shamos, M. I.    83, 131
Shannon, C. E.    168, 204
Shell, D. L.    123, 223
Shell Sort    123, 180, 223
Shepherd, A.    129
Short-Circuiting Monotone Functions    193
signatures    15-16
simulations    62, 98, 153
site, web    vi
Skinger, L.    vii
Smalltalk    27
Smith, C. M.    viii
software engineering    see engineering techniques
Sort, Bitmap    5-8, 140-141, 180, 205-207
sort functions, system    3, 7, 19, 72, 115, 121, 211
Sort, Heap    see Heapsort
Sort, Insertion    115-116, 121, 179, 214
Sort, Merge    5-6, 180
Sort, Quick    see Quicksort
Sort, Radix    180, 222
Sort, Selection    123, 180, 222
Sort, Shell    123, 180, 223
Soundex    16
space    see squeezing space
space, design    4-5, 108, 123, 127-130, 145, 176
sparse arrays    8, 100-103
sparse data structures    100-104
specifications    4, 33, 64, 125-126, 133-135, 150-153
speed, need for    60
spots, popular night    73
spreadsheets    28-29
square roots    71, 92, 189
squeezing space    3, 5, 8, 11, 14, 22, 70, 99-111, 128, 144-146, 156
Stanat, D. F.    vii
Standard Library, C    19, 122, 177, 205, 219
Steele, G. L., Jr.    95
Steier, R.    vii
storage allocation    87, 137
Store Precomputed Results    191
string algorithms    15-16, 18-20, 98, 123, 144-146, 161-173, 182, 219, 230-231
Stroustrup, B.    vii
structures, sparse data    100-104
stuff, boring    37-39
substring, longest duplicated    165-166, 231
substring searching problem    164
subtle humor    21
subtle programs    14, 34, 81, 94, 116, 120, 127, 144-146
suffix arrays    165-173
surveys    21, 125
symmetry    14, 26, 36, 38, 80, 93, 103, 105, 110-111, 117, 120, 123, 138-139, 153, 156, 176-177, 201
system sort functions    3, 7, 19, 72, 115, 121, 211
Szymanski, T. G.    viii


table lookup    see search
tables, tax    30, 99-100, 212
Tacoma Narrows Bridge    72
tax tables    30, 99-100, 212
Tcl    27, 54
telephones    3-4, 8, 17, 104-105, 144, 207, 211
termination    37, 39-40, 49-50, 118-119, 202, 213
test harness    46
testing    8, 20, 22, 33, 41, 46-54, 65, 72, 87, 103
tests, quick    68
text, Markov    167-173, 204, 231
Thompson, K. L.    15, 99, 110-111
time, programmer    3, 6, 63, 66, 87-88, 92, 102, 105, 116, 130, 142
time, run    6, 8, 12, 17-18, 51-55, 59, 62, 70-72, 82, 87-98, 116, 119, 121, 128, 137, 162, 164, 187-189, 206, 210, 214, 221, 230
Toyama, K.    viii
tradeoffs    7-8, 103, 105, 108, 153, 176, 221
Transfer-Driven Loop Unrolling    193
Transformations on Recursive Functions    194
transmission, data    9, 74, 99, 103-104, 215
trees    13, 62
trees, binary    62, 147
trees, binary search    13, 138-140, 164, 171, 181, 198
trees, implicit binary    148
Trickey, H.    viii
trigonometric functions    91
turnpikes    85


Ullman, J. D.    8, 18, 86, 207
Ulysses    166
Unconditional Branch Removal    193
Unix system    99, 107, 176
unrolling, loop    91, 94, 192
user interfaces, graphical    28, 55, 106, 202


Van Wyk, C. J.    vii-viii, 87-88, 96-97, 124, 143, 187, 218
variable-length records    105
vector algorithms    182
vector initialization    8, 207
vector reversal    14
vector rotation    11, 13-15, 17, 209-211
vectors    see arrays
verification, program    vi, 33-44, 84, 92-95, 117-120, 147-157
Visual Basic    25, 27-28, 54
voice synthesizer    26
Vyssotsky, V. A.    vii, 18, 72-73, 95, 131, 178, 201


waving, hand    14, 16
web site    vi
Weide, B. W.    73
Weil, R. R.    8, 12
Weinberger, P. J.    68, 159, 213
West Point    vii, 127
wine cellars    74
Wolitzky, J. I.    75
word counts    162-164
words    15, 18-20, 161-164
Woronow, A.    129
Wright, M. H.    91
Wulf, W. A.    215


Yeager, C.    6


Zave, P.    vii, 130

Copyright © 1999 Lucent Technologies. All rights reserved. Fri 3 Sep 1999