4
$\begingroup$

I am an undergraduate student of Computer Science and am very interested in learning the theoretical part of it all.

Unfortunately, none of the subjects we have in our UG program give us an insight of theoretical part of Computer Science. We do have the subjects Automata and Graph Theory, but our syllabus is very limited.

I have been looking for resources to learn the theory of computer science from the base up, for quite some time now. I have already tried reading papers, completed MOOCs.

Somehow, I am always dissatisfied with the material. It is either too complicated (I don't even understand the notation used) or too trivial (teaching bits and bytes).

Could someone please provide me with some resources to learn theoretical computer science. If possible, sort it in the order in which I should read it, so that the majority of prerequisites of the nth entry in the list, are covered in the preceding n-1 entries.

Please keep in mind:

  • I am really interested in learning it.
  • I have a decent background in programming, and have worked with several programming languages.
  • This is not a What videos/papers/books should everyone watch/read question. I am simply looking for some introductory resources, which are neither too obvious, nor too complicated.

I have had 3 semesters of College level Maths. Also, I have studied the material provided by ocw.mit.edu, for the courses: 18.03, 18.062J and 18.400J mentioned at http://math.mit.edu/academics/undergrad/major/course18C/

Thanks a lot.

$\endgroup$
  • 1
    $\begingroup$ Your question is interesting. However, you forgot to mention one very important thing: What is your math background? $\endgroup$ – scaaahu Aug 1 '13 at 2:46
  • 6
    $\begingroup$ This page from my algorithms course site may be helpful. See especially the review resources at the bottom of the page. $\endgroup$ – Jeffε Aug 1 '13 at 3:09
  • 5
    $\begingroup$ Definitely this must be in your bookcase: M. Sipser, Introduction to the Theory of Computation $\endgroup$ – Marzio De Biasi Aug 1 '13 at 12:14
  • 11
    $\begingroup$ I think this question is off-topic here. Please check help center. This question is more suitable for Computer Science. $\endgroup$ – Kaveh Aug 2 '13 at 6:11
  • 4
    $\begingroup$ This question is certainly not "off-topic" here. And if "formally" it is (by some sets of regulations), then the formalities should probably be changed. Many of the users here are also teachers and part of their job is undergrad and graduate teaching, oriented to TCS. So what kind of undergraduate teaching optimizes a student's skills in doing later research in TCS is part of their interest as researchers. $\endgroup$ – Dilworth Aug 4 '13 at 12:04
4
$\begingroup$

Of course, plenty of introductory resources are available and it is impossible to be objective here. So what follows is merely my biased choice.

I would definitely start with reading something on algorithms and on discrete mathematics (possibly in parallel). Here, I would recommend the following books:

The first book mentioned is one of the most widely known resources on algorithms, suitable as an introductory resource. The second book is little bit older and more theoretical, however imho still valuable. The third book is (in my opinion) an excellent and readable introduction to various parts of discrete mathematics.

Later, I would recommend to focus on formal languages and automata theory. Here, my choice is the following book:

You might also like to consult the Sipser's book mentioned in one of the comments.

Of course, if you have some background, there may not be a need for you to thoroughly study these textbooks. However, it is imho necessary to have a stable grounding in the above mentioned subjects before proceeding any further. Thus, it may be sensible for you to consult the above mentioned resources and focus on the material that you find new and/or interesting.

After mastering these preliminaries, there are plenty of choices where to continue. In my opinion, you should definitely study some complexity theory. Here, I would recommend the following book:

You also might be interested in some slightly more advanced (or, let us say, intermediate) mathematical methods used in the analysis of algorithms. Here, the following resource is considered to be classic:

Some basics of optimization (especially linear programming) are a must for computer scientists. Here, I would recommend the following gentle introduction:

A well written (and not very demanding) introduction to randomized algorithms is the following:

Finally, some nice books on advanced algorithms and/or computation theory include:

However, I would suggest reading these only after thoroughly mastering those mentioned above.

This is not a complete list, however. Many other excellent resources are available. The selection I have made is based on my personal bias. Moreover, I have included only resources focused on the "algorithmic part" of theoretical computer science. That is, the selection I have made is not only incomplete, but also very narrow.

And I have to mention that learning some more advanced math would be very helpful for you. My general advice is: the more mathematics you know, the better. It is more and more obvious that there is not any mathematics absolutely irrelevant to computer science.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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