home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / edu / 1651 < prev    next >
Encoding:
Internet Message Format  |  1992-09-14  |  3.4 KB
  1. Path: sparky!uunet!gatech!concert!duke!srt
  2. From: srt@duke.cs.duke.edu (Stephen R. Tate)
  3. Newsgroups: comp.edu
  4. Subject: Re: Programmers
  5. Message-ID: <716485859@pike.cs.duke.edu>
  6. Date: 14 Sep 92 15:51:00 GMT
  7. References: <BuDHvA.226@mentor.cc.purdue.edu> <PSU.92Sep11102557@ptero.cs.duke.edu> <1992Sep12.043133.6177@linus.mitre.org>
  8. Organization: Duke University Computer Science Dept.; Durham, N.C.
  9. Lines: 57
  10.  
  11. In article <1992Sep12.043133.6177@linus.mitre.org> crawford@church.mitre.org (Randy Crawford) writes:
  12. >In article <PSU.92Sep11102557@ptero.cs.duke.edu> psu@cs.duke.edu (Peter Su) writes:
  13. >>- The libraries have a routine called qsort, [...]
  14. >
  15. >This is an algorithm, not math theory.  To see the difference, pick up and 
  16. >compare any algorithm book with Knuth et al's Concrete Math or a text on 
  17. >computability.
  18.  
  19. And how can you possibly understand why quick sort works fast without
  20. knowing some discrete math?  Of course, if you want to want to just do
  21. things without understanding them, you don't need to know the math....
  22.  
  23. >>- There is a program called Lex that parses regular expressions, which
  24. >>were made up by a math theory bullshit guy named Kleene.  [...]
  25. >
  26. >Another specific algorithm.  I suspect your appreciation for lex is as a
  27. >useful program which illustrates some algorithm, not as a wonderful example 
  28. >of abstract algebra.  And BTW, lex doesn't do much with regular expressions.
  29. >It's sole responsibility is identification of lexical tokens.  Look to YACC 
  30. >for regexps and more.
  31.  
  32. You have just demonstrated the point!!!  You don't understand what lex
  33. has to do with regular expressions --- you say "it's sole responsibility
  34. is identification of lexical tokens".  What exactly do you think
  35. lexical tokens are????  They're regular expressions!!!!  Back to formal
  36. languages theory class for you!
  37.  
  38. YACC recognizes another form of language called "context free languages"
  39. (actually a subset of context free languages, but that's another issue).
  40. *NOONE* should be able to call themselves a competent computer programmer
  41. without understanding context free languages --- that's the basis of
  42. all programming languages, after all.
  43.  
  44. >                                                                 But I sus-
  45. >pect we differ when it comes to expecting most CS grads to be able to analyze 
  46. >algorithms and derive their complexity, or decide whether a task in NP or 
  47. >*P-complete, or compare partial or mu-recursive functions.
  48.  
  49. You certainly aren't saying that understanding NP-completeness is not
  50. useful to a programmer, are you?   If you don't understand that certain
  51. *very natural and often occurring* problems cannot be solved by anyone
  52. today, you could spend a lot of time on pointless work.  And yes, NP-complete
  53. problems come up often in issues related to operating systems and typical
  54. "hacker work".
  55.  
  56. As for the references to recursive function theory, I will agree with
  57. you there --- there's not much that is of day-to-day usefullness.  However,
  58. students should realize that there are functions that cannot be computed
  59. no matter how long you spend, and that some useful sounding things like
  60. the halting problem are non-computable.  It's what we call "being educated".
  61.  
  62.  
  63. -- 
  64. Steve Tate srt@cs.duke.edu | The reason why mathematics enjoys special esteem,
  65. Dept. of Computer Science  | above all other sciences, is that its laws are
  66. Duke University     | absolutely certain and indisputable, while those of all
  67. Durham, NC  27706   | other sciences are to some extent debatable. (Einstein)
  68.