0
$\begingroup$

I am sophomore studying electrical engineering and I have immense interest in pure mathematics and theoretical computer science. I have studied abstract algebra ,real analysis and little bit of topology and discrete math too. I am also an enthusiastic coder .

What is the 'roadmap' for an engineer interested in theoretical computer science and the best books for an undergrad student , which I should study in order to go ahead in this field ?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ I think the roadmap for a sophomore is pretty similar no matter what their current major ... especially since you already have a good math background. (1) Take TCS courses (and math courses don't hurt). (2) Get involved in some TCS research with a professor. $\endgroup$
    – usul
    Feb 15, 2015 at 15:34
  • $\begingroup$ It might help to check out a couple of related topics, like this about learning resources, and of course the poorly named "everyone-should" lists, like this one. $\endgroup$
    – Basil
    Feb 16, 2015 at 11:40

1 Answer 1

Reset to default
1
$\begingroup$

Theoretical computer science has many dimensions. One of them is the study of programming languages (in a general sense). Here is a path into this field.

  • An introductory textbook on logic like Dirk van Dalen's "Logic and Structure". There are plenty of other good books on the subject, but I recommend one that that talks a little bit about proof theory and intuitionistic logic as both are at the heart of programming language theory's use of logic.

  • Followed by an implementation oriented book like John Harrison's amazing "Handbook of Practical Logic and Automated Reasoning". After finishing this book you could start coding, for example SAT-solvers, a highly interesting field, merging theory and practise. It's competitive too: http://www.satcompetition.org/

  • In parallel you can read an introductory text book on the theory of programming languages. Alas there is nothing really up-to-date, reflecting the last 25 years of progress, but Glynn Winskel's "The Formal Semantics of Programming Languages" might not be the worst place to start.

  • Some, but not all parts of programming language research is enamoured with category theory. The usefulness of category theory for programming languages is fiercely debated. But since you've already mastered abstract algebra, you should be able to pick up category theory without too much pain. You could start with "Category Theory" by Steve Awodey, or "Abstract and Concrete Categories" by Adamek et al. The categorical viewpoint on a lot of things can be quite mind-blowing.

You would be well-qualified to dive into more specialised subfields of programming language research with this background.

None of the above would be very useful for the algorithms / complexity track of theoretical computer science.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your answer ... I am interested in complexity theory more than the study if programming languages . Sorry, I forgot to mention that earlier. $\endgroup$
    – Vatsal Limbachia
    Feb 15, 2015 at 9:42
  • 3
    $\begingroup$ SAT solving is very interesting from a complexity point of view because complexity theory suggests that we can't do it, but in practise we do really well. Moreover the algorithms we use in practise for SAT solving (variants of DPLL) are known to be worse (in the sense of complexity theory) than some approaches we don't use. it's all quite mysterious. $\endgroup$
    – Martin Berger
    Feb 15, 2015 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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