Consider two sets A and B, each having n integers in the range from 0 to

10n. We wish to compute the Cartesian sum of A and B, defined by: C = x + y : x A and y B.

We want to find the set of elements in C and also the number of times each element of C is realized as a sum of elements in A and B. Show that the problem can be solved in O(nlogn) time by reducing it to the polynomial multiplication algorithm. Use the polynomial multiplication algorithm as a black-box without modifying it. You need to explain what input you put into the polynomial multiplication algorithm and what you do with the output to get the solution to the Cartesian Sum problem. Dont give code.

Example: for A = [1,2,3] and B = [2,3] then C = [3,4,5,6] and the solution to the Cartesian Sum problem is:

3 appears and is obtainable in 1 way 4 appears and is obtainable in 2 ways 5 appears and is obtainable in 2 ways 6 appears and is obtainable in 1 way.

You dont have to print your output in that form, whatever form that is convenient is OK, e.g., as a vector c = (0, 0, 0, 1, 2, 2, 1). Just make sure to explain the format of your output and how it solves the problem. You can assume each number between 0 and 10n appears at most once in A and at most once in B (although this doesnt matter for the solution, its almost the same algorithm to solve the problem when the sets A and B might contain elements multiple times).

Let P(x) = p0 +p1x+p2x2 ++pmxm and let Q(x) = q0 +q1x+q2x2 + + qmxm be the pair of polynomials that will be used in the polynomial multiplication algorithm. Part (a): Explain how you define the coefficients of these polynomials P(x) and Q(x) from the input sets A = {a1,...,an} and B = {b1,...,bn}.

Part (b): You run the polynomial multiplication algorithm on P(x) and Q(x). You get the coefficients r0,r1,...,r2m of the polynomial R(x) where R(x) = P (x) Q(x). Explain how you go from these coefficients to get the solution to the Cartesian sum problem.