Self-study Theory of Computation

[pc2-brazil]

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.

 

[Adyssa]

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).

 

[dhruv.tara]

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 :)

 

[Edgardo]

If you are interested in automata theory and computation I recommend these lectures by Shai Simonson:
http://www.youtube.com/user/Coderisland#p/c/0/HyUK5RAJg1c"

 

[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.

 

[pc2-brazil]

Thank you for your answers.

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.

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.

 

[Adyssa]

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!