2
$\begingroup$

I have been studying Introduction to Theory of Computation by Micheal Sipser and I just complected it. Now I want to take this a step further what should I do next to increase my skills. I tried looking at some papers from FOCS but they were beyond my understanding. I want to know what should I study next.

$\endgroup$
1
3
$\begingroup$

Theory of Computation, as practiced in the US, focuses mainly on two areas: algorithms and complexity. For algorithms, the standard textbook is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein, also known by its acronym CLRS. For complexity, there's the advanced textbook Computational Complexity: A Modern Approach, but it might be too much for a beginner.

$\endgroup$
1
  • $\begingroup$ Piggybacking on Yuval's answer, a possibly softer introduction to complexity is Dexter Kozen's Theory of Computation. An alternative, freely-available textbook for algorithms is Algorithms by Jeff Erickson. $\endgroup$ Oct 24 '19 at 15:07
2
$\begingroup$

Let me tell you the road map. First thing you need to learn is discrete mathematics, try some books at your own. Once you are comfortable with discrete mathematics then again go through data strcurures one more time. Once you are ok with data structure. Its time to learn the algorithms from coreman book or from any other book. Now once you have a learned algorithms. It is the time to learn theory of computation. I will suggest you learn theory of computation from ullman book (if you are pure theory person) and from Cohen if don't like theory that much. Note that to learn theory of computation you need

  1. Discrete Mathematics
  2. Data structure
  3. Algorithms

if you have this much then follow this method. Suppose you have less time then directly try to read theory of computation book and go back and forth between the topics which you need in order to understand the concepts of theory of computation.

Once more if you really needs to learn the theory of computation, do programming on the exercises on topics like regular expression, turing machines etc.

Now suppose that you have understood the theory of computation then there are two possible directions, you might be interested in compiler design or in complexity theory. For compiler design, there is a famous book by Rajeev motwani et.al. Try to explore both directions.

$\endgroup$
1
  • $\begingroup$ Thank You so much for this insight I will keep these points in my mind. I have struggled with programming for a while and i feel like thats not my area so I want to keep to complexity theory and remain theoretical. $\endgroup$
    – lemniscate
    Oct 25 '19 at 11:05
1
$\begingroup$

If you're looking to increase your development skills, a more hands-on approach to Automata, Automata and Computability: A Programmer's Perspective is an easy read that comes with a fantastic visualization tool for many topics in the field: DFA, NFA, PDA, TM, etc. It's great for getting your feet wet with developing general automata, IMO.

$\endgroup$
1
  • $\begingroup$ I am looking to improve my theoretical skills $\endgroup$
    – lemniscate
    Oct 24 '19 at 4:36

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.