home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / doc / techrepo / 215 < prev    next >
Encoding:
Internet Message Format  |  1992-11-11  |  3.0 KB
  1. Path: sparky!uunet!think.com!ames!agate!darkstar.UCSC.EDU!golding
  2. From: jean@cse.ucsc.edu (Jean McKnight)
  3. Newsgroups: comp.doc.techreports
  4. Subject: UCSC revised TR: Sorting and Searching with a Faulty Comparison Oracle
  5. Date: 9 Nov 1992 23:10:29 GMT
  6. Organization: University of California, Santa Cruz (CE/CIS Boards)
  7. Lines: 58
  8. Approved: compdoc-techreports@ftp.cse.ucsc.edu
  9. Message-ID: <1dre7vINN2qk@darkstar.UCSC.EDU>
  10. NNTP-Posting-Host: oak.ucsc.edu
  11. Originator: golding@oak
  12.  
  13.           University of California at Santa Cruz
  14. Baskin Center for Computer Engineering and Information Sciences 
  15.  
  16. The following technical report is available electronically or as
  17. a paper copy.  Instructions for getting either follow the abstract.
  18.  
  19.  
  20. UCSC-CRL-92-15  (available electronically as ucsc-crl-92-15.ps.Z)
  21. SORTING AND SEARCHING WITH A FAULTY COMPARISON ORACLE
  22. Philip M. Long
  23. May 1992, revised November 1992, 6 pages (paper copy $5.00)
  24.  
  25. Abstract:  We study sorting and searching using a comparison oracle that
  26. ``lies.'' First, we prove that an algorithm of Rivest, Meyer, Kleitman,
  27. Winklmann and Spencer for searching in an n-element list using a
  28. comparison oracle that lies E times requires at most O(log n + E)
  29. comparisons, improving the best previously known bound of
  30. log n + E log log n + O(E log E).  A lower bound, easily obtained from
  31. their results, establishes that the number of comparisons used by their
  32. algorithm is within a constant factor of optimal.
  33.      We apply their search algorithm to obtain an algorithm for sorting
  34. an n element list with E lies that requires at most O(n log n + En)
  35. comparisons, improving on the algorithm of Lakshmanan, Ravikumar and
  36. Ganesan, which required at most O(n log n + En + E^2) comparisons.  A
  37. lower bound proved by Lakshmanan, Ravikumar and Ganesan establishes that
  38. the number of comparisons used by our sorting algorithm is optimal to
  39. within a constant factor.
  40.  
  41.  
  42. This technical report is available electronically through either 
  43. of the following methods:
  44. 1.  through anonymous ftp from ftp.cse.ucsc.edu, in /pub/tr. Log in 
  45.     as "anonymous", use your email address as your password, specify 
  46.     "binary" before getting the file.  Uncompress before printing.
  47. 2.  by mail to automatic mail server rnalib@ftp.cse.ucsc.edu.
  48.     Put this command on the subject line or in the body of the message:
  49.     @@ send ucsc-crl-92-15.ps.Z from tr
  50.     To get the index or abstract list:
  51.     @@ send INDEX from tr
  52.     @@ send ABSTRACTS.1992 from tr
  53.     To get the list of the tr directory:
  54.     @@ list tr
  55.     To get the list of commands and their syntax:
  56.     @@ help commands
  57.  
  58. Order paper copies from:  Technical Library, Baskin Center for Computer 
  59. Engineering & Information Sciences, UCSC, Santa Cruz  CA  95064.
  60. Purchase orders are not accepted.  Checks or money orders must be
  61. for U.S. dollars, payable through a U.S. bank, and made out to 
  62. "UC Regents".
  63.  
  64. Questions:  jean@cse.ucsc.edu
  65.  
  66. ===========================================================================
  67. Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
  68.         compdoc-techreports-request@ftp.cse.ucsc.edu
  69.  
  70.  
  71.