 Let A be an array of integers.
We say that A is bitonic if the elements of A
are first strictly increasing and after reaching a maximum value, they are
strictly decreasing.
More precisely, suppose that A has n elements.
Then for some index j, 0 ≤ j ≤ n1,
the array A is strictly increasing
up to element A[j], that is,
A[0] < A[1] < ... A[j]
and is strictly decreasing after that, meaning
A[j] > A[j+1] > ... > A[n1].
Note that j could be 0 or n1.
Write a nonrecursive java function called findMax that takes a bitonic
integer array of size n and returns the maximum element. The function
header should be
int findMax(int[] A, int n)
In the above, n refers to the size of A.
The function is required to run in O(log(n)) time, which means
you cannot just scan the entire array.
Instead, you should mimic the binary search algorithm.
What to submit: A printout of just the function findMax.

What is the running time of the following code fragment as a function of
n? Express your answer in the BigOh notation.
Show all the steps you took in coming up with your answer.
int i = n;
int j;
while(i >= 10)
{
i = i/3;
for(j = 0; j < n; j++)
System.out.println("In the inner loop");
}
What to submit: Your derivation of the running time of the above
code fragment.

What is the running time of the following code fragment as a function of
n? Express your answer in the BigOh notation.
Show all the steps you took in coming up with your answer.
for(i = 0; i < n; i++)
for(j = 0; j < i; j = j+10)
System.out.println("In the inner loop");
What to submit: Your derivation of the running time of the above
code fragment.

Your boss asks you to implement a data structure for maintaining a collection
of items that permits the operations insert, delete, and
search.
You decide to use an ordered array for your data structure.
Your boss then uses your implementation as part of an application that
starts with an empty collection of items and performs some insert operations
interspersed with some search operations.
After running the application for a while, your boss notices that the number
of insert operations is O(log n) and the number of search operations is
O(n), where n is the size of the input to the application.
Given this information, calculate the total worst case running time of all
the operations performed by your data structure, as a function of n.
Express your answer in the BigOh notation.
Watch out: The running time of each insert and search
depends on the number of elements in the collection and this is much smaller
than n.
What to submit: Your derivation of the total running time of the
operations performed on the data structure.

Write a recursive function to compute the binary equivalent of a given positive integer n.
The recursive algorithm can be described in two sentences as follows.
Compute the binary equivalent of n/2. Append 0 to it if n is even; append
1 to it if n is odd.
Use the following header for the function:
string binaryEquivalent(int n);
What to submit: A printout of just the function binaryEquivalent.