Please note: This master’s thesis presentation will take place online.
Ben Baral, Master’s candidate
David R. Cheriton School of Computer Science
Supervisor: University Professor J. Ian Munro
In this thesis, we study the majority problem using ordered comparisons under the Las Vegas randomized algorithm model. The majority problem asks whether a given set of n elements, each with some colour, has a colour which appears on more than half of the elements. We focus on algorithms for this problem whose fundamental operation is to compare two elements, and in particular the comparison returns one of {<, =, >}. Additionally, we are interested specifically in Las Vegas randomized algorithms for this problem, which solve the problem correctly in all cases but whose running time is a random variable. Interestingly, most previous work studying this problem considers a different model where comparisons return just whether two elements are equal or not, instead of providing ordered information.
Our contribution is a novel Las Vegas algorithm that uses only n + o(n) comparisons in the expectation, compared to 7n/6 + o(n) comparisons required in the expectation by the previous best algorithm for this problem.
To join this master’s thesis presentation on Zoom, please go to https://uwaterloo.zoom.us/j/96426812538?pwd=WSt6TE1lQysrZjk2UTl5SjRBUmhFdz09.
200 University Avenue West
Waterloo, ON N2L 3G1
Canada