home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / edu / 1665 < prev    next >
Encoding:
Text File  |  1992-09-15  |  4.9 KB  |  91 lines
  1. Newsgroups: comp.edu
  2. Path: sparky!uunet!cs.utexas.edu!sun-barr!ames!agate!linus!linus.mitre.org!crawford
  3. From: crawford@church.mitre.org (Randy Crawford)
  4. Subject: Re: Programmers
  5. Message-ID: <1992Sep15.143939.16386@linus.mitre.org>
  6. Sender: crawford@church (Randy Crawford)
  7. Nntp-Posting-Host: church.mitre.org
  8. Organization: The MITRE Corporation, McLean, VA
  9. References: <BuDHvA.226@mentor.cc.purdue.edu> <PSU.92Sep11102557@ptero.cs.duke.edu> <1992Sep12.043133.6177@linus.mitre.org> <716485859@pike.cs.duke.edu>
  10. Date: Tue, 15 Sep 1992 14:39:39 GMT
  11. Lines: 78
  12.  
  13. In article <716485859@pike.cs.duke.edu>, srt@duke.cs.duke.edu (Stephen R. Tate) writes:
  14. > In article <1992Sep12.043133.6177@linus.mitre.org> crawford@church.mitre.org (Randy Crawford) writes:
  15. > >In article <PSU.92Sep11102557@ptero.cs.duke.edu> psu@cs.duke.edu (Peter Su) writes:
  16. > >>- The libraries have a routine called qsort, [...]
  17. > >
  18. > >This is an algorithm, not math theory.  To see the difference, pick up and 
  19. > >compare any algorithm book with Knuth et al's Concrete Math or a text on 
  20. > >computability.
  21. > 
  22. > And how can you possibly understand why quick sort works fast without
  23. > knowing some discrete math?  Of course, if you want to want to just do
  24. > things without understanding them, you don't need to know the math....
  25.  
  26. What has practical discrete math to do with math theory?  I don't deny the 
  27. day-to-day value of discrete math, only of math theory.  There is a _huge_ 
  28. difference between Graham, Knuth and Patashnik's Concrete Math and undergraduate
  29. discrete math.
  30.  
  31. > 
  32. > >>- There is a program called Lex that parses regular expressions, which
  33. > >>were made up by a math theory bullshit guy named Kleene.  [...]
  34. > >
  35. > >Another specific algorithm.  I suspect your appreciation for lex is as a
  36. > >useful program which illustrates some algorithm, not as a wonderful example 
  37. > >of abstract algebra.  And BTW, lex doesn't do much with regular expressions.
  38. > >It's sole responsibility is identification of lexical tokens.  Look to YACC 
  39. > >for regexps and more.
  40. > 
  41. > You have just demonstrated the point!!!  You don't understand what lex
  42. > has to do with regular expressions --- you say "it's sole responsibility
  43. > is identification of lexical tokens".  What exactly do you think
  44. > lexical tokens are????  They're regular expressions!!!!  Back to formal
  45. > languages theory class for you!
  46.  
  47. In most cases, regular expressions are _not_ necessary for the recognition of 
  48. lexical tokens.  If you've ever written your own lexical parser, you've
  49. appreciated the necessity (or lack thereof) for regular expression matching.  
  50. While lex _does_ allow the specification of regular expressions in identifying 
  51. variables, it's only because old context-sensitive languages like FORTRAN need 
  52. disambiguation clues to decide where one token ends and the next begins.  This 
  53. is simply not necessary in more "modern" languages, where lexical analysis can
  54. omit the use of regular expressions, and often relies (as in the case of C) on
  55. type disambiguation. 
  56.  
  57. The original assertion (repeated above so that you might again read it) stated 
  58. that Lex `parses' regular expressions.  I take issue with the term `parses', 
  59. when in most cases, Lex doesn''t even need regular expressions, much less the
  60. abilities of a CFG parser (like YACC).
  61.  
  62. > >                                                                 But I sus-
  63. > >pect we differ when it comes to expecting most CS grads to be able to analyze 
  64. > >algorithms and derive their complexity, or decide whether a task in NP or 
  65. > >*P-complete, or compare partial or mu-recursive functions.
  66. > 
  67. > You certainly aren't saying that understanding NP-completeness is not
  68. > useful to a programmer, are you?   If you don't understand that certain
  69. > *very natural and often occurring* problems cannot be solved by anyone
  70. > today, you could spend a lot of time on pointless work.  And yes, NP-complete
  71. > problems come up often in issues related to operating systems and typical
  72. > "hacker work".
  73.  
  74. Actually, that is exactly what I am saying.  Very few non-PhD computer scientists
  75. (much less non-PhD programmers) will have the opportunity to discuss or decide
  76. the NP-ness of a computational problem.  Their employers simply will not rely
  77. on a non-authoritative source to decide the direction of work when theoretical
  78. issues are at issue.  Would you go to a nurse for an appendectomy when a
  79. surgeon is available, and you have much to lose if the practitioner isn't an
  80. authority?
  81.  
  82. I am not arguing that NP is unimportant.  As I said (clearly, I thought) NP
  83. and number theory are not appropriate subjects in an undergrad CS program
  84. given the value of so many other subjects, that by their omission, leave the
  85. CS degree holder less _appropriately_ educated than s/he should be.
  86. -- 
  87.  
  88. | Randy Crawford        crawford@mitre.org        The MITRE Corporation
  89. |                                                 7525 Colshire Dr., MS Z421
  90. | N=1 -> P=NP           703 883-7940              McLean, VA  22102
  91.