Pattern recognition (chapter 6). Bishop's lectures (see above) have some interesting material that nicely complements this chapter. The geographical data about political donations is taken from the Fundrace project of the Huffington Post. All the handwritten digit data is taken from a dataset provided by Yann LeCun, of New York University's Courant Institute, and his collaborators. Details of the dataset, which is known as the MNIST data, are discussed in the 1998 paper by LeCun et al., “Gradient-Based Learning Applied to Document Recognition.” The web spam results come from Ntoulas et al., “Detecting Spam Web Pages through Content Analysis,” published in the Proceedings of the World Wide Web Conference, 2006. The face database was created in the 1990s by a leading pattern recognition researcher, Tom Mitchell of Carnegie Mellon University. Mitchell has used this database in his classes at Carnegie Mellon and describes it in his influential book, Machine Learning. On the website accompanying his book, Mitchell provides a computer program to perform training and classification of neural networks on the face database. All the results for the sunglasses problem were generated using slightly modified versions of this program. Daniel Crevier gives an interesting account of the Dartmouth AI conference in AI: The Tumultuous History of the Search for Artificial Intelligence. The excerpt from the conference's funding proposal (on page 103) is quoted in Pamela McCorduck's 1979 book, Machines Who Think.
Compression (chapter 7). The story about Fano, Shannon, and the discovery of Huffman coding is taken from a 1989 interview of Fano by Arthur Norberg. The interview is available from the oral history archive of the Charles Babbage Institute. My favorite treatment of data compression is in Information Theory, Inference, and Learning Algorithms, by David MacKay, but this book requires college-level math. Dewdney's book (see above) contains a much briefer and more accessible discussion.
Databases (chapter 8). There is an over-abundance of books providing an introduction to databases for beginners, but they typically explain how to use databases, rather than explaining how databases work—which was the objective of this chapter. Even college-level textbooks tend to focus on the use of databases. One exception is the second half of Database Systems, by Garcia-Molina, Ullman, and Widom, which gives plenty of details on the topics covered in this chapter.
Digital signatures (chapter 9). Gail Grant's Understanding Digital Signatures provides a great deal of information about digital signatures and is reasonably accessible to those without a computer science background.
Computability (chapter 10). The chapter's opening quotation is from a talk given by Richard Feynman at Caltech on December 29,1959. The title of the talk is “There's Plenty of Room at the Bottom,” and it was later published in Caltech's Engineering & Science magazine (February 1960). One unconventional, but very interesting, presentation of the concepts surrounding computability and undecidability is in the form of a (fictional) novel: Turing (A Novel about Computation), by Christos Papadimitriou.
Conclusion (chapter 11). The Stephen Hawking lecture, “The Future of the Universe,” was the 1991 Darwin lecture given at the University of Cambridge, also reprinted in Hawking's book Black Holes and Baby Universes. The televised A. J. P. Taylor lecture series was entitled How Wars Begin, and was also published as a book in 1977.
INDEX
The index that appeared in the print version of this title does not match the pages in your eBook. Please use the search function on your eReading device to search for terms of interest. For your reference, the terms that appear in the print index are listed below.
AAC
abort. See transaction addition
algorithm
addition trick
Adleman, Leonard
Advanced Encryption Standard
advertisement
AES. See Advanced Encryption Standard
AI. See artificial intelligence
algorithm: books on; criteria for greatness; definition of; future of; lack of; relationship to programming; significance of. See also addition algorithm; checksum; compression; digital signature; error-correcting code; Dijkstra's shortest-path algorithm; Euclid's algorithm; factorization; JPEG; key exchange; LZ77; matching; nine algorithms; PageRank; public key; ranking; RSA; web search
AltaVista
AlwaysYes.exe
Amazon
Analytical
Engine
AntiCrashOnSelf.exe
AntiYesOnSelf.exe
Apple
artifact. See compression
artificial intelligence. See also pattern recognition
artificial neural network. See neural network As We May Think
astronomy
Atlantic magazine
atomic. See transaction audio. See also
compression Austen, Jane
authentication
authority: score; of a web page. See also certification authority
authority trick
B-tree
Babylonia
backup
bank; account number; balance; for keys; online banking; for signatures; transfer; as trusted third party
base, in exponentiation
Battelle, John
Bell Telephone Company
binary
Bing
biology
biometric sensor
Bishop, Christopher
bit
block cipher
body, of a web page
brain
Brin, Sergey
British government
browser
brute force
bug
Burrows, Mike
Bush, Vannevar
Businessweek
Byzantine fault tolerance
C++ programming language
CA. See certification authority calculus
Caltech
Cambridge
CanCrash.exe
CanCrashWeird.exe
Carnegie Mellon University
CD
cell phone. See phone certificate
certification authority
Charles Babbage Institute
chat-bot
checkbook
checksum; in practice; simple; staircase. See also cryptographic hash function
checksum trick
chemistry
chess
Church, Alonzo
Church-Turing thesis
citations
class
classification
classifier
clock arithmetic
clock size; conditions on; factorization of; need for large; primary; as a public number; in RSA; secondary
Codd, E. F.
code word
commit phase
compact disk. See CD compression; via AAC (see AAC); artifact; of audio or music; history of; of images; via JPEG (see JPEG); lossless; lossy; via MP3 (see MP3); relation to error-correcting code; uses of; of video
computable: number; problem. See also uncomputable
computer: 1980s and ‘90s; accuracy requirement of; appreciation of; classical; compared to humans; early; error (see also error-correcting code; error detection); first electronic; fundamental jobs of; human calculator; intelligent (see artificial intelligence); laptop (see laptop); limitations on; mechanical; modern; quantum (see quantum computing); router (see router); server (see server); users. See also hardware
computer program; analyzing another program; executable; impossible; input and output; intelligent; programmers; programming; programming languages; verification; world's first programmer; yes-no
computer programming. See computer program
computer science; beauty in; certainty in; curriculum; founding of; in high school; introductory teaching; popularity of; predictions about; public perception of; research; in society; theory of; undecidable problems in
Computing Machinery and
Intelligence
concurrency
consciousness
consistency. See also inconsistency
&nb
sp; contradiction. See proof by contradiction
Cormen, Thomas
cosmology
Covenant Woman
CPU
crash; intentional
Crashing Problem
CrashOnSelf.exe, CRC32
credit card
Crevier, Daniel
Croft, Bruce
cryptographic hash function
cryptography; public key (see public key cryptography) cuneiform
cycle
Dartmouth AI conference
Dasgupta, Sanjoy
data center
database; column; definition of; geographically replicated; of faces; relational; replicated; row; table. See also virtual table
deadlock
decision tree
decrypt
Deep Blue
Democrat
Dewdney, A. K.
Dickens, Charles
Diffie, Whitfield
Diffie-Hellman. See key exchange
digital signature; applications of; connection to cryptography; detect forgery of; of long messages; in practice; security of. See also RSA; signature
Dijkstra's shortest-path algorithm
discrete exponentiation
discrete logarithm
disk. See hard disk distributed hash table
double-click
Doyle, Arthur Conan
drive. See hard disk DVD
Dylan, Bob
eBay
e-commerce
Elgin, Ben
e-mail
Emma
encrypt; 128-bit encryption
engineering
Entscheidungsproblem
error detection
error-correcting code; relation to compression
Essay Concerning Human
Understanding
Ethernet
Euclid
Euclid's algorithm
excitatory
exponent
exponentiation. See also discrete exponentiation; power notation
extension. See file name extension
face database. See database
face recognition
Facebook
factorization
Fano, Robert
Faraday, Michael fault-tolerance
fax
Feldman, Yishai
Fetterly, Dennis
Feynman, Richard
file name extension;
unhide
financial information
finite field algebra
flash memory. See memory
forgery. See also digital signature
freeze
Freeze.exe
Fundrace project
garage
Garcia-Molina, Hector
GCHQ
genetics
GeoTrust
GlobalSign
Google
Grant, Gail
Gray, Jim
Great American Music Hall
hacker
halt. See terminate
halting problem
Hamming, Richard
Hamming code
handwriting recognition
hard disk; failure; operation; space
hardware; failures of
Hardy, G. H.
Harel, David
hash tables
Hawking, Stephen
haystack
Hellman, Martin
Hewlett, Dave
Hewlett-Packard
hidden files
high-definition
hit, for web search query
Holmes, Sherlock
Hromkovc, Juraj
HTML
http
https
Huffington Post
Huffman, David
Huffman coding
hyperlink; cycle of (see cycle); incoming
hyperlink trick
IBM
ICT
idempotent
incoming link. See hyperlink
Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers Page 23
