Problem #1:

Given a sorted array of integer, A, with possible duplicate elements.

(a) Implement an efficient function 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 #2: The input is a square, N by N, matrix of nonnegative integers with possible duplicate elements. Each individual row is a strong decreasing sequence from left to right. Each individual column is a strong decreasing sequence from top to bottom.

Implement in Java an O(N) worst-case algorithm that decides if a number x is in the matrix and, if x is present, prints how many times.

Note: Please include in the header of your Java program (using comments) the main ideas of your algorithm.

Example of the 4 x 4 matrix: 26 22 17 10

19 16 12 7

12 10 7 4

5 4 2 1

Example of the output for this matrix and x = 7

Number 7 found in the matrix 2 times";

Problem #3: (a) Implement a sublinear running time complexity recursive function in Java

public static long exponentiation(long x, int n)

to calculate x^n.

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^63 .