Master’s Thesis Presentation • Algorithms and Complexity — Majority in the Three-Way Comparison Model

Azin Nazari, Master’s candidate
David R. Cheriton School of Computer Science

In this thesis, we study comparison based problems in a new comparison model called three-way, where a comparison can result in { >, =, < }. 

We consider a set of n balls with fixed ordered coloring. Particularly, we are interested in finding a ball of the majority color, the color that occurs more than half, when there are 2 colors, partition problem, where the goal is to determine groups of balls with the same color when there are 2 and 3 colors, respectively. 

We study these problems using both deterministic and randomized approaches.