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
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)).
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)
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).
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"; }