2. Consider an algorithm for integer multiplication of two n-digit numbers where each number is split into three parts, each with n/3 digits. (a) Design and explain such an algorithm, similar to the integer multiplication algorithm (i.e., Karatsuba's algorithm) presented in class. Your algorithm should describe how to multiply the two integers using only six multiplications on the smaller parts (instead of the straightforward nine) (b) Determine the asymptotic running time of your algorithm. Would you rather split it into two parts (with three multiplications on the smaller parts) as in Karatsuba's algorithm? (c) Suppose you could use only five multiplications instead of six. Then determine the asymptotic running time of such an algorithm. In this case, would you rather split it into two parts or three parts? (d) Challenge problem- this is optional, and not worth any points. Solving it will simply impress the in- structor. Find a way to use only five multiplications on the smaller parts. Can you generalize to when the two initial n-digit numbers are split into k parts, each with n/k digits? Hint: also consider multiplication by a constant, such as 2; note that multiplying by 2 does not count as one of the five multiplications. You may need to use some linear algebra