home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15177 < prev    next >
Encoding:
Text File  |  1992-11-18  |  1.7 KB  |  41 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!seas.gwu.edu!chihy
  3. From: chihy@seas.gwu.edu (Chih-Hsun Yao)
  4. Subject: comparison problem
  5. Message-ID: <1992Nov18.161028.11906@seas.gwu.edu>
  6. Sender: news@seas.gwu.edu
  7. Organization: George Washington University
  8. Distribution: usa
  9. Date: Wed, 18 Nov 1992 16:10:28 GMT
  10. Lines: 29
  11.  
  12. Hi, everyone:
  13.         I got problem with following question:
  14.  
  15. Describe an algorithm that finds the largest and second largest integer in a
  16. set of (2^m) integers using at most m+(2^m)-2 comparisons.
  17. (Hint: Consider binary tree tournament)
  18.  
  19.         My problem is following: if I use the way of binary tree tournament,
  20. there is no doubt I can find the largest number at (2^m)-1 comparisons, but
  21. how can I find the second largest number at (m-1) comparisons?
  22.         My friend give me an example: the set {9,2,4,5,6,3,1,8}
  23. 9 compares to 2, 9 stands out. 4 compares to 5, 5 stands out. 6 compares to
  24. 3, 6 stands out. 1 compares to 8, 8 stands out. Then 9 compares to 5, 9 
  25. stands out. 6 compares to 8, 8 stands out. The final step, 9 compares to 8,
  26. 9 stands out. We get the largest number, and the total comparisons are
  27. 7 times = (2^m-1). To get the second largest number, we just use 8 to 
  28. compare to 6 and 5, just 2 comparisons = (m-1).
  29.         I find it only works in this example. If I put the 8 at the second
  30. position such as {9,8,2,4,5,6,3,1}, I can still get the largest number at 
  31. (2^m)-1 comparisons, but I cannot get the second largest number at m-1
  32. comparisons. As you see, I will lose the second largest number 8 at first 
  33. comparison. In that case, I have to recompare form the beginning, and the
  34. result will not be m+(2^m)-2 comparisons.
  35.         Any idea? Thanks in advance.
  36.  
  37.  
  38.                                                         Chih-Hsun Yao
  39.  
  40.  
  41.