I'm very interested in Computer Science (computational complexity, etc.). I've already finished a University course in the subject (using Sipser's "Introduction to the Theory of Computation").
I know the basics, i.e. Turing Machines, Computability (Halting problem and related reductions), Complexity classes (time and space, P/NP, L/NL, a little about BPP).
Now, I'm looking for a good book to learn about some more advanced concepts. Any ideas?
$\endgroup$ 126 Answers
$\begingroup$The Art of Computer Programming
(Donald Knuth)
The legendary book (of multiple volumes, still incomplete) can't go without mention. For learning about algorithms and their complexities, there is no rival. It's written with practicality in mind, though from a largely theoretical perspective.
(source: wikimedia.org)
Papadimitriou's Computational Complexity covers complexity theory at a higher level than Sipser, but has essentially no prerequisites.
$\endgroup$ $\begingroup$You may enjoy "Computers and Intractability: A Guide to the Theory of NP-Completeness" by Garey and Johnson. It is widely considered a classic in the field and it takes the subject matter of the last chapters of Sipser into the stratosphere.
Also... why not just follow the bibliograpy in Sipser?
$\endgroup$ $\begingroup$Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak, is a more up to date advanced 'introduction' text.
$\endgroup$ $\begingroup$I think you should determine what kinds of applications you want to apply CS to and then learn general theory relevant to those applications. Not all theory is equally applicable everywhere.
$\endgroup$ 1 $\begingroup$The Mythical Man-Month more for software engineering but absolutely one of the best books ever written about programing IMO.
$\endgroup$
