Index

Θ, 442
Ω, 442

abstract data types, 387
Ackermann, Wilhelm, 51, 179
Adleman, Len, xxii, 463
Advanced Research Projects Agency (ARPA), 201, 225, 252, 373
Aiken, Howard Hathaway, xviii, 61, 99, 107, 147, 169, 192, 307, 399
al-Kwarizmi, xvi
Albert (Prince Consort), xvii
ALGOL, xiv, xx, 209, 213, 222, 231, 281, 282, 292, 297, 305, 306, 447
analog computer, 107
analytical engine, 9, 150, 157
Apple Computer, 357
Aristotle, xvi, 1, 5, 7, 27, 450
ARITH-MATIC, 170
ARPA, see Advanced Research Projects Agency (ARPA)
ARPANET, 201, 373, 407
Art of Computer Programming, The, 441
artificial intelligence, 147, 183, 203, 213, 268, 271
As We May Think, xxi, 107, 225
Atanasoff, John Vincent, xviii
Austin, University of Texas at, 267
Automatic Calculating Engine, xviii, 89, 147
Automatic Sequence Controlled Calculator, 61

Babbage, Charles, xvi, 9, 27, 61, 63, 109, 150, 157, 170
Backus, John, xiv, 237
Baran, Paul, 373
BBN, 201, 373
Begriffsschrift, 45
Belfast, Queen’s University in, 298
Bell Helicopter Company, 252
Bell Labs, 112, 121, 135, 180, 212, 238, 357
Berkeley, University of California at, 308, 333, 349, 422
binary, xviii, 5, 71, 89, 98, 121
bit, xviii, 121, 122, 188
Bletchley Park, 147, 307
Boggs, David R., 407
Bolt Beranek and Newman (BBN), 201, 373
Boole, George, xvi, xviii, xix, 27, 71, 135
boolean logic, 27, 72, 349
Borůvka, Otakar, 179
Boston University, 334
Bronx High School of Science, 183
Brooks, Frederick C., xxii, 321, 399
Brooks’s Law, 406
bug, 169
Burks, Arthur, 89, 165
Bush, Vannevar, xxi, 6, 107, 191, 225, 307
Butler, Samuel, xix, 193
Byron, George Gordon (Lord Byron), 9

California Institute of Technology, 213, 441
Cambridge, University of, 9, 53, 147, 150, 165, 339
Cantor, Georg, xvii, 51
Cerf, Vinton, xxii, 373
channel, 424
Cheatham, Thomas E., Jr., vi, 399
Chicago, University of, 80
Chomsky, Noam, xiv
chosen plaintext attack, 427
chromatic number, 354
Church, Alonzo, xiv, xvii, xx, 51, 53, 87, 153, 213, 217, 307
ciphertext, 425
ciphertext only attack, 427
circuits, integrated, 261
circuits, series-parallel, 72
Clarke, Edmund, 447
clique, 353
clock, 79, 91, 96, 102, 241, 242, 283, 285, 291
Cobham, Alan, 179, 333
COBOL, xiv, xx, 170, 231, 305, 460
Codd, Edgar F., xxii, 307
Compatible Time-Sharing System, 238, 357
compiler, 169, 441
computable number, 53
concurrency, xxi, 267
Cook, Stephen A., xxi, 333, 349
Cook–Levin Theorem, 334
Corbató, Fernando, xxii, 237
Cork, Queen’s College in, 28
Cornell University, 183
critical section, 267, 287
cryptography, xxii, 421, 463
CTSS, 238
cybernetics, 191

