Can anyone help with this particular problem? I'm not really sure how to go about it. I am adding my divide and conquer solution below and my pseudo code. "a" and "b" is just my integers which we can assume they are of n size and even. So we break them up into two piece as a "R" right side and a "L" left side. I can see why "Divide and Solve" seems out of place. My professor uses this annotiation. It's just explaining the reason behind the algorithm. Also, the book "Algorithm design" by Jon Kleinberg and Eva Tardos uses a similar explanation with binary numbers. However, they title it "Design the algorithm" and it's under the Divide and Conquer chapter,by the way that's page 238. The pseudo code is very similar to the one on the book. My professor asked to prove it by induction and I'm having a hard time. The base case is very simple when the length is 1 return 1. How do I state my induction hypothesis which is something like, assume P(k) is correct and then show P(k+1) holds.
Divide and Solve Solution
a = aL aR = aL * 10^(n/2) + aR
b = bL bR = bL * 10^(n/2) + bR
a * b = (aL * 10^(n/2) + aR) * (bL * 10^(n/2) + bR) = (aLbL)* 10^n + ( aLbR + aRbL) * 10^(n/2) + aRbR
However, aLbR + aRbL = (aL + aR) (bL + bR) - aLbL - aRbR
mult(a,b)
if len(a), len(b) = 1 return a * b
split a,b into aL bR
c1 = mult(aL, bL)
c2 = mult(aL + aR, bL + bR)
c3 = mult(aR, bR)
return c1*10^n + (c2 - c1 - c3) * 10^(n/2) + c3