Historical notes and further reading

Historical notes and further reading

Chapters 1 and 2

The classical book on the theory of numbers is

$G$. H. Hardy and E. M. Wright, Introduction to the Theory of Numbers. Oxford University Press, 1980.

The primality algorithm was discovered by Robert Solovay and Volker Strassen in the mid-1970’s, while the RSA cryptosystem came about a couple of years later. See

D. R. Stinson, Cryptography: Theory and Practice. Chapman and Hall, 2005.

for much more on cryptography. For randomized algorithms, see

$R$. Motwani and P. Raghavan, Randomized Algorithms. Cambridge University Press, 1995.

Universal hash functions were proposed in 1979 by Larry Carter and Mark Wegman. The fast matrix multiplication algorithm is due to Volker Strassen (1969). Also due to Strassen, with Arnold Schonhage¨ , is the fastest known algorithm for integer multiplication: it uses a variant of the FFT to multiply n-bit integers in O(n log n log log n) bit operations.

Chapter 3

Depth-first search and its many applications were articulated by John Hopcroft and Bob Tarjan in 1973—they were honored for this contribution by the Turing award, the highest distinction in Computer Science. The two-phase algorithm for finding strongly connected compo nents is due to Rao Kosaraju.

Chapters 4 and 5

Dijkstra’s algorithm was discovered in 1959 by Edsger Dijkstra (1930-2002), while the first algorithm for computing minimum spanning trees can be traced back to a 1926 paper by the Czech mathematician Otakar Boruvka. The analysis of the union-find data structure (which is actually a little more tight than our log∗ n bound) is due to Bob Tarjan. Finally, David Huffman discovered in 1952, while a graduate student, the encoding algorithm that bears his name.

Chapter 7

The simplex method was discovered in 1947 by George Danzig (1914-2005), and the min-max theorem for zero-sum games in 1928 by John von Neumann (who is also considered the father of the computer). A very nice book on linear programming is

$V$. Chvatal, ´ Linear Programming. W. H. Freeman, 1983.

And for game theory, see

Martin J. Osborne and Ariel Rubinstein, A course in game theory. M.I.T. Press, 1994.

Chapters 8 and 9

The notion of NP-completeness was first identified in the work of Steve Cook, who proved in 1971 that SAT is NP-complete; a year later Dick Karp came up with a list of 23 NP-complete problems (including all the ones proven so in Chapter 8), establishing beyond doubt the applicability of the concept (they were both given the Turing award). Leonid Levin, working in the Soviet Union, independently proved a similar theorem.

For an excellent treatment of NP-completeness see

$M$. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman, 1979.

And for the more general subject of Complexity see

C. H. Papadimitriou, Computational Complexity. Addison-Wesley, Reading Massachusetts, 1995.

Chapter 10

The quantum algorithm for primality was discovered in 1994 by Peter Shor. For a novel introduction to quantum mechanics for computer scientists see

http://www.cs.berkeley.edu/ vazirani/quantumphysics.html

and for an introduction to quantum computation see the notes for the course “Qubits, Quantum Mechanics, and Computers” at

http://www.cs.berkeley.edu/ vazirani/cs191.html