Daggett, Marjorie Merwin, 237
Daley, Robert C., 237
Dartmouth College, 213
database, 307
Davies, Donald, 373
Davis, Martin, 46
Davis–Putnam procedure, 337, 338
De Morgan, Augustus, 27
De Morgan’s laws, 27, 75, 77, 336
deadly embrace, 288
debugging, 165, 169, 239, 281, 297, 304, 402
DEC, 201, 358, 373
DeMillo, Richard, xxii, 447
difference engine, 9
differential analyzer, 107, 158
Diffie, Whitfield, xxii, 421, 463
Digital Equipment Corporation (DEC), 201, 358, 373
digital signatures, 421
Dijkstra, Edsger, xxi, xxii, 180, 267, 279, 289, 321, 387
diophantine equation, xvi, 46, 50
discrete logarithm, 422
documentation, 305, 325
dynamic programming, 180

Eckert, Presper, xvii, 89
Eckert–Mauchly Computer Corporation, 90, 169, 170
Edmonds, Jack, xxi, 179, 333, 351
EDSAC, 165
EDVAC, xvii, 89, 121, 136, 147, 165, 251
Eindhoven, Technological University in, 267, 279
ELIZA, xx, 147, 271
Elizabeth II (Queen), 53
Emerson, E. Allen, 447
Engelbart, Douglas C., xxi, 225
ENIAC, xvii, 89
entropy, 121
Entscheidungsproblem, xvii, xx, 46, 51, 60, 213, 421
error correcting code, xviii, 138
error detecting code, xviii, 138
Ethernet, xxii, 407
exact cover, 354
exponential backoff, 416
exponential growth, 261
exponential time, 333

factoring, 463
feedback arc set, 354
feedback node set, 353
Fermat, Pierre de, 47, 449, 469
Ferranti Mark 1, 165
Floyd, Robert, xiv, 180, 297
FORTRAN, xiv, xx, 209, 222, 237, 242, 305
Frege, Gottlob, 45

gateway, 376
Gauss, Carl Friedrich, 463
Gaussian elimination, 293
GCHQ, xxii, 422
Georgia Institute of Technology, 448
GNU, 357
go to statement, 289, 387
Gödel, Kurt, xvii, 46, 51, 60, 153
Goldstine, Herman, 89, 165
Göttingen, University of, 45
graph isomorphism, 356
graphics, computer, 201, 251, 399
Gray, Jim, xiv
greedy algorithm, 180

Hamiltonian circuit, 180, 350, 354
Hamming, Richard W., xviii, 135
Hamming code, 135
Hardy, G. H., 422, 443–446, 449, 452, 457
Harvard architecture, 62
Harvard University, xviii, 61, 107, 169, 191, 201, 333, 349, 357, 399, 407
hashing, 441
Hawking, Stephen, 9
Hellman, Martin, xxii, 421, 463
Hilbert, David, xvii, 45, 51, 90, 213, 421, 448
hitting set, 354
Hoare, C. A. R., xxi, 292, 297
Hobbes, Thomas, xix
Homer, xix
Hopper, Grace Murray, xx, 169, 237, 307
Huffman code, 121

IBM, see International Business Machines Corporation (IBM)
imitation game, 148
IMS, 307
indexing, xxii, 107, 116, 117, 309, 339
information theory, 121, 424
Ingres, 308
integer programming, 353
integrated circuit, 262
Intel Corporation, 261
International Business Machines Corporation (IBM), xviii, 61, 68–70, 99, 165, 183, 201, 203, 213, 214, 218, 237, 238, 241, 249, 272, 307, 349, 373, 387, 399, 408, 466, 472
internet, xxii, 201, 373
inverse document frequency, 339
IP, 373

Jarník, Vojtěch, 180
Jevons, William, 27, 463
job sequencing, 355

Kahn, Robert, xxii, 373
Karp, Richard, xxi, 180, 349, 439
key (cryptography), 421
key (database), 314
Kleene, Stephen Cole, xiv, 80, 87, 153
knapsack, 354, 422, 439, 440
known plaintext attack, 427
Knuth, Donald E., xxi, 179, 289, 441
Kruskal, Clyde, 180
Kruskal, Joseph B., Jr., xxi, 179, 333
Kruskal, Martin David, 180
Kruskal, William, 180
al-Kwarizmi, xvi

