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 ...
I briefly reviewed some areas here, trying to focus on ideas that would appeal to someone with a background in advanced mathematical logic.
Finite Model Theory
The simplest restriction of classical model theory from the viewpoint
of computer science is to study structures over a finite universe.
These structures occur in the form of relational databases, ...
I wish I had a good answer for you. I use Book:Fundamental Data Structures (a collection of relevant Wikipedia articles) for my course on this subject but it's not really a complete textbook (for one thing, it has no exercises). CLRS is, I think, at a good level of detail for this sort of class but is missing too many of the important structures.
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 ...
Maheshwari and Smid's Introduction to Theory of Computation is free, with a Creative Commons license. It has some computability and complexity theory as well but seems to be primarily on languages and automata.
"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 ...
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.
"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
Edmund M. Clarke, Orna Grumberg, Doron A. Peled: Model Checking. MIT Press 1999, is a nice book (for me) on model checking.
Glynn Winskel: The Formal Semantics of Programming Languages: an introduction. MIT Press 1994, is one of the standard textbooks on programming languages.
Mordechai Ben-Ari: Mathematical logic for computer science. Springer 2001, is ...
The Handbook of Data Structures and Applications (Chapman & Hall/CRC Computer & Information Science Series) is mostly devoted to elementary data structures, but it also contains a few advanced materials that you may find useful for teaching a graduate level course. Given the huge size (1392 pages), this book may be classified as an encyclopedic ...
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 ...
I'm pretty sure no such book exists.
I drew up an annotated bibliography for my recent course, which was loosely based on Erik's course at MIT. It's definitely incomplete—I covered very few geometric data structures and no text data structures, for example—but you might still find it useful.
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 ...
Database theory is a sprawling field providing many applications of logic. Descriptive complexity and finite model theory are closely associated fields. As far as I can tell, these areas all tend to use algebraic styles of logic (following in the footsteps of Birkhoff and Tarski) rather than proof-theoretic. However, some of the work of Peter Buneman, ...
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 ...
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)