Algorithms on Majority Problem

The main idea of the paper to give solutions to the majority problem where we are counting the number of occurrences of the majority element more than half of the total number of the elements in the input set and also for the number of occurrences of the element at least half of the total number of the elements in the input set. In the model we use elements that cannot be used to index into an array and there is no order for the input elements. Thus the outcome of the comparison of two elements can only be either equal or not equal and cannot be greater than or smaller than. The focus of the paper is to propose algorithms for these problems and analyze their time complexity. For both versions we show O(n) time algorithms. These results could be compared with cases whose elements can be ordered. The paper has also been modified to give the solution to the majority problem where the number of occurrences of an item exceeds (at least) more than n/k times in a multiset of n elements. In the model we used elements cannot be used to index into an array and there is no order for the input elements. The focus of this thesis is on the solutions and analyze the time complexity. We have achieved time O(nk) for this problem and we believe this is the optimal time complexity for this problem. Moreover an algorithm is suggested in this paper to find the majority elements which is only applicable for integers. Keywords: Algorithm, Majority, Complexity, Recursion, Group

Name thesis:degree_name

M.S.

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science (UMKC)

Grantor dc:publisher

University of Missouri--Kansas City

Year dc:date.issued

2017

Author dc:creator

• Tarafdar, Rajarshi

Advisor dc:contributor.advisor

• Han, Yijie, 1959-

Language dc:language.iso

en_US

Handle dc:identifier.uri

https://hdl.handle.net/10355/62441

OAI identifier oai:identifier

oai:mospace.umsystem.edu:10355/62441