Order Description

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

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.