Insights and Algorithms

• S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: Algorithms
• Steven S. Skiena: The Algorithm Design Manual and the Stony Brook Algorithm Repository

Who is the Hardest One of All? NP-Completeness

• Wikipedia: List of NP-complete problems

The Deep Questions: P vs. NP

• Gerhard Woeginger's P vs NP page
• Letter from Gödel to von Neumann

Grand Unified Theory of Computation

• Computability and Complexity from the Stanford Encyclopedia of Philosophy
• The Analytical Engine: John Walker's collection of writings on Charles Babbage's computing machinery
• Alan Turing's 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem
• Alexander Sakharov's resource center for the foundations of Mathematics
• David Keenan's To dissect a mockingbird: a graphical notation for the lambda calculus with animated reduction
• Wikipedia: Wang tiles
• Lance Fortnow on the strong Church-Turing thesis
• Unconventional computation Conference 2007
• for those who enjoy really unconventional models of computation: Mark Chu-Carroll's blog on pathological programming

Simply the Best: Optimization

• Compendium of NP-hard optimization problems
• TSP pages at Georgia Tech
• Daniel Spielman's smoothed analysis page

Random Walks and Rapid Mixing

• Wilfrid Kendall's perfect simulation, including his beautiful dead leaf applet
• David B. Wilson's website on perfect sampling

References

• The Turing Digital Archive
• List of important publications in computer science
• Tommaso Toffoli's quantum computation archive