22C:21: Computer Science II: Data Structures

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 ≤ jn-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.

    Solution:

    	public static int findMax(int[] A, int n)
    	{
    		int first = 0;
    		int last = n-1;
    		int mid;
    	
    		while(first <= last)
    		{
    			// if the current array has size 1
    			if(first == last)
    				return A[first];
    
    			// if the current array has size 2
    			else if(first == last-1)
    				return Math.max(A[first], A[last]); 
    			
    			// if the current array has size 3 or more
    			else
    			{
    				mid = (first + last)/2;
    			
    				if(A[mid-1] < A[mid] && A[mid] > A[mid+1])
    					return A[mid]; // we found the peak
    				else if(A[mid-1] < A[mid] && A[mid] < A[mid+1])
    					first = mid+1; // we are on an upward slope; go to the right
    
    				else if(A[mid-1] > A[mid] && A[mid] > A[mid+1])
    					last = mid-1; // we are on a downward slope; go to the left
    				else
    					return Integer.Integer.MIN_VALUE ; //this implies A is not bitonic
    			} // end of else
    		} // end of while
    		return Integer.Integer.MIN_VALUE; // the program should never reach here
    	} // end of function
    

  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.

    Solution: The body of the inner-loop executes n times, for each value of i. The running time of the body of the inner loop is O(1). Therefore, the running time of the inner loop is An + B, for some constants A and B. The assignment statement just before the inner loop, "i = i/3" also runs in O(1) time and therefore, we can conclude that the body of the outer loop runs in An + C time, where A and C are some constants. We just need to figure out how many times the body of the outer-loop is executed. Each time the body of the outer-loop is executed, the value of i shrinks by a factor of 3. This means that in log_3(n) steps, i falls below 10 after having started at n. Therefore, the running time of the outer-loop is O(n log n). The statements before the outer-loop run in O(1) time and therefore the overall running time is O(n log(n)).

  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.

    Solution: For each value of i, the outer-loop index, the body of the inner-loop executes i/10 times. Each execution of the body of the inner-loop takes O(1) time. So for each value of i, the running time of the inner-loop is A(i/10) + B. To calculate the running time of the entire code fragment, we simply need to sum up A(i/10) + B over all values of i = 0, 1, ..., n-1. This simplifies to

    	A/10 (0 + 1 + ... + (n-1)) + Bn = A n(n-1)/20 + B n = O(n^2)
    

  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.

    Solution: Since there are O(log n) insert operations, there are at most O(log n) elements in the ordered array. In the worst case, each insert takes time that is linear in the number of elements in the array. Therefore, each insert takes O(log n) time. There are O(log n) inserts and therefore the total time to insert is O((log n)^2). The search operation is implemented as a binary search, since the data is ordered. Therefore, in the worst case, search takes time that is logarithmic in the size of the array. Since the size of the array is O(log n), the worst case running time of search is O(log(log(n))). There are O(n) searches and therefore the total running time of search is O(n log(log(n))). The total running time of the insert operations plus the search operations is O(n log(log(n))) because n log(log(n)) grows faster than log^2(n).

  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.

    Solution:

    		public static String binaryEquivalent(int n)
    		{
    			if (n == 0)
    				return "0";
    			if (n ==1) 
    				return "1";
    			if (n % 2 == 0) 
    				return binaryEquivalent(n/2) + "0";
    			else 
    				return binaryEquivalent(n/2) + "1";
    		}