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
Copyright © 1999
Lucent Technologies. All rights reserved.
Fri 3 Sep 1999
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