Question

I posted the question for this and I want to make sure that this answers the question

1.a) The pseudo code for the closest pair problem is as illustrated below:

Closest pair (K, i, j)

input: Array K is indexed from i to j. closest pair returns the indices of the closest pairs.

diff = K[2] - K[1]   // This is the initial difference between the first two numbers. This is shown through the array and these differences. example: K[2] > K[1] else vice versa

loop from i to j

   loop from i to j

       //works only when I ≠ j

       if K[i] < K[j] and diff > K[j] - K[i]

       // Here, K[j] is greater than K[i] and is greater than the current value in diff

       then     diff = K[j] - K[i]

                  index1 = i

           index2 = j

       elseif K[j] < K[i] and diff > K[i] - K[j]

       // Here, K[i] is greater than K[j] and is greater than the current value in diff

       then     diff = K[i] - K[j]

                  index1 = i

           index2 = j

       else

       // Here, the values in K[i] and K[j] are same

       then   diff = 0

                  index1 = i

           index2 = j

return index1, index2

1.b) On examining the algorithm, the following points can be determined

•   The nested loop showa a complexity of O(n^2). Nested loops will show the Big-Oh notation, the value of which depends on the index.

•   The algorithm has only one input: n. It's time complexity is O(n^2), regardless of n, so there's no particular “best case” and "average case". Note same result can be in constant time.

2.a) The pseudo code for the binary search problem is as illustrated below:

binsrch(K, i, j, v)

input: array K indexed from i to j with items sorted from smallest to largest and item v. output: binsrch returns a location of item v in array K; if v is not found, -1 is returned.

if (i > j) then return (-1); m = (i + j)/2;

if (K[m] == v) then return(m);

if (K[m] < v)

then return(binsrch(K, m+1, j, v));

else return(binsrch(K, i, m-1, v));

2.b) On examining the algorithm, the following points can be deduced:

•   The non-recursive work takes constant time C.

•   The single recursive call has input half the size of the original.

•   The algorithm terminates when the array has size no larger than one.

Therefore, we have the following recurrence: T (n) = T (n/2) + C, and we conclude that T (n) = k · (C + 1), where k is the number of recursive calls. Also, we note that, if the size of array A is n, then (n/2k ) = 1, so k = lg n, and T (n) = (C + 1) · lg n.

Answer 1

1.

a)

Given solution is correct, because it checks each pair of items and checks whether current difference is less than previous difference then update difference as well as index1 and index2 value.

As it takes for all n(n+1)/2 pairs it takes O(n²) time, we can design a O(nlog n ) time algorithm as follows:

The idea to design algorithm to find closest pair of items in given array A is, first sort the array using quick sort in O(nlog n) time. Then for each consecutive pair of items in sorted array find the difference and output the pair with minimum difference.

Algorithm:(A[1,2,...,n],n)

1. sort A using Quick Sort .

2. min_difference=|A[2]-A[1]|

3. min_index=1

4. for i=2 to n-1 do

5. if(|A[i+1]-A[i]| < min_difference)

6.   do min_difference=|A[i+1]-A[i]|

7. min_index=i

8. print (A[i],A[i+1])

Above algorithm takes O(n log n) time is best,worst,average case.

b)

Given analysis is also correct for given algorithm.

2.

a) Given algorithm for binary search is correct, as it compares given item with middle element.

If it is equal to middle element it returns index ,.

if middle item is less than given element, then search in right half of array otherwise search in left half of array.

b)

Given analysis is correct, as after each recursive step problem size is reduced by 1/2, so algorithm takes O(log n) time.