🚀 go-pugleaf

          University of California at Santa Cruz
Baskin Center for Computer Engineering and Information Sciences 

The following technical report is available electronically or as
a paper copy.  Instructions for getting either follow the abstract.


UCSC-CRL-92-15  (available electronically as ucsc-crl-92-15.ps.Z)
SORTING AND SEARCHING WITH A FAULTY COMPARISON ORACLE
Philip M. Long
May 1992, revised November 1992, 6 pages (paper copy $5.00)

Abstract:  We study sorting and searching using a comparison oracle that
``lies.'' First, we prove that an algorithm of Rivest, Meyer, Kleitman,
Winklmann and Spencer for searching in an n-element list using a
comparison oracle that lies E times requires at most O(log n + E)
comparisons, improving the best previously known bound of
log n + E log log n + O(E log E).  A lower bound, easily obtained from
their results, establishes that the number of comparisons used by their
algorithm is within a constant factor of optimal.
     We apply their search algorithm to obtain an algorithm for sorting
an n element list with E lies that requires at most O(n log n + En)
comparisons, improving on the algorithm of Lakshmanan, Ravikumar and
Ganesan, which required at most O(n log n + En + E^2) comparisons.  A
lower bound proved by Lakshmanan, Ravikumar and Ganesan establishes that
the number of comparisons used by our sorting algorithm is optimal to
within a constant factor.


This technical report is available electronically through either 
of the following methods:
1.  through anonymous ftp from ftp.cse.ucsc.edu, in /pub/tr. Log in 
    as "anonymous", use your email address as your password, specify 
    "binary" before getting the file.  Uncompress before printing.
2.  by mail to automatic mail server rnalib@ftp.cse.ucsc.edu.
    Put this command on the subject line or in the body of the message:
	@@ send ucsc-crl-92-15.ps.Z from tr
    To get the index or abstract list:
	@@ send INDEX from tr
	@@ send ABSTRACTS.1992 from tr
    To get the list of the tr directory:
	@@ list tr
    To get the list of commands and their syntax:
	@@ help commands

Order paper copies from:  Technical Library, Baskin Center for Computer 
Engineering & Information Sciences, UCSC, Santa Cruz  CA  95064.
Purchase orders are not accepted.  Checks or money orders must be
for U.S. dollars, payable through a U.S. bank, and made out to 
"UC Regents".

Questions:  jean@cse.ucsc.edu

===========================================================================
Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
	    compdoc-techreports-request@ftp.cse.ucsc.edu