home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15209 < prev    next >
Encoding:
Text File  |  1992-11-18  |  1.3 KB  |  30 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!sun-barr!cs.utexas.edu!zaphod.mps.ohio-state.edu!darwin.sura.net!haven.umd.edu!decuac!pa.dec.com!nntpd2.cxo.dec.com!nntpd.lkg.dec.com!math.zk3.dec.com!edp
  3. From: edp@math.zk3.dec.com (Eric Postpischil)
  4. Subject: Re: comparison problem
  5. Message-ID: <1992Nov18.191533.23359@nntpd.lkg.dec.com>
  6. Sender: usenet@nntpd.lkg.dec.com (USENET News System)
  7. Reply-To: edp@math.zk3.dec.com (Eric Postpischil)
  8. Organization: Digital Equipment Corporation
  9. References:  <1992Nov18.161028.11906@seas.gwu.edu>
  10. Distribution: usa
  11. Date: Wed, 18 Nov 1992 19:15:33 GMT
  12. Lines: 16
  13.  
  14. In article <1992Nov18.161028.11906@seas.gwu.edu>, chihy@seas.gwu.edu
  15. (Chih-Hsun Yao) writes:
  16.  
  17. >Describe an algorithm that finds the largest and second largest integer in a
  18. >set of (2^m) integers using at most m+(2^m)-2 comparisons.
  19. >(Hint: Consider binary tree tournament)
  20.  
  21. Bigger hint:  Consider recursion.  Let f(k)=k+(2^k)-2 and suppose you
  22. had a procedure that could find the largest and second largest of a set
  23. of 2^k integers, but the procedure only worked for k < m.  Could you
  24. make a new procedure that worked for k=m?
  25.  
  26.  
  27.                                 -- edp (Eric Postpischil)
  28.                                 "Always mount a scratch monkey."
  29.                                 edp@rusure.enet.dec.com
  30.