[-] Show simple item record

dc.contributor.advisorHan, Yijie, 1959-
dc.contributor.authorTarafdar, Rajarshi
dc.date.issued2017
dc.date.submitted2017 Fall
dc.descriptionTitle from PDF of title page viewed January 4, 2018
dc.descriptionThesis advisor: Yijie Han
dc.descriptionVita
dc.descriptionIncludes bibliographical references (page 34)
dc.descriptionThesis (M.S.)--School of Computing and Engineering, University of Missouri--Kansas City, 2017
dc.description.abstractThe 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, Groupeng
dc.description.tableofcontentsAlgorithms for majority problem -- Counting majority elements at least N/K occurrences -- Finding majority integer element
dc.format.extentviii, 35 pages
dc.identifier.urihttps://hdl.handle.net/10355/62441
dc.publisherUniversity of Missouri--Kansas Cityeng
dc.subject.lcshAlgorithms -- Computer programs
dc.subject.lcshComputational complexity
dc.subject.otherThesis -- University of Missouri--Kansas City -- Computer science
dc.titleAlgorithms on Majority Problemeng
dc.typeThesiseng
thesis.degree.disciplineComputer Science (UMKC)
thesis.degree.grantorUniversity of Missouri--Kansas City
thesis.degree.levelMasters
thesis.degree.nameM.S.


Files in this item

[PDF]

This item appears in the following Collection(s)

[-] Show simple item record