March 7, 2006: Seminar: Dr. Edward Reingold ''Determining Plurality''

Seminar Announcement

Determining Plurality

Dr. Edward Reingold
Illinois Institute of Technology
Tuesday March 7, 2006
11 a.m., Room 1000 SEO

Abstract:

Given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We prove that (c-1)(n-c)/2 color comparisons are necessary in the worst case to determine the plurality color and give an algorithm requiring (0.775 c + 3.6)n + O(c^2) color comparisons for c >= 9.

Host: Professor Tanya Berger-Wolf