home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / 3098 < prev    next >
Encoding:
Internet Message Format  |  1992-08-14  |  2.8 KB
  1. Path: sparky!uunet!crdgw1!ge-dab!puma.ATL.GE.COM!puma!sjameson
  2. From: sjameson@atl.ge.com (Stephen M Jameson)
  3. Newsgroups: comp.ai
  4. Subject: Re: Kolmogorov complexity
  5. Message-ID: <SJAMESON.92Aug13090132@fergie.atl.ge.com>
  6. Date: 13 Aug 92 13:01:32 GMT
  7. References: <1992Aug11.020517.18834@kronos.arc.nasa.gov>
  8. Sender: news@puma.ATL.GE.COM (USENET News System)
  9. Organization: General Electric Advanced Technology Labs
  10. Lines: 39
  11. In-Reply-To: wray@kronos.arc.nasa.gov's message of 11 Aug 92 02:05:17 GMT
  12.  
  13. In article <1992Aug11.020517.18834@kronos.arc.nasa.gov> wray@kronos.arc.nasa.gov (Wray Buntine) writes:
  14.  
  15. > >   I hope someone will follow up with some indication of whether anyone
  16. > >   has actually cared about the constant factors.
  17. > 
  18. > The constant factor is all important because in practice we only have small
  19. > sample sizes.  People who gloss over it usually have no experience at 
  20. > competitive implementation (implementing an algorithm that *outperforms* 
  21. > the *existing* competitors).
  22. > 
  23.  
  24. I attended undergraduate school at Johns Hopkins and graduate school at U of
  25. Maryland.  The CS cirriculum at Hopkins was quite theoretical, while the basic
  26. graduate cirriculum at UofM was eminently practical, and I had a couple of
  27. lessons in putting asymptotic complexity into perspective.  In my first
  28. graduate course at UofM, we were discussing various data structures/algorithms
  29. and reasons why one might prefer them and the professor indicated that option A
  30. was better because option B required 2 extra bytes per structure for an
  31. additional pointer or something like that.  My initial reaction was "who cares,
  32. it's a constant factor," but the professor was not impressed.
  33.  
  34. In the second course, we were discussing a one point an algorithm which
  35. required finding the mean of a set of numbers.  He pointed out that there is a
  36. worst-case O(n) algorithm known for doing this, but "only an idiot would use
  37. it" because it is horrendous to implement, and the one he suggested was far
  38. simpler, and gave O(n) performance except in pathological cases.  I gulped,
  39. having learned about the worst-case O(n) at Hopkins and having spent over a
  40. week implementing and debugging it for a program I wrote on a summer job.
  41.  
  42. --
  43. Steve Jameson                           General Electric Aerospace 
  44. sjameson@atl.ge.com                     Advanced Technology Laboratories
  45.                                         Moorestown, New Jersey              
  46. ****************************************************************************
  47. **  . . . but I do not love the sword for its sharpness, nor the arrow    **
  48. **  for its swiftness, nor the warrior for his glory.  I love only that   **
  49. **  which they defend . . .                                               **
  50. **    -- Faramir, "The Two Towers"                                        **
  51. ****************************************************************************
  52.