home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / lang / c / 20211 < prev    next >
Encoding:
Text File  |  1993-01-26  |  2.0 KB  |  51 lines
  1. Newsgroups: comp.lang.c
  2. Path: sparky!uunet!uunet.ca!canrem!dosgate!dosgate![peter.curran@canrem.com]
  3. From: "peter curran" <peter.curran@canrem.com>
  4. Subject: Neophyte C programmer needs HELP!
  5. Message-ID: <199326.4396.31043@dosgate>
  6. Reply-To: "peter curran" <peter.curran@canrem.com>
  7. Organization: Canada Remote Systems
  8. Distribution: comp
  9. Date: 26 Jan 93 07:07:51 EST
  10. Lines: 39
  11.  
  12.  
  13. In <1993Jan22.040237.9860@organpipe.uug.arizona.edu>,
  14.                         dave@cs.arizona.edu (Dave Schaumann) writes...
  15.  
  16. [after describing a non-dynamic-programming solution to a problem]
  17.  
  18. DS>BTW, for those wondering, dynamic programming is a method which
  19. DS>an algorithm that would otherwise have combinatorial time complexity
  20. DS>uses (typically a 2-dimensional) array to hold intermediate results.
  21. DS>Exploiting the fact that the combinatorial nature of the algorithm
  22. DS>results from computing the same functions over and over again, this
  23. DS>"saving of intermediate values" results in a polynomial-time algorithm.
  24.  
  25. DS>Those further interested by my (admittedly weak) description of
  26. DS>dynamic programming are advised to locate a good algorithms book.
  27.  
  28. To forestall confusion, it should be made clear that "dynamic
  29. programming" has nothing to do with "computer programming" (except
  30. that computers are usually used to implement solutions).  The
  31. idea was invented by Richard Bellman, sometime around the early
  32. 50's, I believe.  It is considered a field of Operations Research.
  33. It can produce feasible solutions to many otherwise-intractible
  34. optimization problems.
  35.  
  36. Two of the classic references are:
  37.  
  38. Applied Dynamic Programming, by Richard E. Bellman and Stuart E.
  39. Dreyfus, Princeton University Press, 1962.
  40.  
  41. Introduction to Dynamic Programming, George L. Nemhauser,
  42. John Wiley and Sons, 1966.
  43.  
  44. Peter Curran                          FidoNet: 1:229/15
  45. Usenet: peter.curran@canrem.com       RIME:    CRS (#118)
  46. ---
  47.  ■ DeLuxe² 1.25 #12339 ■ 
  48. --
  49. Canada Remote Systems  - Toronto, Ontario
  50. World's Largest PCBOARD System - 416-629-7000/629-7044
  51.