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, ...
I would divide the books on programming language semantics into two classes: those that focus on modelling programming language concepts and those that focus on the foundational aspects of semantics. There is no reason a book can't do both. But, usually, there is only so much you can put into a book, and the authors also have their own predispositions ...
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 ...
"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)
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.
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 ...
I think the solution to your problem is not reading a probability book, but reading more papers in TCS.
Most papers in TCS don't actually use very advanced probability tools. Most of them use a small collection of basic and well known probability tricks. The reason you have a hard time following them is that you are not yet familiar with this bag of tricks, ...
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.
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
"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 ...
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.
I believe you would enjoy Theory of Classification: A Survey of Recent Advances by Boucheron, Bousquet, and Lugosi. In particular, it starts by building up basic generalization theory via Rademacher complexities, introduces some useful tools (like the contraction principle, whose proof you can track down in Shai&Shai's notes referenced in the answer by ...
For some material more recent than Kearns and Vazirani, you could check out Rocco Servedio's lecture notes for Advanced Topics in Computational Learning Theory, or the notes from Sasha Rakhlin's class.
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, ...