10
$\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?

$\endgroup$

closed as not constructive by Gilles 'SO- stop being evil', svick, Stéphane Gimenez, Gopi, Raphael Mar 18 '12 at 22:59

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. If this question can be reworded to fit the rules in the help center, please edit the question.

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.
$\endgroup$
  • $\begingroup$ DPV is not in print yet; is it generally known? $\endgroup$ – Raphael Mar 18 '12 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 '12 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 '12 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 '12 at 17:38
7
$\begingroup$
$\endgroup$
  • $\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 '12 at 8:19
  • $\begingroup$ @Dai, you are probably right, I've changed it to Baier's Principles of Model Checking $\endgroup$ – Daniil Mar 17 '12 at 8:51
  • $\begingroup$ Can one understand model checking without basics in logics and/or automata? $\endgroup$ – Raphael Mar 17 '12 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 '12 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 '12 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).

$\endgroup$
  • $\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 '12 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 '12 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 '12 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 '12 at 0:23
  • 2
    $\begingroup$ @DaveClarke can you please recommend us some books on Theory B maths? $\endgroup$ – Daniil Mar 18 '12 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...

$\endgroup$
  • $\begingroup$ Logicomix is certainly a gem, not saying that the others aren't. $\endgroup$ – Dave Clarke Mar 17 '12 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 '12 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 '12 at 15:29
  • $\begingroup$ Which of those are really beginner-proof? $\endgroup$ – Raphael Mar 18 '12 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 '12 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:

$\endgroup$
  • $\begingroup$ Already mentioned above. $\endgroup$ – Dave Clarke Mar 17 '12 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 '12 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 '12 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 '12 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 '12 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.

$\endgroup$
  • $\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 '12 at 13:10
  • 1
    $\begingroup$ I've added a description of each book. All are good. $\endgroup$ – Dave Clarke Mar 18 '12 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.
$\endgroup$
  • $\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 '12 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 '12 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 '12 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 '12 at 21:55
  • $\begingroup$ let us continue this discussion in chat $\endgroup$ – Raphael Mar 18 '12 at 22:51

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