**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**