The mode of a set of numbers is defined to be the number that occurs most frequently in the set. The set {4,6,2,4,3,1} has a mode of 4.

a) Suppose we know that there is an (unknown) element that occurs (n/2) + 1 times in the set. Design an O(n) time algorithm to find the mode. Justify the time complexity of your algorithm.

b) Design an algorithm to compute the mode of a set of n numbers. You should try to solve the problem in smallest running time. Justify the time complexity of your algorithm.

Answer rating: 100% (QA)

a The algorithm that works in On is known as Moores Voting Algorithm Basic idea of the algorithm is that if we cancel out each occurrence of an element e with all the other elements that are different ... View the full answer