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.
200 University Avenue West
Waterloo, ON N2L 3G1
Canada