11
$\begingroup$

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?

Improve this question
$\endgroup$
8

7 Answers 7

Reset to default
9
$\begingroup$

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.
Improve this answer
$\endgroup$
4
  • $\begingroup$ DPV is not in print yet; is it generally known? $\endgroup$
    – Raphael ♦
    Mar 18, 2012 at 2:27
  • $\begingroup$ Due to this answer's score, I included the answers in an aggregate answer. Please consider removing your answer for the sake of clarity. $\endgroup$
    – Raphael ♦
    Mar 18, 2012 at 2:41
  • $\begingroup$ @Raphael DPV has been in print for several years, but it's still nicely available online. I tried not to link to commercial website like amazon. $\endgroup$
    – Dai
    Mar 18, 2012 at 14:50
  • $\begingroup$ @Dai: I see. The page you link to says "This is a penultimate draft of our soon to appear textbook.", therefore my confusion. $\endgroup$
    – Raphael ♦
    Mar 18, 2012 at 17:38
7
$\begingroup$
Improve this answer
$\endgroup$
11
  • $\begingroup$ I find Clarke's book a bit too heavy for someone without TCS background. I know (in person) PhD students who find the book hard to understand. $\endgroup$
    – Dai
    Mar 17, 2012 at 8:19
  • $\begingroup$ @Dai, you are probably right, I've changed it to Baier's Principles of Model Checking $\endgroup$
    – Daniil
    Mar 17, 2012 at 8:51
  • $\begingroup$ Can one understand model checking without basics in logics and/or automata? $\endgroup$
    – Raphael ♦
    Mar 17, 2012 at 11:49
  • 1
    $\begingroup$ The Dragon Book is certainly a good reference; is it theoretical enough, though? (I honestly don't know) $\endgroup$
    – Raphael ♦
    Mar 17, 2012 at 12:04
  • $\begingroup$ @Raphael "Principles" somewhat gives an introduction to logic (at least some necessary knowledge) and automata. It's a pretty big book too, ~980 pages. As for The Dragon Book, I thought that compilers is a rather theoretical area, isn't it? $\endgroup$
    – Daniil
    Mar 17, 2012 at 12:12
6
$\begingroup$

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).

Improve this answer
$\endgroup$
5
  • $\begingroup$ I tried reading this book, but I didn't like it, because it all felt very... clumsy and clustered. I just didn't feel the beauty of maths there. Compare that with Sipsers' outline of automata theory or Smullyan's books on logic or even Dummit&Foote's Abstract Algebra. Maybe that's just me, tho. $\endgroup$
    – Daniil
    Mar 17, 2012 at 15:05
  • $\begingroup$ I second Daniil. It's a collection of excellent tools for theoreticians. But it is too dry and technical to be enjoyable for beginners. I really like the books I mentioned above since they seem to have their own souls. They read as if someone is telling you stories, interesting ones. $\endgroup$
    – Dai
    Mar 17, 2012 at 15:58
  • $\begingroup$ Unfortunately, it does not cover structural induction, coinduction, domain theory, and all of the stuff needed for Theory B-style TCS. $\endgroup$
    – Dave Clarke
    Mar 17, 2012 at 20:29
  • $\begingroup$ @DaveClarke: Correct. I am not sure I would expect any math-math book to contain any of that. But then, GKP is supposed to be a cs-math book. It contains no logics, either, so I should rephrase a bit. $\endgroup$
    – Raphael ♦
    Mar 18, 2012 at 0:23
  • 2
    $\begingroup$ @DaveClarke can you please recommend us some books on Theory B maths? $\endgroup$
    – Daniil
    Mar 18, 2012 at 6:05
5
$\begingroup$

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!

Again 1979
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...

