From: crawford@church.mitre.org (Randy Crawford)
Subject: Re: Programmers
Organization: The MITRE Corporation, McLean, VA
Date: Tue, 15 Sep 1992 14:39:39 GMT

In article <716485859@pike.cs.duke.edu>, srt@duke.cs.duke.edu (Stephen R. Tate) writes:
> 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....

What has practical discrete math to do with math theory?  I don't deny the 
day-to-day value of discrete math, only of math theory.  There is a _huge_ 
difference between Graham, Knuth and Patashnik's Concrete Math and undergraduate
discrete 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!

In most cases, regular expressions are _not_ necessary for the recognition of 
lexical tokens.  If you've ever written your own lexical parser, you've
appreciated the necessity (or lack thereof) for regular expression matching.  
While lex _does_ allow the specification of regular expressions in identifying 
variables, it's only because old context-sensitive languages like FORTRAN need 
disambiguation clues to decide where one token ends and the next begins.  This 
is simply not necessary in more "modern" languages, where lexical analysis can
omit the use of regular expressions, and often relies (as in the case of C) on
type disambiguation. 
 
The original assertion (repeated above so that you might again read it) stated 
that Lex `parses' regular expressions.  I take issue with the term `parses', 
when in most cases, Lex doesn''t even need regular expressions, much less the
abilities of a CFG parser (like YACC).

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

Actually, that is exactly what I am saying.  Very few non-PhD computer scientists
(much less non-PhD programmers) will have the opportunity to discuss or decide
the NP-ness of a computational problem.  Their employers simply will not rely
on a non-authoritative source to decide the direction of work when theoretical
issues are at issue.  Would you go to a nurse for an appendectomy when a
surgeon is available, and you have much to lose if the practitioner isn't an
authority?

I am not arguing that NP is unimportant.  As I said (clearly, I thought) NP
and number theory are not appropriate subjects in an undergrad CS program
given the value of so many other subjects, that by their omission, leave the
CS degree holder less _appropriately_ educated than s/he should be.
-- 

| Randy Crawford        crawford@mitre.org        The MITRE Corporation
|                                                 7525 Colshire Dr., MS Z421
| N=1 -> P=NP           703 883-7940              McLean, VA  22102
Xref: sparky comp.edu:1572 comp.arch:9280 comp.lang.misc:2968