Will Theory of Computation course improve my coding skill?

[Jon McDonald]

Hey all,
I am starting a master's program this fall and one of the courses is on the theory of computation. I was wondering what your opinions are as to how applicabale knowledge gained from this type of course will be in on a job. I understand that understanding push down autonoma and turing machines may not be directly applicable to EJB development, but how will this knowledge improve my software engineering and program design & implimintation skill?
Thanks,
Jon

[Frank Carver]

In conjunction with other things, the answer is probably yes. You probably won't actually use much of it in day-to-day work, but having been exposed to it can give you a good alternative viewpoint to help you "see the wood for the trees".
On the other hand, there could be other courses you could take instead which might be more practically useful. What might you be choosing it against ?

[Joseph Hammerman]

Automata theory is pretty mathematical and out of touch with reality. If you are going to take theoretical computer science algorithms and complexity will be more useful, in an indirect sort of way.

[Roseanne Zhang]

Originally posted by Joseph Hammerman:
Automata theory is pretty mathematical and out of touch with reality. If you are going to take theoretical computer science algorithms and complexity will be more useful, in an indirect sort of way.

I've nothing to say about Automata, since I skipped that prerequite and took compiler theory directly. However, I'm sure i can say something about theoretical computer science algorithms and complexity. They are very useful in my experiences!!!

[Mark Herschberg]

I took two semesters of the theory of computation. it was one of my favotire courses (if they don't have a recommended text, use Mike Sipser's book). Of course, there's very little practical value.
Algorithms is the most practial, and the course teaches one of the most useful metalessons. Complexity theory is good for the same reason.
A good class on computer architecture and/or OS could be good, too, so could a compiler class. Those will give you a better undertsanding of the context and constraints in which you work.
--Mark

[Jon McDonald]

Thanks Everyone, for your replies.
I'm taking the algorithms course next semester, it should be fun.
My choices for this semester were between Theory of Computation,k a course on the Perl Language, and a course on Computational Biology. I excluded the perl course because I don't want spend a whole semester just studying a single programing language, if I can help it. It would be easier (and less expensive) for me to learn that on my own.
I'm leaning against the computational biology, mainly for 2 reasons. First, I question how taking a couse in that specific area of programming will improve my overall CS skill, compared to Theory of Computation. Second, taking that course would require me to really cram all the background biology knowledge I would need to pass the course. That time could be better spent studying CS.
Thanks again,
Jon

[Roseanne Zhang]

You said everything right on the point about computational biology. However, it is extremely hot on the job market, I guess that was why they offered it at the first place.

[flying jordan]

I have CS Masters degree so I have taken all these
courses. I think Algorithm is useful because it teaches you how to efficiently analyze and solve a problem and understand the tradeoff of running time, etc. Theory of computing, well, lot of schools require you to take it. But from the practical IT point of view. I think it is useless.

[Vikrama Sanjeeva]

Originally posted by Joseph Hammerman:
Automata theory is pretty mathematical and out of touch with reality.

Well, i have taken Automata Course too, & i found it much of help in reality.Especially NFA's (Non-deterministic Finite Auotmat) and Transition diagrams.

Originally posted by Roseanne Zhang :
I've nothing to say about Automata, since I skipped that prerequite and took compiler theory directly

Amazing!!.How your course advisor has allowed you to took Compiler course without Automata!!
Bye,
Viki.

[Roseanne Zhang]

That was my first graduate level course in CS, before that, I only had four concentated under-courses for non-CS majors. I totally went blank in the first a few weeks, and end-up the number one in class for the huge project. I was teaching theoretical physics at the same time. BTW, I got an A for that course.
I become a CS RA the next semester, and also taught other non-CS major graduate students.
A former physicist
[ August 20, 2002: Message edited by: Roseanne Zhang ]

[stephen Kang]

hi, Jon
Look at this page
You could find out very good algorithm materials from here.