Improve this answer
$\endgroup$
5
  • $\begingroup$ Logicomix is certainly a gem, not saying that the others aren't. $\endgroup$
    – Dave Clarke
    Mar 17, 2012 at 14:41
  • $\begingroup$ I don't really like the way Logicomix portrayed Logicians as "insane" sort of people. Ideas in logic when explained in the right way are very down to earth and simple, and not really that "insane". $\endgroup$
    – Dai
    Mar 17, 2012 at 14:49
  • 1
    $\begingroup$ @Dai Have a look at the lives of extraordinary people like e.g. Gödel, Wittgenstein, Nash, etc. they were ... well extraordinary. $\endgroup$
    – uli
    Mar 17, 2012 at 15:29
  • $\begingroup$ Which of those are really beginner-proof? $\endgroup$
    – Raphael ♦
    Mar 18, 2012 at 2:25
  • $\begingroup$ @Raphael IMHO all of them, otherwise I wouldn’t have posted them here. Some may have a steep learning curve but I think that’s okay. $\endgroup$
    – uli
    Mar 18, 2012 at 10:11
4
$\begingroup$

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:

Improve this answer
$\endgroup$
7
  • $\begingroup$ Already mentioned above. $\endgroup$
    – Dave Clarke
    Mar 17, 2012 at 14:42
  • $\begingroup$ @DaveClarke I was planning to add more resources to the list as I did with my edit now, but I also wanted to emphasize how great Sipser's book is by mentioning it again! :-) $\endgroup$
    – codd
    Mar 17, 2012 at 14:51
  • 1
    $\begingroup$ Pierce's book is a gem. I wish it had been around when I did my PhD (in types). $\endgroup$
    – Dave Clarke
    Mar 17, 2012 at 14:52
  • $\begingroup$ @DaveClarke I am currently using it for my bachelor thesis by recommendation of my advisor and I am also very impressed by it! $\endgroup$
    – codd
    Mar 17, 2012 at 14:54
  • 1
    $\begingroup$ Thanks for the reference, I will take a look at it later today. I see that you are a professor at KUL, I am coming there next year to study Secure Software (Veilige software). What a small world. $\endgroup$
    – codd
    Mar 17, 2012 at 15:15
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't know any of those even by reputation, so I can't say wether they are any good (even though I am inclined to take your word for it). :/ $\endgroup$
    – Raphael ♦
    Mar 18, 2012 at 13:10
  • 1
    $\begingroup$ I've added a description of each book. All are good. $\endgroup$
    – Dave Clarke
    Mar 18, 2012 at 13:17
3
$\begingroup$

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

Formal Languages & Automata

Applied Theory

  • 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.
Improve this answer
$\endgroup$
5
  • $\begingroup$ This doesn't answer the question, or if it's meant to, it is not a good answer. Do you mean someone starting TCS needs to read all of these books? If not, how would they choose? Keep in mind that by your rule, this answer is likely to grow to contain hundreds of books $\endgroup$
    – Gilles 'SO- stop being evil'
    Mar 18, 2012 at 2:46
  • $\begingroup$ @Raphael Are you it's polite to ask someone else to remove his/her own answer? Usually the asker himself/herself can do the job of aggregating his favorite answers by modifying his/her own question text, but I've never seen anyone force another person to delete his/her own post to create his own answer. This cs stackexchange is getting weird with these narcissistic behaviors. $\endgroup$
    – Dai
    Mar 18, 2012 at 12:46
  • $\begingroup$ @Raphael: Making it a CW doesn't make it right to ask someone to delete his/her own answer. It's like saying I'm gonna writing a book/survey paper (which I will publish online for free), so I go around and ask all authors whose papers I cite to take down their own papers to avoid confusion. $\endgroup$
    – Dai
    Mar 18, 2012 at 14:47
  • $\begingroup$ @Raphael I don't see any where in the CC licenses saying that my work will be eventually requested taken down by someone else. I don't know what sort of fantasy you have with SE, but it's definitely not Wikipedia. I know you work hard to "moderate" this website, but please also respect someone else's freedom of speech and privacy, and simply let the up/down votes take care of the rest. I think the goal of cs SE is to provide a more friendly forum than cstheory SE to beginners, but the micro level of management you proposed here made it so much worse. $\endgroup$
    – Dai
    Mar 18, 2012 at 21:55
  • $\begingroup$ let us continue this discussion in chat $\endgroup$
    – Raphael ♦
    Mar 18, 2012 at 22:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.