If you have to recommend books for someone who wants to learn more about TCS at the introductory level such as automata theory, algorithmics, complexity theory, etc, what book(s) would you recommend for those who are interested and want to learn more about TCS, but not had any exposure to it?
If you would like to have a general introduction without getting to deep into the technical details, I suggest David Harel's Algorithmics: The Spirit of Computing. After that, this is my favorite list:
- Michael Sipser's Introduction to the Theory of Computation: the best introduction to automata theory, computability and complexity.
- Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: the most intuitive introduction to algorithms with stronger focus on intuition than technical proofs.
- Jon Bentley's Programming Pearls: this is not a textbook on algorithms, but it demonstrates beautifully how to use algorithm design techniques to solve real problems that irritated real programmers. :-) This might be a good start if you have some pre-knowledge on programming.
- Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein is a popular choice, title speaks for itself.
- Compilers: Principles, Techniques, And Tools by Aho, Ulman and Sethi is a good book about compilers, has some introduction material about automata theory too.
- Principles of Model Checking is a massive book can be used as an introduction to model checking
For the mathematics needed in algorithm analysis, I recommend the one and only GKP:
Concrete Mathematics by Graham, Knuth, Patashnik
A comprehensive, high quality treatment of practically all the math you will need in (basic) algorithmics. It is an entertaining read and includes a wealth of exercises (and solutions).
Algorithms 4. Edition R. Sedgewick
An Introduction to the Analysis of Algorithms P. Flajolet, R. Sedgewick
Introduction to Automata Theory, Languages, and Computation J. E. Hopcroft, J. D. Ullman, (R. Motwani)
The 1979 first Edition has more theoretical results that are missing in the 2001 second Edition. Haven’t look at the third Ed yet.
Introduction to formal language theory M. A. Harrison
It is from 1978 but I still would like to see it on the list.
Logicomix: An Epic Search for Truth A. Doxiadis, C. H. Papadimitriou
Because it is totally awesome!
Garey and Johnson's Computers and Intractability: A Guide to the Theory of NP-Completeness
I’d love to have TAoCP on the list but I fear, that Don Knuth’s meticulous approach is nothing that could be considered as “introductory”. Sadly...
If you are entirely new to the field of TCS then Sipser's Introduction to the Theory of Computation is definitely the best book to get you started. I have read other introductionary books, and none of them, in my opinion, come close to Sipser's way of bringing the matter.
Other, more specific, good theoretical books are:
Some good books covering the Theory B part of TCS:
Logic in CS: Logic in Computer Science: Modelling and Reasoning about Systems By Michael Huth and Mark Ryan.
Broad coverage of various uses of logic in computer science. About 3rd year undergraduate level.
The Lambda Calculus: Lambda-Calculus and Combinators. An introduction by J. Roger Hindley and Jonathan P. Seldin.
Introduces the lambda calculus, which is an essential ingredient in the foundations of programming languages. About 3rd year undergraduate level.
Lead in to domain theory: Introduction to Lattices and Order (2nd ed.) by Davey, B. A. and Priestley, H. A. Cambridge University Press. (2002).
Covers a very useful topic, especially if you plan to work with semantics. It is a bit more mathematical than the other topics, but the early chapters are certainly at an advanced undergraduate level.
Semantics: Semantics with Applications: An Appetizer by Hanne Riis Nielson and Flemming Nielson.
A really nice introduction to programming language semantics. Rather than going deep into any particular formalism, it gives a broad presentation and includes applications generally not considered in other books on semantics. Could possibly be useful for 2nd year undergraduates.
This is an aggregate answer that contains books from answers with score at least five. Please discuss its content in the chat.
Algorithms & Data Structures
- Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (3rd ed 2009)
A comprehensive treatment of basic algorithms and data structures and their analysis without digging too deep.
- Algorithms by Dasgupta, Papadimitriou, Vazirani (2006)
The most intuitive introduction to algorithms with stronger focus on intuition than technical proofs.
Computability & Complexity
- Introduction to the Theory of Computation by Sipser (2nd edition 2005)
The best introduction to automata theory, computability and complexity.
Formal Languages & Automata
- Compilers: Principles, Techniques, And Tools by Aho, Ulman and Sethi (2nd ed 2006)
The standard book about compilers; very comprehensive. Touches automata theory, too.
- Principles of Model Checking by Baier, Katoen (2008)
Massive book that an be used as a comprehensive introduction to model checking.
- Programming Pearls by Jon Bentley (2nd ed 1999)
Not a textbook on algorithms but demonstrates beautifully how to use algorithm design techniques to solve real problems. Might be a good start if you have some pre-knowledge on programming.