Analysis of execution costs for QuickSelect
by Nakama, Takehiko, Ph.D., THE JOHNS HOPKINS UNIVERSITY, 2009, 125 pages; 3392363

Abstract:

QuickSelect is a search algorithm widely used for finding a key of target rank in a file of keys. When the algorithm compares keys during its execution, it must operate on the keys' representations or internal structures, which were ignored by the previous studies that quantified the execution cost for the algorithm in terms of the number of required key comparisons. In this dissertation, we conduct analyses of running costs for the algorithm that take into account not only the number of key comparisons but also the cost of each key comparison. First we suppose that keys are independent and uniformly distributed in the unit interval (0, 1) and are represented as their binary expansions, and we derive exact and asymptotic expressions for the expected number of bit comparisons required by QuickSelect. We also establish a closed formula for the expectation that only involves finite summation and use it to compute the expected cost for various values of the target rank and the number of keys. Then we investigate execution costs for the algorithm applied to keys that are represented by more general sequences of symbols, and we identify limiting distributions associated with the costs. Further, we derive integral and series expressions for the expectations of the limiting distributions and use them to recapture previously obtained results on the number of key comparisons required by QuickSelect.

 
AdviserJames Allen Fill
SchoolTHE JOHNS HOPKINS UNIVERSITY
SourceDAI/B 71-01, p. , Mar 2010
Source TypeDissertation
SubjectsApplied mathematics; Computer science
Publication Number3392363
Adobe PDF Access the complete dissertation:
 

» Find an electronic copy at your library.
  Use the link below to access a full citation record of this graduate work:
  http://gateway.proquest.com/openurl%3furl_ver=Z39.88-2004%26res_dat=xri:pqdiss%26rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation%26rft_dat=xri:pqdiss:3392363
  If your library subscribes to the ProQuest Dissertations & Theses (PQDT) database, you may be entitled to a free electronic version of this graduate work. If not, you will have the option to purchase one, and access a 24 page preview for free (if available).

About ProQuest Dissertations & Theses
With over 2.3 million records, the ProQuest Dissertations & Theses (PQDT) database is the most comprehensive collection of dissertations and theses in the world. It is the database of record for graduate research.

The database includes citations of graduate works ranging from the first U.S. dissertation, accepted in 1861, to those accepted as recently as last semester. Of the 2.3 million graduate works included in the database, ProQuest offers more than 1.9 million in full text formats. Of those, over 860,000 are available in PDF format. More than 60,000 dissertations and theses are added to the database each year.

If you have questions, please feel free to visit the ProQuest Web site - http://www.proquest.com - or call ProQuest Hotline Customer Support at 1-800-521-3042.