8. Here we explore the task of designing a fast algorithm to multiply two n-digit numbers x and y. For the purposes of this problem you are to assume that in a single instruction you can only multiply (or add) two 1-digit numbers. Note for this problem the number of digits, n, is our measure of the problem size. Useful Observations: Multiplying a number by a powerof 10 can be implemented as a single shift operation. Two n digit numbers can be added in O(n) time (by breaking it down into O(n) additions of two one digit numbers). In the regular algorithm we use for multiplying two n- digit numbers, every digit of the second number is multiplied by every digit of the first number, i.e. there are nmultiplication, plust we have do shifts and do additions of the shifted multiplication results and take care of carry overs. Thus the number of operation peformed T(n) > n, i.e. T(n) = N(n). (a) (10 pts) Let's now design a divide-and-conquer algorithm for this problem. I'll get you started. Divide x into t and xr where xe is the most significant [n/2] digits of x and Xis the least significant [n/2] digits of x. So for example if x = 783621 then xe = 783 and xy = 621. In the same manner divide y into ye and yr. Note that x = xl. 101n/21 + Xr and y = ye 10[n/21+ Yr, so T = ( 10[n/21a)(ge 10[n/21 + 3) How could you use this fact, and the fact that you recursively could get the answer of multiplying any two n/2-digit numbers, to get the answer to the original problem? Where does the recursion stop? Complete the multiplications of the expressions on the right side and you will obtain a formula where the product ry of the two n-digit numbers is computed by using only products of n/2-digit numbers, possible multiplications of powers of 10 and additions of at most n digit numbers. How could you use this fact, and give the duvide and concuew algorithm Multiply(x, y,n) for multiplying two n-digit numbers x and y, by first dividing the problem into 4 subproblems of computing products of n/2- digit humbers (figure out how many subproblems there are), recursively computing the product of the n2-digit numbers and fina;lly using the formula you obtained above to combine the results and obtain the value of the product of the originam n-digit numbers. Be careful and put a stoping condition of the recurrsive function. Complete the design of this algorithm, clearly describing it. Give the pseudo-code. You need not go into details about how to create Cl, Xr, ye, and y, but should discuss the worst-case time to do this splitting. Give the recurrence relation describing the time complexity and give its -complexity using the Master method. (b) (5 pts) Try to reduce the time complexity of your algorithm in part (b) by taking advantage of the fact that: Xeyr + Xrye = (xl Xr)(Yr ye) + Xeye + Xryr. Go back to the formula you computed in part a) and figure out how to avoid computing sepa- rately xeyr and Xryl, and get their sum directly instead. In particular, how many subproblems of size n/2 do you now need to solve in order to then combine them to obtain the solution to the original problem? Describe the algorithm you obtain by applying this fact. Give the pseudo-code. Do not just state what needs to be changed, give the whole algorithm. It is not very long and it would not kill you to write it. Give the recurrence relation describing the time complexity and give its O-complexity using the Master method. (c) (5 pts) Of the three algorithms you have developed which is best in terms of worst case asymp- totic time complexity? 8. Here we explore the task of designing a fast algorithm to multiply two n-digit numbers x and y. For the purposes of this problem you are to assume that in a single instruction you can only multiply (or add) two 1-digit numbers. Note for this problem the number of digits, n, is our measure of the problem size. Useful Observations: Multiplying a number by a powerof 10 can be implemented as a single shift operation. Two n digit numbers can be added in O(n) time (by breaking it down into O(n) additions of two one digit numbers). In the regular algorithm we use for multiplying two n- digit numbers, every digit of the second number is multiplied by every digit of the first number, i.e. there are nmultiplication, plust we have do shifts and do additions of the shifted multiplication results and take care of carry overs. Thus the number of operation peformed T(n) > n, i.e. T(n) = N(n). (a) (10 pts) Let's now design a divide-and-conquer algorithm for this problem. I'll get you started. Divide x into t and xr where xe is the most significant [n/2] digits of x and Xis the least significant [n/2] digits of x. So for example if x = 783621 then xe = 783 and xy = 621. In the same manner divide y into ye and yr. Note that x = xl. 101n/21 + Xr and y = ye 10[n/21+ Yr, so T = ( 10[n/21a)(ge 10[n/21 + 3) How could you use this fact, and the fact that you recursively could get the answer of multiplying any two n/2-digit numbers, to get the answer to the original problem? Where does the recursion stop? Complete the multiplications of the expressions on the right side and you will obtain a formula where the product ry of the two n-digit numbers is computed by using only products of n/2-digit numbers, possible multiplications of powers of 10 and additions of at most n digit numbers. How could you use this fact, and give the duvide and concuew algorithm Multiply(x, y,n) for multiplying two n-digit numbers x and y, by first dividing the problem into 4 subproblems of computing products of n/2- digit humbers (figure out how many subproblems there are), recursively computing the product of the n2-digit numbers and fina;lly using the formula you obtained above to combine the results and obtain the value of the product of the originam n-digit numbers. Be careful and put a stoping condition of the recurrsive function. Complete the design of this algorithm, clearly describing it. Give the pseudo-code. You need not go into details about how to create Cl, Xr, ye, and y, but should discuss the worst-case time to do this splitting. Give the recurrence relation describing the time complexity and give its -complexity using the Master method. (b) (5 pts) Try to reduce the time complexity of your algorithm in part (b) by taking advantage of the fact that: Xeyr + Xrye = (xl Xr)(Yr ye) + Xeye + Xryr. Go back to the formula you computed in part a) and figure out how to avoid computing sepa- rately xeyr and Xryl, and get their sum directly instead. In particular, how many subproblems of size n/2 do you now need to solve in order to then combine them to obtain the solution to the original problem? Describe the algorithm you obtain by applying this fact. Give the pseudo-code. Do not just state what needs to be changed, give the whole algorithm. It is not very long and it would not kill you to write it. Give the recurrence relation describing the time complexity and give its O-complexity using the Master method. (c) (5 pts) Of the three algorithms you have developed which is best in terms of worst case asymp- totic time complexity