First, "theoretical computer science" means different things to different people. I think for most users on this site, a historical caricature (which reflects some modern sociological tendencies) is that there is "Theory A" and "Theory B" (with no implied order relation between them): Theory A consists of the theory of algorithms, complexity theory, ...
It really makes a difference what the input to the algorithm is: how do you specify a group?
If you want groups given by generators and relators, I would suggest Combinatorial Group Theory, by Magnus, Karrass, and Solitar (but algorithms there are sparse because too many of the important problems are undecidable).
If you want automatic groups (groups whose ...
After clarifying the (unclear for me) meaning of "popular science" (thanks Sasho :-) I propose:
Title: Winning Ways for Your Mathematical Plays (4 volumes)
Authors: Elwyn R. Berlekamp, John H. Conway, Richard K. Guy
Description: it can be considered a compendium of information on mathematical games (tons of games are analyzed: coin and paper-and-pencil ...
Scott Aaronson's Quantum Computing Since Democritus. This book is an excellent introduction to theoretical computer science and quantum computing for layman as well as begining students of theoretical computer science. Unlike other pop science books this book is rigorous as well.
"Descriptive Complexity, Canonisation, and Definable Graph Structure Theory," by Martin Grohe. Date on manuscript: March 7, 2013. Available at: http://www.automata.rwth-aachen.de/~grohe/pub.en. (Link Broken)
Eyal Kushilevitz and Noam Nisan, "Communication Complexity", 2006.
Stasys Jukna, "Boolean Function Complexity: Advances and Frontiers", 2012. (Part II of the book is dedicated to Communication Complexity.)
Alexander Razborov, "Communication Complexity".
Toni Pitassi, "Communication Complexity, Information Complexity and ...
"Foundations of Data Science" (pdf) by Hopcroft and Kannan. The text was discussed by Lipton on his blog. As the title implies, the emphasis of the text seems to be applications and issues related to Big Data and Learning problems. It seems to have grown out of this course.
(Update 8/2015) The book now has a third author, Avrim Blum. The pdf link has ...
"Logic and Discrete Mathematics for Computer Scientists", by James Caldwell. Manuscript Date: August 22, 2011. Available at: http://www.cs.uwyo.edu/~jlc/courses/2300/book.pdf.
"Data Structures and Algorithms, The Basic Toolbox", by Kurt Mehlhorn. Manuscript Date: August 2008. Available at: http://www.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/.
"An Introduction ...
Notes or books about Distributed Algorithms:
"A Course on Deterministic Distributed Algorithms" by Jukka Suomela. Available at http://www.cs.helsinki.fi/u/josuomel/dda/dda-print.pdf
"Principles of Distributed Computing" by Roger Wattenhofer. Available at http://dcg.ethz.ch/lectures/podc_allstars/lecture/podc.pdf
There are several ways to learn about type theory. For a working programmer,
Types and Programming Languages by B. Pierce is a good start.
Practical Foundations for Programming Languages by R. Harper might also be good. If you want a bit of easy to read background on operational semantics,
I recommend G. Winskel's, The Formal Semantics of Programming ...
It's a wide field with a few quite different areas.
I'd start with some of the most fundamental ideas about what computers are: Hopcroft and Ullman, "Introduction to Automata Theory, Languages and Computation."
The reason I'd recommend that in particular, is their emphasis on proofs. They guide you through a rigorous way of thinking. That's the difference ...
At the intersection of evolutionary biology and theoretical computer science there are two recent books.
Valiant's "Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World", and
Chaitin's "Proving Darwin: Making Biology Mathematical".
Both books look at evolution through the algorithmic lens, with the first ...
I first got interested in TCS after reading Scott Aaronson's writings; one of the earlier ones was Who Can Name the Bigger Number?, which does have a pop-science feel to it
Another very good one I read later is Why Philosophers Should Care About Computational Complexity; although written in an academic style I would say it is "popular science" in that its ...
Devdatt Dubhashi and Alessandro Panconesi: Concentration of Measure for the Analysis of Randomised Algorithms. A first draft is available at http://wwwusers.di.uniroma1.it/~ale/Papers/master.pdf (via geomblog)
IMHO, I would recommend these "popular" books:
Any book by James Gleick - Chaos, The Information
Fire in the Valley, for an account of early PC history
Books by Steven Levy: Insanely Great, In the Plex, Hackers, etc.
And the grand master, though somewhat dated:
The Soul of a New Machine by Tracy Kidder
The Design of Approximation Algorithms by Williamson & Shmoys (http://www.designofapproxalgs.com/) is a great book for many approximation methods such as greedy algorithms, semidefinite programming, etc. Also, it covers some topics within complexity that are closely related to approximation algorithms (inapproximability, Unique Games-based hardness of ...
The most modern and comprehensive reference is probably "Handbook of Computational Group Theory" by Holt, Eick and O'Brien (link)
A classic reference is "Computation in Finitely Presented Groups" by Charles Simms.
If you're interested in the group theory that's relevant for Graph Isomorphism, then in addition to Seress's book that David Eppstein mentioned, I would highly recommend
Dixon and Mortimer's Permutation Groups
The above is a book on "just" group theory, but of the books on pure group theory, it is probably the most relevant to Graph Isomorphism.
A book ...
The obvious answer would be Lance Fortnow's book The Golden Ticket but I can't say anything more about it, as I've not read it myself. (If somebody has read it and wants to say more, please leave a separate answer and I'll delete this one.)
Charles Petzold: The Annotated Turing, which is essentially a guide through Turing's seminal paper and a set of notes explaining things.
I also liked:
Douglas Hofstadter: Metamagical Themas, in my opinion more interesting than GEB (which is - according to some of the other commenters - not too difficult to achieve :) ), this is a collection of ...
You may find of interest the following recent handbooks.
The range of topics covered goes well beyond CLRS, and the material is well suited for graduate and Ph.D. students, even though you may choose a few selected topics for advanced undergraduate students.
Algorithms and Theory of
Computation Handbook Second Edition (Special Topics and Techniques)
I would like to add two books not found on the answers given up to now:
Aaron Stump, Programming Language Foundations
David Schmidt, Denotational Semantics: A Methodology for Language Development
Stump's book is concise but very clear.