home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15149 < prev    next >
Encoding:
Text File  |  1992-11-17  |  3.9 KB  |  115 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!darwin.sura.net!spool.mu.edu!sgiblab!munnari.oz.au!bunyip.cc.uq.oz.au!marlin.jcu.edu.au!coral.cs.jcu.edu.au!spuler
  3. From: spuler@coral.cs.jcu.edu.au (David Spuler)
  4. Subject: Recurrence relations
  5. Message-ID: <spuler.722054177@coral>
  6. Sender: news@marlin.jcu.edu.au (USENET News System)
  7. Organization: James Cook University
  8. Date: 18 Nov 92 02:36:17 GMT
  9. Lines: 104
  10.  
  11.  
  12. Can anyone help me solve the following two recurrence relations?
  13. They are both derived from optimal binary trees and must be minimized.
  14.  
  15. I'm a PhD student in Computer Science, at James Cook University, Australia,
  16. and any help on these issues would improve my thesis.
  17.  
  18.  
  19. RECURRENCE A:
  20.   c[0] = 0
  21.   Generally, c[n] is minimum of 3 cases:
  22.     c[n] = c[n-1]            + alpha * n                      ; Case 1
  23.     c[n] = c[i]     + c[n-i] + alpha * n  (with 1<=i<n)       ; Case 2
  24.     c[n] = c[i - 1] + c[n-i] + beta * n   (with 1<=i<n)       ; Case 3
  25.  
  26.  
  27. RECURRENCE B:
  28.   c[0] = 0
  29.   Generally, c[n] is minimum of 2 cases:
  30.     c[n] = c[n-1]            + alpha * n                      ; Case 1
  31.     c[n] = c[i]     + c[n-i] + beta * n      (with 1<=i<n)    ; Case 2
  32.  
  33.  
  34. Both of these recurrences can be simplified to change the two parameters alpha
  35. and beta to use only one parameter:
  36.  
  37.   R = beta/alpha
  38.  
  39. Dividing all terms gives the new equivalent recurrences:
  40.  
  41. RECURRENCE A2:
  42.   c[0] = 0
  43.   Generally, c[n] is minimum of 3 cases:
  44.     c[n] = c[n-1]            + n                      ; Case 1
  45.     c[n] = c[i]     + c[n-i] + n       (with 1<=i<n)  ; Case 2
  46.     c[n] = c[i - 1] + c[n-i] + R * n   (with 1<=i<n)  ; Case 3
  47.  
  48.  
  49. RECURRENCE B2:
  50.   c[0] = 0
  51.   Generally, c[n] is minimum of 2 cases:
  52.     c[n] = c[n-1]            + n                      ; Case 1
  53.     c[n] = c[i]     + c[n-i] + R * n (with 1<=i<n)    ; Case 2
  54.  
  55.  
  56. CONJECTURE 1:  cut-offs for Case 1
  57. --------------------------------------
  58.  
  59. I have empirical evidence to support the conjecture that Case 1 is only
  60. chosen for small n, and for some cut-off point k, we have n>=k implying
  61. that only Case 2 (or 3 for recurrence A) is applicable.
  62. Can anyone help me prove this?
  63.  
  64. Is there an analytical formula for the cut-off?
  65. For recurrence B I have a theoretical approximate value of
  66.  
  67. k ~=~ 4R 
  68.  
  69. which I derived by noting that if my conjecture is true, then
  70.  
  71. n <= k  ====> c[n] = 1/R * n(n+1)/2
  72.  
  73.  
  74. CONJECTURE 2:  Choice of i for case 2/3
  75. --------------------------------------
  76.  
  77. I also have the conjecture backed up by empirical evidence that if Case 3 
  78. is chosen in Recurrence A, or Case 2 in Recurrence B, then the best choice of
  79. i is ceil(n/2)  (equivalently floor, doesn't matter which).
  80. However, Case 2 in Recurrence A seems not to always be i==n/2, although it
  81. is always reasonably close to that value.
  82. Can anyone help me prove this..
  83.  
  84. ---------------------------------------------------------
  85.  
  86. Perhaps this will help ......
  87. These recurrences are all generalizations of a simpler recurrence about which
  88. I posted a query a while ago.  That recurrence was:
  89.  
  90. c[0] = 0
  91. c[n] = c[n - 1]  + n         Case 1
  92. c[n] = c[i] + c[n-i] + n     Case 2
  93.  
  94. Thanks to a few great responses the exact solution was derived as:
  95.  
  96. c[n] = a(b+4) + (3b+6) 2^b,   where n is parameterized as:  n= a + 3*2^b
  97. equivalently:  c[n] = 2a + (b+2)n
  98.  
  99. This also helped prove similar conjectures to above, i.e that for n>=5 the
  100. best choice was always case 2 (i.e. the cut-off was k=4), and also that the
  101. best choice of i for case 2 was i=floor(n/2).
  102. This recurrence is the same as Recurrence B with R=1, or Recurrence A without
  103. Case 3.
  104.  
  105. ---------------------------------------------------------
  106.  
  107. More details are available on request.  I look forward to any useful responses
  108. with hints, tips, or even pointers to papers/books which will help me solve
  109. such minimization recurrences  (e.g. I've looked at Greene/Knuth's book
  110. "Mathematics for the Analysis of Algorithms" but my recurrences are more
  111. difficult than the one's they examine).
  112.  
  113. Thanks in advance,
  114. David Spuler
  115.