Assignment 

Data structures and algorithms:

For each of your solutions please provide a short explanation as to why you
believe your solution works properly.
1 Most frequently occurring number
Design an O(n) algorithm whose input is a sorted array A of integer numbers.
The program should print the most frequent element of A. For example, in
the array A = [1; 2; 2; 5; 7; 7; 7; 8], 1 occurs once, 2 occurs twice, 5 occurs once,
7 occurs three times,and 8 occurs once. Hence, the most frequently occurring
element is 7. If there are two or more most frequently occurring elements, the
algorithm can be print anyone of them (e.g. the first one).
2 Number of distinct elements in a sorted array
Design an O(n) algorithm whose input is a sorted array A of integer numbers.
The program should print the number of distinct elements of A. For example,
in the array A = [1; 2; 2; 5; 7; 7; 7; 8], as in the previous section, the number of
distinct elements is 5 which are 1; 2; 5; 7; 8.
3 Number of distinct elements in an arbitraryarray
Design an O(n2) algorithm whose input is an array A of integer numbers (not
necessarily sorted). The program should print the number of distinct elements
of A.

4 Three distinct elements of a sorted array

Design an O(log n) algorithm whose input is a sorted array A of integer numbers.
The algorithm should print YES if A contains at least 3 distinct numbers and
NO otherwise.

Solution