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? 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
