Describe algorithms that solve each of the following problems. In each case, you
ID: 3665219 • Letter: D
Question
Describe algorithms that solve each of the following problems. In each case, you can modify, adapt, and/or combine one or more familiar algorithms to solve the problem. Describe your algorithms in precise English, not with code. Explain why your algorithm meets the specified complexity bound. Given a non-empty array A of length n, determine its length. The only operation you are allowed to perform on the array is to attempt to access A[i] for nonnegative integers i. Each such attempt will either succeed (if i is less than the length of A) or result in an out of bounds exception (otherwise). Your algorithm should be 0(log n). Given an integer array A of length n, create a new integer array B containing no duplicates such that a number appears in B if and only if it appears in A . Your algorithm should be 0(n log n). Given an integer x and an array A of n integers, find two elements of A that add up to x, or report that no such pair exists. Your algorithm should be 0(n log n).Explanation / Answer
Answers):
1). The length ‘n’ of the array is not known. To find ‘n’, step through the array A[i] taking i = 1, 2^1, 2^2, 2^3, …, 2^m until you get the ArrayIndexOutofBounds error. Then binary search between 2^(m-1) and 2^m until you get the frontier where the error no longer appear. This will be the length ‘n’ of the array. This takes O(log n).
2). For every element in array A, perform a binary search in array B, if the search is un-successful then insert the element into array B, else continue with other elements. This will take O(n log n). O(n) for every elements in array A and O( log n) for every binary search , overall it takes O(n log n).
3). Sort the array using quick or merge sort, this will take O(n log n). Then for each sum ‘x’ in array A, perform binary search. This will take O(n log n). So, overall, it will take O(n log n).