Recommended resources for computer science theory.

Question

When I return to university in December (I'm on an internship now), I'll be taking a course in Computer Science theory. However, I'm not a very theoretical person, and abstract concepts have been difficult.

This course will cover topics such as regular, context-free and computable (recursive) languages with finite state machines, pushdown automata and turing machines along with the basic concepts of computability theory and NP-theory.

I have downloaded JFlap (an automata simulator application) and read Wikipedia, but what other resources cover topics such as this? I'm thinking it might also be a good idea to brush up on my discrete mathematics, so I'll be using that book, but discrete mathematics resources would also be appreciated.

Answer 1

The Art of Computer Programming by Donald Knuth

It's not 'easy' in any way, shape, or form, but you'll learn a heck of a lot.

Answer 2

Try Google Scholar: http://scholar.google.com/scholar?q=computer+science+theory

Answer 3

@Nick Berardi: It's just a list of books. Hopefully, people here have experience in this topic area and can recommend resources to use or avoid. If I just wanted a raw list, I would use Google or Amazon.

Answer 4

Concrete Mathematics by Graham, Knuth and Patashnik is an excellent text book for more advanced discrete mathematics, particularly providing the mathematical tools that are needed for a wide range of problems.

Actually being able to understand most of it is still one of my goals a decade after graduating.

Answer 5

http://www.theannotatedturing.com/

Recommended reading by Jeff Atwood.

Answer 6

A very nice book about these topics is Papadimitriou's Computational complexity. Not so much on discrete mathematics in this one, though...

I would really not recommend Knuth's TAOCP in this context: to me, it's more a reference book that one you read front to back! (And it's quite frustrating as a reference, as a lot of interesting results are 'left as exercises'...)

Answer 7

Introduction to the Theory of Computation by Michael Sipser

used to be our course book back in college. It is easy to read and concepts are explained in a very neat way.

Answer 8

• Introduction to Algorithms is fairly good introduction into some of the theory of algorithms and also makes a decent enough reference once you are done reading it.
• Computers and Intractability: A Guide to the Theory of NP-Completeness is a classic on the field of NP-Completeness, but is starting to get dated in some areas. However, it is still one of the best books out there on the topic.
• Art of Computer Programming previously mentioned, but it bares worth mentioning again as this is one of the authoritative texts on the subject and Knuth continues to try and make sure it is up to date via Errata that he releases. If you can understand everything in this, then you should be able to understand most anything related to computer theory.

Google Scholar is actually a really good place to look for articles, but you need to be fairly targeted in your searches. For example, the search "knapsack problem" should turn up some actual articles that you can actually download. It does take a bit of practice to start getting use to Google Scholar though.

Answer 9

I think that "Algorithmics: The Spirit of Computing" by David Harel is just the thing for you.

It's a very light read, but coveres things like computability theory, NP-theory in a really easy and fun approach. Maybe it doesn't explain any equasions, or stuff like that, but it shows you the ideas in a really great way. I think it's a very good place to start for a guy like you.

Answer 10

Hover in and around wikipedia, it should help a lot. If you want to go deeper, even then follow links from wikipedia

Answer 11

Concepts of Programming Languages by Sabesta is a great resources for what you are wanting to learn.

Answer 12

Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists: This is a bedside book, but it helps you understand how some innovations are made through the lives of great computer theorists. Also, it gives some very basic background on what these men have found. You can be motivated with what's in it.