home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15196 < prev    next >
Encoding:
Internet Message Format  |  1992-11-18  |  1.1 KB
  1. Path: sparky!uunet!destroyer!cs.ubc.ca!unixg.ubc.ca!unixg.ubc.ca!israel
  2. From: israel@unixg.ubc.ca (Robert B. Israel)
  3. Newsgroups: sci.math
  4. Subject: Re: comparison problem
  5. Date: 18 Nov 92 23:55:01 GMT
  6. Organization: The University of British Columbia
  7. Lines: 17
  8. Distribution: usa
  9. Message-ID: <israel.722130901@unixg.ubc.ca>
  10. References: <1992Nov18.161028.11906@seas.gwu.edu>
  11. NNTP-Posting-Host: unixg.ubc.ca
  12.  
  13. In <1992Nov18.161028.11906@seas.gwu.edu> chihy@seas.gwu.edu (Chih-Hsun Yao) writes:
  14.  
  15. >Hi, everyone:
  16. >        I got problem with following question:
  17.  
  18. >Describe an algorithm that finds the largest and second largest integer in a
  19. >set of (2^m) integers using at most m+(2^m)-2 comparisons.
  20. >(Hint: Consider binary tree tournament)
  21.  
  22. >        My problem is following: if I use the way of binary tree tournament,
  23. Sounds awfully like homework, so I'll just give a hint: the second largest
  24. is compared to the largest at some point in the tournament.
  25. -- 
  26. Robert Israel                            israel@math.ubc.ca
  27. Department of Mathematics             or israel@unixg.ubc.ca
  28. University of British Columbia
  29. Vancouver, BC, Canada V6T 1Y4
  30.