From: srt@duke.cs.duke.edu (Stephen R. Tate)
Newsgroups: comp.edu
Subject: Re: Programmers
Date: 14 Sep 92 15:51:00 GMT
Organization: Duke University Computer Science Dept.; Durham, N.C.

In article <1992Sep12.043133.6177@linus.mitre.org> crawford@church.mitre.org (Randy Crawford) writes:
>In article <PSU.92Sep11102557@ptero.cs.duke.edu> psu@cs.duke.edu (Peter Su) writes:
>>- The libraries have a routine called qsort, [...]
>
>This is an algorithm, not math theory.  To see the difference, pick up and 
>compare any algorithm book with Knuth et al's Concrete Math or a text on 
>computability.

And how can you possibly understand why quick sort works fast without
knowing some discrete math?  Of course, if you want to want to just do
things without understanding them, you don't need to know the math....

>>- There is a program called Lex that parses regular expressions, which
>>were made up by a math theory bullshit guy named Kleene.  [...]
>
>Another specific algorithm.  I suspect your appreciation for lex is as a
>useful program which illustrates some algorithm, not as a wonderful example 
>of abstract algebra.  And BTW, lex doesn't do much with regular expressions.
>It's sole responsibility is identification of lexical tokens.  Look to YACC 
>for regexps and more.

You have just demonstrated the point!!!  You don't understand what lex
has to do with regular expressions --- you say "it's sole responsibility
is identification of lexical tokens".  What exactly do you think
lexical tokens are????  They're regular expressions!!!!  Back to formal
languages theory class for you!

YACC recognizes another form of language called "context free languages"
(actually a subset of context free languages, but that's another issue).
*NOONE* should be able to call themselves a competent computer programmer
without understanding context free languages --- that's the basis of
all programming languages, after all.

>                                                                 But I sus-
>pect we differ when it comes to expecting most CS grads to be able to analyze 
>algorithms and derive their complexity, or decide whether a task in NP or 
>*P-complete, or compare partial or mu-recursive functions.

You certainly aren't saying that understanding NP-completeness is not
useful to a programmer, are you?   If you don't understand that certain
*very natural and often occurring* problems cannot be solved by anyone
today, you could spend a lot of time on pointless work.  And yes, NP-complete
problems come up often in issues related to operating systems and typical
"hacker work".

As for the references to recursive function theory, I will agree with
you there --- there's not much that is of day-to-day usefullness.  However,
students should realize that there are functions that cannot be computed
no matter how long you spend, and that some useful sounding things like
the halting problem are non-computable.  It's what we call "being educated".


-- 
Steve Tate srt@cs.duke.edu | The reason why mathematics enjoys special esteem,
Dept. of Computer Science  | above all other sciences, is that its laws are
Duke University     | absolutely certain and indisputable, while those of all
Durham, NC  27706   | other sciences are to some extent debatable. (Einstein)
Newsgroups: comp.edu,comp.ai.edu,sci.edu,comp.multimedia,misc.education