Re: Is it essential to learn data structures before automata theory?

Barb Knox <see@xxxxxxxxx> wrote:
In article <laFEg.7372$Ji1.3582@trnddc05>, sillybanter@xxxxxxxxx wrote:

Student Body <studentbody@xxxxxxxxx> wrote:

Is it essential to learn data structures before automata and formal
language theory, or is some mathematical maturity enough? If so, why?

Is it essential, no. You can certainly learn automata and formal
languages with just a good math (particularly discrete math)
background.

A different but related question would be "does data structures make
sense as a prerequisite in a C.S. curriculum?" I'd say the answer to
that is "yes". In our curriculum, we use data structures as a
prerequisite for almost all advanced (junior/senior level) courses.
Why? Because that's how we guarantee that students have a significant
amount of experience writing programs and thinking about algorithms
and that sort of thing. Having that experience (and not necessarily
the specific topics in data structures), it's much easier to see how
automata theory relates to real-world problems in parsing and
programming.

I agree that some "programming maturity" as well as mathematical
maturity is useful for studying automata theory. But it may be that the
OP already has it through other routes, and thus wouldn't need to take a
data structures class; and indeed, in the OP's institution it may be
that the "programming lab" aspects that your institution folds into the
data structures class is located somewhere else (such as an explicit
programming lab class).

Good point. I also wanted to add two things to my earlier posting.

First, there are certainly reasonable disagreements over which works
better: starting with abstract concepts and applying to concrete
things later vs. doing concrete things first and then bringing in the
abstract things to tie things together with the big picture. As
someone who started off writing machine code in octal, then assembly,
and then higher level languages, I've always thought concrete-first
was the way to go. But people I know and respect have certainly made
good arguments for abstract-first as well.

Second, not everyone wants to be a programmer. I've known excellent
theoreticians (the area I worked in for my PhD and years afterward,
incidentally) who understood complexity theory and higher-level
algorithm design and analysis and yet couldn't have written a decent
program to save their lives. Nothing wrong with that if that's how
someone wants to specialize...

--

Steve Stringer
sillybanter@xxxxxxxxx

.

Relevant Pages

  • Re: Is it essential to learn data structures before automata theory?
    ... You can certainly learn automata and formal ... A different but related question would be "does data structures make ... I agree that some "programming maturity" as well as mathematical ...
    (comp.theory)
  • Re: Domain Modeling Refutation Authorities
    ... Adaptive programming and the Demether Method research project ... problems with vague assumptions about data structures. ... principles like Liskov Substitution Principle. ... it is domain-modelling of a situation, ...
    (comp.object)
  • Re: Factor
    ... emphasis on idiomatic programming is the greatest challenge. ... it sure is nice when a language gives you a rich and ... flexible set of data structures and algorithms that are designed so ... There is no reason to believe that my implementation of lists is ...
    (comp.lang.forth)
  • Re: dangers of operator overloading
    ... Understanding data structures and algorithms is what ... true of a lot more domains than programming. ... Disagree about what you would call "high-level"? ... and languages like Ruby or ML or APL ...
    (comp.programming)
  • Re: Academic research aimed at improving programmer productivity?
    ... >> automata. ... > But note that to USE antilock brakes properly you must have read the ... >> So programming would be difficult, but not because of a sea a details ... Except it seems rather unlike real carpentry, ...
    (comp.programming)