Problem #1: (30 points) Given an array A of n distinct integer elements with the following property:

The first k elements (0 < k < n-1) are in strictly increasing sequence followed by the strictly decreasing sequence.

Example: A = {1, 3, 4, 5, 7, 14, 11, 7, 2, -4, -8}. It monotonically increases from 1 to 14, then decreases from 14 to -8

(a) Implement an efficient program in Java that, given an array with the previous property, determines whether a given integer is in the array.

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

Problem #2: (35 points) Given a sorted array of integer, A, with possible duplicate elements.

(a) Implement an efficient program in Java to find in A, the numbers of occurrences of the input value k. For example, in an array A = {-1, 2, 3, 5, 6, 6, 6, 9, 10} and k = 6, your program should return 3.

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

Problem #3: (35 points)

The Fibonacci sequence {fib}i1 is defined recursively as follows:

fib(1) = 1, fib(2) = 1 and, fib(n) = fib(n-1) + fib(n-2) for n 3.

The numbers in the Fibonacci sequence are called the Fibonacci numbers, for example: {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,}

(a) Implement a sub-linear time complexity function in Java. int fib(int n) that returns the nth Fibonacci number. Example: fib(9) returns 34.

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

1. Your Java program should print correctly the fib(250); fib(250) = 7896325826131730509282738943634332893686268675876375

2. In the resolution of this problem it is not allowed (and is not a good idea) to use the Binet's formula.

Please be thorough with explanation