lambda-calculus, xx, 51, 87, 213
Lamport, Leslie, xiv
Lampson, Butler, xiv
Lawler, Eugene, 351
Laws of Thought, The, xviii, 27, 135
Leibniz, Gottfried Wilhelm, xvi, xix, 5, 45, 62, 109, 170, 442
Levin, Leonid, 334
Licklider, J. C. R., xxi, 201, 225, 237, 252, 373
light pen, 251
linear equations, 293
linear inequalities, 350, 356
Linux, 357
Lipton, Richard, xxii, 447
Liskov, Barbara, xxii, 387
LISP, xx, 51, 213
logic, xv, xxi, 5, 27, 50, 60, 72, 183, 297, 333
logic piano, 27, 463
Lovelace, Ada Augusta, xvii, xix, 9, 61, 157
Ludolph of Cologne, 7

machine learning, 161, 183, 195
man-month, 402
Manchester, University of, 147, 150, 159, 165
Manchester “Baby”, xviii
Manhattan Project, 90, 107, 135
Mark 1 (Manchester), 147, 150, 159, 165
Mark I (Harvard), xviii, 61, 91, 107, 147, 169, 307
Massachusetts Institute of Technology, xxi, 71, 80, 107, 121, 183, 191, 201, 213, 237, 251, 271, 357, 387, 407, 463
matching, 354
MATH-MATIC, 170
Matiyasevich, Yuri, 46
matrix multiplication, 293
Mauchly, John W., xvii, 89, 170
max cut, 355
McCarthy, John, xx, 213, 237, 238, 387
McCarthy, Joseph (Senator), 192
McCulloch, Warren, xix, 6, 79, 90, 97, 191, 213
memex, 117
Menabrea, Luigi, 9
Merkle, Ralph, xxii, 421
METAFONT, 442
Metcalfe, Robert, xxii, 407
microcode, xx, 165
microfilm, 107
Millennium Prize problems, 45
minimum cut, 351
Minsky, Marvin, 183, 213
MIT, see Massachusetts Institute of Technology
model-checking, 447
Moore, Gordon, xx, 261
Moore School, 89, 147, 165, 169
Moore’s Law, xx, 261
Morgenstern, Oskar, 194
Morland, Samuel, 62
mother of all demos, 225
MULTICS, 238, 357
multiprogramming, 280
mutual exclusion, 267, 287
My Fair Lady, 271
Mythical Man-Month, The, 399

Napier, John, 62
National Science Foundation, 107
network, 373, 407
neuron, 79, 185
Newell, Allen, xiv, 203, 214
Newton, Isaac, xvi, 9
node cover, 353
nondeterministic Turing machine, 334, 352
normal form, 313
Noyce, Robert, 261
𝒩𝒫, xxi, 333, 349, 442
𝒩𝒫-complete, 180, 338, 353, 440

O-notation, 442
object-oriented programming, 387
one time pad, 424
one-way authentication, 432
one-way function, 433
operating system, 237, 279, 357
oracle, 335
Oracle Corporation, 308
Oxford, University of, 298

𝒫, xxi, 334, 349, 442
packet, 374, 407
Papert, Seymour, 183
parity code, 136
partititon, 355
Pascal (programming language), 289
Pascal, Blaise, xvi, 5, 10, 62, 170
Paterson, Michael, 443
Peacock, George, 27
Peirce, Charles Sanders, 71
Pennsylvania, University of, xviii, 89, 147, 165, 169
perceptron, xix, 183
Perlis, Alan, xxii, 222, 447
Péter, Rósza, xx
Pitts, Walter, xix, 6, 79, 90, 97, 191, 213
plaintext, 425
polynomial time, 333, 350
Post, Emil, 52
predicate, 1, 214
predicate calculus, 51, 308, 317
Prim, Robert Clay, 180
prime number, 48, 49, 51, 335, 356, 443, 451, 464, 469, 471, 477
Princeton University, xxi, 53, 90, 180
Principia Mathematica, xix, 45, 51, 60, 80, 448, 450
Prior Analytics, 1, 27
projection, 319
proof, 60, 297, 333, 447
propositional logic, 28, 74
protocol, xxii, 374
public key, 421, 463
Putnam, Hilary, 46
Pygmalion, 271