This guy is amazing. You might want to learn as
a reference. As a bonus, you want to write the homework using LaTeX.
You don't want to look at CLR book(i never seen this kind of boring algorithm book) by MIT press
[ August 21, 2002: Message edited by: stephen Kang ]

[stephen Kang]

There is good quote ..
Today, I sometimes interview recent grads for software design jobs. One standard problem I pose is "Write a routine, in any programming language of your choice (I've probably seen it), that sorts an array of things according to some ordering scheme. I don't care about efficiency, but I expect the following: (a) that it is correct, (b) that you can explain the complexity of the algorithm in "O(n)" notation." Of course I expect a bubble sort of integers. One smartass did a Shell sort and got it right. But over 90% of the candidates fail this basic test. That's sad.

-- Rene Hollan, slashdot.org, 17 Oct 2001

[SJ Adnams]

stephen,
How many jobs require that you are able to write a sorting algorithm?
..and LaTex? why not learn morse code??

[stephen Kang]

simon,
It depends on what you think. Most courses from school are useless if we just think about the market. Why do we need to study Operating System Design in the college instead of getting MCSE and SCSA? Dadabase Systems instead of getting OCP or DB2? Then why do we need to go to the graduate school to learn the crap instead of getting lots of certifications?
I don't think learning a LaTeX doesn take a long time. If you really want to be 'trained', it will take a while. Vector programming, Scheme, Prolog, ML those are all stupid if we just think about the current market. Why people are so concerned about x'ML' language thesedays?
And another point is
Does the student whoever goes to the college needs to enjoy whatever their learning?
I actually heard the many people from the school enjoy using LaTeX also were interested in learning XML though i didn know what it was before. Maybe, those guys participate new language system or give a direction to the industry. who knows?
And I bet there are some reasons they teach LaTeX in the 'academic circle'.
Who knows he/she will publish the journal at ACM, which they only accept LaTeX format(maybe later, they could adopt xml code). As far as i know, LaTeX is the best presentation language so far. isn't it?
i guess those guys in W3C are used to be a fan of LaTeX since LaTeX gives idea of presentation of mark up. My biggest mistake during college was spending too much time for learning about C++.(template, STL) i thought it is really good language to worth spending time. But,I should have picked up java if i thought about Market. No, i should have gotten SunJavaCert. maybe i should have dropped out from the college to get many certifications.
They r not gonna ask about the memorization of "sorting algorithm". but they want to ask how do you approach the problems if you don't have easy access. I think learning algorithm is about teaching how to think of Computer Science problems in general. That's why the algorithm course is the core course of master and/or ph.d programm in any school. Maybe, the school want to weed out someone who doesn want to think or cannot think hard problems they encounter during graduate studies.
In addition, Is Automata theory a prerequisite for Compiler Construction? later on, parallel computing course. ah, one should learn about even regular expression, which is useless to the market, to write down about parsers. one might be sick and tired of 'right recursion stuffs' to deal with parsing algorithm.
[ August 21, 2002: Message edited by: stephen Kang ]

[Mark Herschberg]

Originally posted by Simon Lee:
How many jobs require that you are able to write a sorting algorithm?

I've used such algoritms 3 times at 2 jobs. Each time I used quick sort on 5-20 items--after I first looked it up in the book.
Unless you work for Google, I can't imagine that any job would. But, the algorithms course teaches a meta-lesson: how to concretely think and analyze algorithms and software issues. I won't hire someone who cannot do it.

--Mark

[Frank Silbermann]

Theory of computation only has direct applicability if you're going to write compilers/parsers.
What is of general value that the course can provide is a sense of conservatism. That is, that every feature or capability comes with a price. E.g., you can have weak models with limited generality about which you can prove many theorems, or you can have complex models with great representational power, which are very difficult to reason about.
I think the hope is that it gives the programmer a desire to seek simplicity in his code. As in Extreme Programming -- where you learn that the simpler design is going to be easier to modify when the requirements are changed.