Explained solutions to all the parts, please.

[8] 4. Krushing Karatsuba. Consider multiplying integers x and y, each of which is n digits long. (We will work with numbers in base 10, not in binary.) We may decompose the inputs as r = 22 - 102n/3 + 21 . 10/3 + xo y = y2 102n/3 + y1 - 107/3 + yo where x2,21,20, 42, 41, Yo are each n/3 digits long. The goal is to calculate z = r.y, which we may write as 2=2. = (22 - 102n/3 +21 - 10/3 + xo) - (y2 - 1020/3 + y1 - 10/3 + yo). [8] (a) Describe a recursive algorithm for integer multiplication based on the decomposition in (1). How much time does your algorithm take, ignoring the recursive calls? Briefly demonstrate that your algorithm runs in (n) time using a recurrence relation. You may assume that it O(n) time to add two numbers, each of which has O(n) digits. (This is via the long addition algorithm from elementary school.) You may ignore floors and ceilings. [2] (b) OPTIONAL BONUS QUESTION. Let's see if we can improve the runtime by computing the zi's more cleverly. Suppose we have computed the following values. L = 20 - Yo U1 = (22 +221 +4.00). (y2 + 2y1 + 4yo) u2 = 22 +31 +30). (y2 + yi+yo) U3 = (4.12 + 2x1 +20). (4y2 + 2y1 + yo) 44 = 22.42 Then, suppose we also compute the following values. a = 740/2 u1/2 + 5u2 43/2 + 744/2 b=-720/2+1/3 2u2 + 43/6 24 c=-up + u1/6 2u2 +43/3 7u4/2 How do these values relate to z? Describe and analyze an algorithm for integer multiplication whose runtime is asymp- totically better than Karatsuba's algorithm. You may additionally assume that subtraction of two n-digit numbers takes O(n) time. Also, it takes on time to divide an n-digit number by a single digit. [8] 4. Krushing Karatsuba. Consider multiplying integers x and y, each of which is n digits long. (We will work with numbers in base 10, not in binary.) We may decompose the inputs as r = 22 - 102n/3 + 21 . 10/3 + xo y = y2 102n/3 + y1 - 107/3 + yo where x2,21,20, 42, 41, Yo are each n/3 digits long. The goal is to calculate z = r.y, which we may write as 2=2. = (22 - 102n/3 +21 - 10/3 + xo) - (y2 - 1020/3 + y1 - 10/3 + yo). [8] (a) Describe a recursive algorithm for integer multiplication based on the decomposition in (1). How much time does your algorithm take, ignoring the recursive calls? Briefly demonstrate that your algorithm runs in (n) time using a recurrence relation. You may assume that it O(n) time to add two numbers, each of which has O(n) digits. (This is via the long addition algorithm from elementary school.) You may ignore floors and ceilings. [2] (b) OPTIONAL BONUS QUESTION. Let's see if we can improve the runtime by computing the zi's more cleverly. Suppose we have computed the following values. L = 20 - Yo U1 = (22 +221 +4.00). (y2 + 2y1 + 4yo) u2 = 22 +31 +30). (y2 + yi+yo) U3 = (4.12 + 2x1 +20). (4y2 + 2y1 + yo) 44 = 22.42 Then, suppose we also compute the following values. a = 740/2 u1/2 + 5u2 43/2 + 744/2 b=-720/2+1/3 2u2 + 43/6 24 c=-up + u1/6 2u2 +43/3 7u4/2 How do these values relate to z? Describe and analyze an algorithm for integer multiplication whose runtime is asymp- totically better than Karatsuba's algorithm. You may additionally assume that subtraction of two n-digit numbers takes O(n) time. Also, it takes on time to divide an n-digit number by a single digit