Suppose we are given two sorted arrays (nondecreasing from index 1 to index n) X[1] X[n] and Y [1] Y [n] of integers. For simplicity, assume that n is a power of 2. Problem is to design an algorithm that determines if there is a number p in X and a number q in Y such that p + q is zero. If such numbers exist, the algorithm returns true; otherwise, it returns false. We can consider every pair of numbers, one taken from X and other from Y , using a double-nested loop and solve this in O(n 2 ) time (a faster algorithm than the ones proposed here exists, but the homework is about divide and conquer). (1) We want to design a better algorithm using divide and conquer. Let (X, Y ) refer to the given problem. Let T(n) be the complexity of your algorithm when each of X, Y has n elements. Consider each of X, Y divided into two equal halves as shown below: X = X1 X2 Y = Y1 Y2 If such a pair p, q of numbers existed, then p has to be in one of X1, X2, and q has to be in one of Y1, Y2. Thus, we can determine the answer to problem (X, Y ) from answers to the following four smaller problems of half the size: (X1, Y1), (X1, Y2), (X2, Y1), and (X2, Y2)

(d) (15 pts) Present complete pseudocode for solving the problem (X[i...j], Y [k...l]) using divide and conquer by specifying details of the following. Invoking the algorithm as zeroSum (X, 1, n, Y, 1, n) solves the problem (X, Y ).

// Solves the problem (X[i ... j], Y[k ... l])

// Returns true if some p in X[i ... j] and some q in Y[k ... l]

// add up to zero; returns false otherwise

// Pre: (1) X and Y are in nondecreasing order

// (2) (j-i+1) = (l-k+1), i.e., X, Y have equal number of elements

boolean zeroSum (X[], i, j, Y[], k, l)

{

}

You must clearly specify the base case(s).