For all problems in which you are asked to develop an algorithm, write down the pseudocode, along with a rough argument for the correctness and an analysis of the running time. Please answer a, b, and c

Question 2: More divide, faster run time [15] Consider the problem of multiplying two n-digit integers. We saw in class (Karatsuba's algo- rithm) that dividing into two n/2 bit numbers and combining appropriately, we can compute the product in time 0(n1.585..). So we can wonder: can division into > 2 pieces help? Suppose we have two n-digit integers A, B. Assume for this problem that n is a power of 3. Split A into A1, A2 and 43, each having n/3 digits. So also, split B into B1, B2 and B3. If the numbers are in base 10, then as we saw, we can write A = 102n/3 3A +10/3 A2 + A3, B = 1021/3B, +10/3B2+Bz. Let p(z) be the polynomial Aj z2 + A2z + A3, and let q(z) = Bz2 + B2z + B3. Define r(2) = p(z)q(2). The degree of r(2) is 4, so r(z) = C1z4+C223 +03:2+Caz+Cs, for some coefficients C. (a) [1] Observe that the product of A and B is r(10/3). (Just a line of explanation is fine.) (b) [3] Show that once we know the Ci, assuming they are O(n) digits each, r(101/3) can be found in O(n) time. (e) [4] We thus need to find the C;. The trick is to find the values of r(2) at a few small values of z. Prove that for any z in the set {-2, -1,0,1, 2}, the value of r(z) can be computed in time T(n/3) +O(n), where T(n/3) is the time needed to multiply two n/3 digit numbers. Page 2 [Hint: use r(z) = p(2)9(2). You may also need the fact that since T(n) = O(n), we have T(1/3+1) =T(1/3) +0(n). ] (d) [4] The idea is now to use the value of r(2) at z={-2, -1,0,1,2} to find the C. Prove that this can be done by solving a system of linear equations, and moreover, that Cican be found in O(n) time. (e) [3] Write down the running time of the overall algorithm above as a recurrence of the form T(n) = ...T(n/3) +O(n) and find the closed form solution. (Provide a short explanation for your answer.) Moral: as long as the "conquer step is not too expensive, dividing a problem into smaller sub-problems typically helps. Question 2: More divide, faster run time [15] Consider the problem of multiplying two n-digit integers. We saw in class (Karatsuba's algo- rithm) that dividing into two n/2 bit numbers and combining appropriately, we can compute the product in time 0(n1.585..). So we can wonder: can division into > 2 pieces help? Suppose we have two n-digit integers A, B. Assume for this problem that n is a power of 3. Split A into A1, A2 and 43, each having n/3 digits. So also, split B into B1, B2 and B3. If the numbers are in base 10, then as we saw, we can write A = 102n/3 3A +10/3 A2 + A3, B = 1021/3B, +10/3B2+Bz. Let p(z) be the polynomial Aj z2 + A2z + A3, and let q(z) = Bz2 + B2z + B3. Define r(2) = p(z)q(2). The degree of r(2) is 4, so r(z) = C1z4+C223 +03:2+Caz+Cs, for some coefficients C. (a) [1] Observe that the product of A and B is r(10/3). (Just a line of explanation is fine.) (b) [3] Show that once we know the Ci, assuming they are O(n) digits each, r(101/3) can be found in O(n) time. (e) [4] We thus need to find the C;. The trick is to find the values of r(2) at a few small values of z. Prove that for any z in the set {-2, -1,0,1, 2}, the value of r(z) can be computed in time T(n/3) +O(n), where T(n/3) is the time needed to multiply two n/3 digit numbers. Page 2 [Hint: use r(z) = p(2)9(2). You may also need the fact that since T(n) = O(n), we have T(1/3+1) =T(1/3) +0(n). ] (d) [4] The idea is now to use the value of r(2) at z={-2, -1,0,1,2} to find the C. Prove that this can be done by solving a system of linear equations, and moreover, that Cican be found in O(n) time. (e) [3] Write down the running time of the overall algorithm above as a recurrence of the form T(n) = ...T(n/3) +O(n) and find the closed form solution. (Provide a short explanation for your answer.) Moral: as long as the "conquer step is not too expensive, dividing a problem into smaller sub-problems typically helps