Design and Analysis of Algorithms

Links

Set Theory and Logic

• Basic notation and terminology for set theory
• Elementary Boolean Logic (part of a larger page "factasia" on logic)

History of Computing

• For a history of computers from the early calculating machines of Pascal to the design of the von Neumann computer, see Herman Goldstine's excellent The Computer from Pascal to von Neumann.
• There are many books about Charles Babbage and his difference and analytical engines that foreshadow the von Neumann computer. Doron Swade's account of the London's Science Museums effort to actually build parts of the difference engine makes suspenseful reading, and offers many insights into Babbage's thinking.

Limits of Computation

• Kurt Gödel published his famous incompleteness theorem in 1931. Several years later, Alan Turing developed his theoretical model of computation (the Turing machine) and recast the incompleteness theorem, showing that the halting problem is undecidable. For a history of the impact of Gödel's theorem on mathematics, see Kline's "Mathematics. The Loss of Certainty".
• Popular accounts of Gödel's theorem can be found in several of Raymond Smullyan's books ("Lady or Tiger", and "Forever Undecided"), and Douglas Hofstaedter's "Goedel, Escher, Bach". Also check out Rucker's "Infinity and the Mind" which is fun reading, and makes connections to philosophy and cognitive science. It contains a full proof of Gödel's theorem. Another readable account of Gödel's theorem is by Nagel and Newman.
• Andrew Hodges' account of Turing's life also contains explanations of Turing's technical contributions to computer science. Ag good introduction to computability theory is Martin Davis's book on "Computability and Unsolvability".
• In Neil Stephenson's science fiction novel "Cryptonomicon" Alan Turing makes an appearance as a character, and an amazing number of technical details, about Turing's work on descrypting the German Enigma machine during the second world war are explained.

Algorithms

• Cormen, Leiserson, Rivest, Stone is the standard textbook for an algorithms course.
• The standard reference, however, is Donald Knuth's "The Art of Computer Programming".