Problem #1

Implement a recursive search function in Java

int terSearch(int arr[], int l, int r, int x)

that returns location of x in a given sorted array arr[lr] 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

Problem #2

Write a method named palindromeAddNumber in Java that accepts an integer parameter and repeatedly adds the integer to the reversal of itself (the integer constructed by reversing the order of the digits) until the result is a palindrome (an integer that is the same when the order of its digits is reversed). Your method should print a single line of output containing the number of adds that were needed, followed by a space, followed by the palindrome that was computed.

For example, the call of palindromeAddNumber(195); should print: 4 9339 because:

195 (initial number)

+ 591 add #1

786

+ 687 add #2

1473

+ 3741 add #3

5214

+ 4125 add #4

9339 (resulting palindrome)

Problem #3

(a) Implement a sublinear running time complexity recursive function in Java

public static long exponentiation(long x, int n)

to calculate xⁿ.

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 x⁶³.