# Self-study Theory of Computation

by pc2-brazil
Tags: computation, selfstudy, theory
 P: 205 Good night, I want to study by myself Theory of Computation and its three main areas: Computational Complexity, Automata Theory and Computability. I find Algorithms and Algorithm Analysis to be specially interesting (although I don't know exactly where this topic fits). I am starting to self-study Discrete Mathematics, which I know to be fundamental for understanding all these subjects. For Discrete Mathematics, I'm reading Kenneth Rosen's "Discrete Mathematics and Applications", which I find very didactic. My doubt is the following: How should I proceed for being able to study these subjects the right way? By "the right way", I mean in the correct order, without missing on any basic subjects. I want to be correctly introduced to everything starting from the basics. Are there any other mathematics requirements besides Discrete Mathematics? Is there still something "between" Discrete Math and Theory of Computation? Also, I have the book "Algorithms" by Dasgupta, Papadimitriou and Vazirani, but I also don't know where to fit it. My current background in Mathematics is basically: high-school math and some self-taught Calculus (limits, derivatives and basic integrals). I'm currently reading Leithold's "The Calculus with Analytic Geometry". Thank you in advance.
 P: 188 I'm studying CompSci at uni, currently 2nd year and I'm a mature age student with a 10 year gap since I finished high school, so my maths is quite rusty. We use the following books: Discrete Algorithmic Mathematics - Maurer & Ralston The Design & Analysis of Algorithms - Levitin Languages & Machines - Sudkamp In my introductory maths course we studied set theory, some number theory, probability, logic and matrix manipulation - with a focus on set theory and logic. The prescribed book was quite good I thought, and I occassionally dig it out again. I'm certainly not getting rid of it, the concepts are core to Computer Science. For algorithms and complexity, I like the prescribed book VERY MUCH! It has hundreds of great exercises and good explanations of all the topics. This is a difficult subject for me, and I've found the book invaluable. We don't use a whole lot of maths in this course, as it's quite practical (we study different sorting algorithms, data structures, graph traversal, etc). We do derive summations to work out algorithm complexity, and I've had to study up on logarithm identities I found I was quite prepared for Computing Theory, we study languages, grammars, regular expressions, automata, complexity classes and cryptography which is an interesting application of some of the theory. We don't use much math in this course, most time is spent on regular/context-free/sensitive/unrestricted grammars and their relation to DFA/NFA/PDA/TM automata. If anything, I'd like a better understanding of proofs (by induction), as I get a bit lost in those sometimes. I'm yet to use much calculus (except for my OpenGL procedural modelling class, and not much there), but I start on more advanced maths next semester. So in short, IMHO, a basic understanding of discrete maths should set you up quite nicely to start on (theory of) computation and algorithm complexity. For the record, my next purchase is going to be Donald Knuth's books on algorithms. I'm going to have a look at the ones you've listed too as I've not heard of them before (that's not saying much, I'm only 18 months into my course and don't have much time for texts outside the prescribed ones).
 P: 46 I think that would be nice... there are more online lectures... check youtube for nptel and its course on discrete maths. and then you can see the course on numerical methods (if you are interested) on the same channel and finally you can get into the course on mit channel that deals directly with algorithms. B/w do some probability too. I am also going to self study some of these topics in coming summers :)
 P: 686 Self-study Theory of Computation If you are interested in automata theory and computation I recommend these lectures by Shai Simonson: Introduction to the Theory of Computation
 P: 595 I'm afraid I just can't remember the name of the automata book I remember somewhat successfully poking at 10 years ago... but the Wiki FSA and Markov pages have what looks to be a number of interesting sources in their bib's: http://en.wikipedia.org/wiki/Finite-state_machine http://en.wikipedia.org/wiki/Markov_chain For math, strong combinatorics and good linear algebra come to mind.
P: 205

 Quote by Adyssa Discrete Algorithmic Mathematics - Maurer & Ralston The Design & Analysis of Algorithms - Levitin Languages & Machines - Sudkamp
Based on Adyssa's suggestions, I think that I could use:
- "The Design & Analysis of Algorithms" by Levitin for algorithms and
- "Introduction to Automata Theory, Languages and Computation" by Hopcroft for Theory of Computation,
both at the same time.
It is a good combination?
But, before studying these topics, I need to study well Discrete Structures.

For discrete structures, I'm using "Discrete Mathematics and Its Applications" by Rosen, which I think is very good.

 Quote by schip666! I'm afraid I just can't remember the name of the automata book I remember somewhat successfully poking at 10 years ago... but the Wiki FSA and Markov pages have what looks to be a number of interesting sources in their bib's: http://en.wikipedia.org/wiki/Finite-state_machine http://en.wikipedia.org/wiki/Markov_chain For math, strong combinatorics and good linear algebra come to mind.
Do you think that Rosen's book provides the necessary basis (for combinatorics, discrete probability etc.)?
What about Markov chains? Is there some other math topic that I should study for this subject?

Another question:
What about Cormen's book on algorithms? I think that, besides Discrete Structures, I will need Statistics for this book.
 P: 188 Cormen's book was recommended for me, but it's apparently more rigorous and harder going than the one we were prescribed for the course. I plan on having a look at it, when I have some more time!

 Related Discussions Engineering, Comp Sci, & Technology Homework 1 Atomic, Solid State, Comp. Physics 0 Programming & Computer Science 0 Academic Guidance 0 Academic Guidance 1