Quicksort, 297

Rabin, Michael, xiv, xxi, 451
reducible, 335, 349
relational model, xxii, 307
Relational Technology Inc., 308
Remington Rand, 169
Ritchie, Dennis, xxii, 357
Rivest, Ronald, xxii, 463
Roberts, Lawrence “Larry”, 373
Robinson, Julia, 46
Rochester, Nathaniel, 213
Rosenblatt, Frank, xix, 183
Royce, Winston, xxii, 321
RSA, xxii, 463
Russell, Bertrand, 45, 80, 195, 448

satisfiability, 333, 351
Science, the Endless Frontier, 107
Scott, Dana, xiv, xxi
semaphore, 286
set cover, 353
set packing, 353
Shamir, Adi, xxii, 422, 463, 475
Shannon, Claude, xvii, xviii, 71, 107, 121, 135, 213, 251, 421
Shaw, George Bernard, 271
Shaw, John, 203
Shor, Peter, xxii
shortest paths, 267, 351
Sifakis, Joseph, 447
Simon, Herbert, xv, 203
Sketchpad, 251
software crisis, 387
software engineering, xxii, 321, 399
Southern California, University of, 464
spanning tree, 179, 333, 351
Spärck Jones, Karen, xxii, 339
Sputnik, 373
SQL, 308
SRI, 225
Stallman, Richard, 357
Stanford University, 183, 213, 387, 441
Steiner tree, 354
Stonebraker, Michael, 308
Strassen, Volker, xxi, 293
structured programming, 289, 387
subgraph, 335
subroutine, 172
Sutherland, Ivan E., vi, xxi, 251
syllogism, 2
System R, 308
System/360, 165, 399

Tandem Computers, 308
Tarjan, Robert, xiv, 179, 351, 443
tautology, 334
Taylor, Robert, 373
TCP, 373
testing, 304, 321, 404
TE X, 442
Thompson, Ken, xxii, 238, 357
time-sharing, 237, 271, 357
Toronto, University of, 333
Torvalds, Linus, 357
transistor, xx, 232, 251, 257, 258, 261, 262, 264
trap door, 437, 465
traveling salesman problem, 179
Truman, Harry S., 107
Tufts University, 191
Tukey, John, 121
tuple, 308
Turing, Alan Mathison, xvii, xix, xxi, 46, 51, 89, 147, 307, 421
Turing machine, 52, 334, 350
Turing test, 147
TX-2 computer, 251, 261

UNISYS, 169
UNIVAC, 170
UNIX, xxii, 238, 357

vacuum tube, xvii, 64, 91, 96–102, 109, 115, 191, 261
Venn, John, 27
verification, xxi, 297, 447
Victoria (Queen), xvii, 28
Vocoder, 112, 123
von Neumann, John, xvii, 89, 135, 165, 194
von Neumann architecture, xviii, 89

Wang, Hao, 333
Warshall, Stephen, 180
waterfall model, 321
Watson, Thomas, Jr., 399
Weizenbaum, Joseph, xx, 147, 271
Weizmann Institute, 464
Wells, H. G., 107
Whitehead, Albert North, 45, 80
Wiener, Norbert, xx, 80, 191, 454
Wilder, Thornton, vii
Wilkes, Maurice V., xx, 165, 170, 175
Wirth, Niklaus, 289
World War II, xv, xxi, 46, 53, 61, 90, 107, 169, 206, 225, 428

Xerox Palo Alto Research Center (PARC), 407

Yale University, 169, 447

Zilles, Stephen, 387