Name: Elements of the Theory of Computation
ISBN: 9780132734172

What Hacker News says

guiraldelliOct 2019

I don't think there is a definitive answer for your question because computer science is a relative new area of knowledge and “fundamental books” are still being published.

If I had to say one text that is the fundamental one, I would go with a paper: “On Computable Numbers, with an Application to the Entscheidungsproblem” [1], by Alan Turing.

---

But if you just started your course in Computer Science, then I will give you some “bookshelf advice" based on my experience. I had the pleasure to study all the books I am going to recommend you, and most of them I was able to read cover-to-cover during the university years. And they are also in my bookshelf for reference.

The book order does not represent rank of importance.

* “Introduction to the Theory of Computation”, by Michael Sipser.

    * I also recommend the “Elements of the Theory of Computation”, by Christos Papadimitriou.

    * Another good complement is “Introduction to Automata Theory, Languages and Computation”, by Hopcroft and Ullman. (Thanks, @reacweb, for the reminder.)

* “Graph Theory”, by Reinhard Diestel.

    * If you feel you want to go deeper, and like a book which you cannot skip a single word, I strongly recommend “Modern Graph Theory”, by Béla Bollobás: it is one of my favorite textbooks ever!

* “The Algorithm Design Manual”, by Steven Skiena.

    * While a lot of people seems to praise either the Cormen et al. or the Sedgewick books, I have the feeling that “Algorithms” by Dasgupta, Papadimitriou  and Vazirani is my choice for “fundamental” book. But I decided to

* “Computer Architecture: a Quantitative Approach”, by Hennessy and Patterson.

* “Modern Operating Systems”, by Andrew Tanenbaum.

* “Artificial Intelligence: a Modern Approach”, by Russel and Norvig.

* “Modern Compiler Implementation (in ML)”, by Andrew Appel.

I would like to also recommend “Concrete Mathematics”, by Graham, Knuth and Patashnik, but I remember to not feel it the most pedagogical book on the subject.

Good luck!

---

[1]: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

thread

Turing_MachineFeb 2018

You didn't say whether the goal is fundamental knowledge or employability. :-)

Splitting the difference, I'd say:

1) A Lisp or Lisp-like language. Either Racket or Clojure would be an excellent choice here; Racket is especially designed for teaching, and there is a lot of top-quality educational material for it. Clojure is probably more employable but isn't specifically designed for beginners. Recommended book: How to Design Programs, by Felleisen, et al (free online). If you want to go old-school, try Structure and Interpretation of Computer Programs by Abelson, Sussman, and Sussman. The video lectures for that one are also quite valuable.

2) C. K&R is short and information-dense. If you're going to use C professionally, you'll want more, but K&R is definitely enough for a good overview. Recommended book: The C Programming Language, by Kernighan and Ritchie (reasonably priced).

3) Maybe an assembly language. Or maybe not. If the goal is to understand computers at the most fundamental level, you might as well study the theory of computation rather than learning the quirks of a particular machine's instruction set. Recommended book: Elements of the Theory of Computation, Lewis and Papadimitriou (spendy).

4) The Javascript/HTML/CSS hodgepodge. Not anyone's choice for the greatest language ecosystem in the world, but probably the most employable one. Recommended book: sorry, I've never seen one that's completely satisfactory. On the other hand, there's probably more free educational material on the web for this than for anything else. On the gripping hand, a lot of it sucks.

5) An algorithms text. Many would recommend Introduction to Algorithms by Cormen, et al (often called "CLR" or "CLRS" for recent editions, but that can be tough sledding for a beginner. I would instead recommend any of the Algorithms in "X" books by Robert Sedgewick (where "X" is some programming language, such as C, Java, etc.). Having concrete code examples can be useful for a beginner, IMO. Once you have a handle on the basic ideas, The Art of Computer Programming by Donald Knuth is a reference you can return to time and again for the rest of your career.

5) Enough database theory and SQL to feel comfortable writing basic queries. Maybe Database System Concepts by Silberschatz, et al for the theory and one of the "SQL cookbook" texts for practical applications. Make sure that whatever cookbook you use covers things like SQL injection and that you fully understand that coverage. :-)

6) Prolog. The classic here is Programming in Prolog, by Clocksin and Mellish. However, I haven't been keeping up with Prolog for a long time. Someone else may have a better suggestion.

7) Machine learning and neural nets. No suggestion here -- it's not my field and it's been advancing very rapidly of late. Again, someone else may have a better suggestion.

8) Graphics. I like Computer Animation: Algorithms and Techniques by Rick Parent. Also, Computer Graphics: Principles and Practice by some combination of Hughes, Foley, van Dam, et al. This is a more in-depth text (actually, it's a good reference book). In either case, you'll need a good background in linear algebra and probably some calculus before tackling this. Owning both of these would be good if you're going to get into graphics in a serious way.

9) Erlang. Programming Erlang by Joe Armstrong.

thread

nandemoDec 2011

Yes.

I also like Papadimitriou's textbooks: Elements of the Theory of Computation and Computational Complexity.

thread

rwJun 2009

A few suggestions (if only we all had more time):

Do ProjectEuler.net, as it provides a great mesh between algorithm design and mathematics; it might be within your expertise already, however. Look in to getting a good discrete math book or two. My circumstances led me to not use my discrete math book very much for class, so I won't give you a recommendation that I do not have.

Go through Scholarpedia. They are doing cool work over there.

Get some text(s) on statistical inference, especially Bayesian learning. If you have access to a good library system (say, state-wide library loan), you ought to have no problem getting most textbooks.

Seeing as how you're into NLP and AI, look at concurrency and what, say, Google is doing with MapReduce and PageRank (they publish reasonably-understandable papers). In general, push yourself to read peer-reviewed journal articles on the topics of your interest.

Peruse some of the organizations that do research into the philosophical and human issues surrounding AI and technology. For example, there's Less Wrong at lesswrong.com. They can come off as quite hubristic, but if you drill through the latent groupthink and individual over-assertiveness, you'll find a gigantic wealth of information on both what rationality is, and how to apply it to your life.

Additionally, check out (I've mentioned these before, so I'll quote myself verbatim):

"Problems On Algorithms" (Parberry, Gasarch): A slim volume containing ~700 exercises on proving various properties of algorithms. And it teaches you most of what is needed. Download it from: http://www.eng.unt.edu/ian/books/free/

"Elements of the Theory of Computation" (Papadimitriou): Classic text. Sure you've heard of Turing machines before, but what do you know about mu-recursive functions? It's very beautiful and if you have a person with whom to read the book and do the exercises, you will gain immensely. It will help unify, in your mind, many of the myriad articles you've probably read on Wikipedia about formal languages and complexity theory.

thread

rwMay 2009

thread

AutreAug 2007

Kernighan & Ritchie, The ANSI C Programming Language

Kernighan & Pike, The UNIX Programming Environment

Kernighan & Pike, The Practice Of Programming (Really, anything written by Kernighan is pure joy, even a man page)

Jon Bentley, Programming Pearls

Papadimitriou &Lewis, Elements of the theory of computation

thread