Index

To look up algorithms, see also Appendix 1 (A Catalog of Algorithms). To look up code-tuning techniques, see also Appendix 4 (Rules for Code Tuning).

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

datatypes, 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, Tel, 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, Tel, 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

Roueché, 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

Tel 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