Book Review: Theoretical Computer Science

I recently picked up a copy of Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptographyby Juraj Hromkovič. (Spriger, EATCS series)Theoretical Computer Science

I thought the chapters in the book were pretty introductory, however the emphasis here was on mathematical (and formal) rigor. There were no intuition-based talks, but everything followed from deductions. The book is very conservative about notations and formalism, which i think is a good thing, especially for new researchers (like me)

The nine chapters covered a lot of ground, and would benefit anyone who wants an introduction to the topics listed in the cover. Although, they were mostly introductory, it still conveyed some of the important ideas in the topics and in Theoretical Computer Science in general. I particularly enjoyed the read on Kolmogorov complexity.

The book, I felt, is accessible to an advanced undergraduate, or anyone with a enough mathematical maturity. There are some really nice exercises as well, and it can be fun to discuss those. The exercises were mostly based on the ideas that came from the sections that preceded it.

Overall, anyone who wants to explore CS Theory to a level of attending a talk in a Theory conference, can take a look at this book, the exercises require some work, but i won’t say they are really challenging.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s