{"id":{"repo_id":"umkc","oai_identifier":"oai:mospace.umsystem.edu:10355/62441"},"canonical_url":"https://search.dev.ndltd.org/etd/umkc/oai:mospace.umsystem.edu:10355/62441","repository":{"repo_id":"umkc","name":"University of Missouri - Kansas City","base_url":"https://mospace.umsystem.edu/oai/request"},"display":{"title":"Algorithms on Majority Problem","abstract":"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","abstract_html":"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","abstract_has_math":false,"creators":["Tarafdar, Rajarshi"],"institution":"University of Missouri--Kansas City","degree_name":"M.S.","degree_level":"Masters","degree_discipline":"Computer Science (UMKC)","degree_department":null,"school":null,"contributors":[],"advisors":["Han, Yijie, 1959-"],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017","date_published":"2017","updated_at":"2026-07-24T05:16:32Z","subjects":[],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/10355/62441","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Han, Yijie, 1959-"]},{"key":"dc:creator","label":"Author","values":["Tarafdar, Rajarshi"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2018-01-04T14:51:55Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2018-01-04T14:51:55Z"]},{"key":"dc:date.issued","label":"Date","values":["2017"]},{"key":"dc:publisher","label":"Institution","values":["University of Missouri--Kansas City"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science (UMKC)"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Missouri--Kansas City"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10355/62441"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Title from PDF of title page viewed January 4, 2018","Thesis advisor: Yijie Han","Vita","Includes bibliographical references (page 34)","Thesis (M.S.)--School of Computing and Engineering, University of Missouri--Kansas City, 2017"]},{"key":"dc:description.abstract","label":"Abstract","values":["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"]},{"key":"dc:title","label":"Title","values":["Algorithms on Majority Problem"]}]}],"canonical_facts":{"dc:contributor.advisor":["Han, Yijie, 1959-"],"dc:creator":["Tarafdar, Rajarshi"],"dc:date.accessioned":["2018-01-04T14:51:55Z"],"dc:date.available":["2018-01-04T14:51:55Z"],"dc:date.issued":["2017"],"dc:description":["Title from PDF of title page viewed January 4, 2018","Thesis advisor: Yijie Han","Vita","Includes bibliographical references (page 34)","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 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:identifier.uri":["https://hdl.handle.net/10355/62441"],"dc:language.iso":["en_US"],"dc:publisher":["University of Missouri--Kansas City"],"dc:title":["Algorithms on Majority Problem"],"dc:type":["Thesis"],"thesis:degree_discipline":["Computer Science (UMKC)"],"thesis:degree_level":["Masters"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Missouri--Kansas City"]},"updated_at":"2026-07-24T05:16:32Z"}