Write a linear running time complexity program in Java to find all the dominant elements in the given array of integers.

An element is a dominant element if is greater than all the elements to its right side. The rightmost element in the array is always a dominant element.

For example, in the array {16, 17, 4, 3, 5, 2}, dominant elements are 17, 5 and 2.

Important Notes:

· You must add the main method in your program in order to test your implementation.

· There are no data errors that need to be checked as all the data will be assumed correct.

· You can use the array of the previous example to test your program, however, I suggest that you also use other input arrays to validate the correctness and efficiency of your solution.

· Your program MUST be submitted only in source code form (.java file).

· A program that does not compile or does not run loses all correctness points.

Write a program in Java to implement a recursive search function

int terSearch(int A[], int l, int r, int x)that returns the location of x in a given sorted array of n integers A if x is present, otherwise -1.

The terSearch search function, unlike the binary search, must consider two dividing points

int d1 = l + (r - l)/3 int d2 = d1 + (r - l)/3

For the first call of your recursive search function terSearch you must consider l = 0 and r = A.length - 1.

Important Notes:

· For this problem you must add the main method in your program in order to test your implementation.

· There are no data errors that need to be checked as all the data will be assumed correct.

· Your program MUST be submitted only in source code form (.java file).

· A program that does not compile or does not run loses all correctness points.

(a) Implement a sublinear running time complexity recursive function in Java public static long exponentiation(long x, int n)

to calculate xn.

Note: In your function you can use only the basic arithmetic operators (+, -, *, %, and /).

(b) What is the running time complexity of your function? Justify.

(c) Give a number of multiplications used by your function to calculate x63.

Important Notes:

· For the item (a):

o you must add the main method in your program in order to test your implementation.

o there are no data errors that need to be checked as all the data will be assumed correct.

o your function you can use only the basic arithmetic operators (+, -, *, %, and

/).

o Your program MUST be submitted only in source code form (.java file).

A program that does not compile or does not run loses all correctness points.