##### URI
https://hdl.handle.net/10355/62441
 dc.contributor.advisor Han, Yijie, 1959- dc.contributor.author Tarafdar, Rajarshi dc.date.issued 2017 dc.date.submitted 2017 Fall dc.description Title from PDF of title page viewed January 4, 2018 dc.description Thesis advisor: Yijie Han dc.description Vita dc.description Includes bibliographical references (page 34) dc.description Thesis (M.S.)--School of Computing and Engineering, University of Missouri--Kansas City, 2017 dc.description.abstract The main idea of the paper to give solutions to the majority problem where we are eng 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 dc.description.tableofcontents Algorithms for majority problem -- Counting majority elements at least N/K occurrences -- Finding majority integer element dc.format.extent viii, 35 pages dc.identifier.uri https://hdl.handle.net/10355/62441 dc.publisher University of Missouri--Kansas City eng dc.subject.lcsh Algorithms -- Computer programs dc.subject.lcsh Computational complexity dc.subject.other Thesis -- University of Missouri--Kansas City -- Computer science dc.title Algorithms on Majority Problem eng dc.type Thesis eng thesis.degree.discipline Computer Science (UMKC) thesis.degree.grantor University of Missouri--Kansas City thesis.degree.level Masters thesis.degree.name M.S.
﻿