Xref: utzoo comp.parallel:2371 comp.theory:1729
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!uwm.edu!linac!att!pacbell.com!ucsd!mvb.saic.com!ncr-sd!ncrcae!hubcap!usage.csd.unsw.oz.au!vast.eecs.unsw.oz!stevea
From: stevea@vast.eecs.unsw.oz.au (Steve Avery)
Newsgroups: comp.parallel,comp.theory
Subject: Parallel Algorithm for determing Mode
Keywords: parallel, algorithm, mode
Message-ID: <1991Mar27.133936.21302@hubcap.clemson.edu>
Date: 27 Mar 91 05:02:11 GMT
Sender: news@usage.csd.unsw.OZ.AU
Reply-To: stevea@vast.eecs.unsw.oz.au (Steve Avery)
Followup-To: comp.parallel
Organization: VLSI And Systems Technology Laboratory, EECS, UNSW, Australia
Lines: 30
Approved: parallel@hubcap.clemson.edu
To: comp-parallel%munnari.cs.mu.oz@munnari.OZ.AU


In a project I am currently undertaking, it is necessary to determine
the mode (ie. most frequent element) of a set of numbers (with fixed 
number of elements). There is no restriction on the type of algorithm
to be applied, other than it have time complexity O(log n), where n is
the number of elements. The set is originally unsorted, but of course
I can easily perform a sort in O(log n).

Is anyone aware of an algorithm I might employ to implement this function?
Is there any way to determine the frequency of the lements of a set in
O(log n) time?

Any references or ideas would be greatly appreciated.

Thanks in advance.

-steve

-------------------------------------------------------------------------------
Steve Avery                      | VLSI & Systems Technology Laboratory,
                                 | School of Computer Science & Engineering,
stevea@vast.eecs.unsw.oz.au      | University of New South Wales,
stevea@spectrum.cs.unsw.oz.au    | P.O. Box 1, Kensington, NSW, Australia, 2033
                                   

-- 
=========================== MODERATOR ==============================
Steve Stevenson                            {steve,fpst}@hubcap.clemson.edu
Department of Computer Science,            comp.parallel
Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell