Homework 1: Due 9/7, 2005

1. 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 ≤ n-1, 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[n-1].
   

   Note that j could be 0 or n-1. Write a non-recursive 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.

2. What is the running time of the following code fragment as a function of n? Express your answer in the Big-Oh 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.

3. What is the running time of the following code fragment as a function of n? Express your answer in the Big-Oh 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.
   

4. 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 Big-Oh 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.
   

5. 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.