Prove the correctness of the following algorithm- if, in fact, it is correct. Since it is recursive, we expect that mathematical induction will be used. Before launching into an attempted proof, you should first try to decide if it has a chance of being correct.

Multiply(y, z)

// Precondition: y and z are non-negative integers.

// Postcondition: Multiply(y, z) = yz.

// Note: c 2 is an integer - some constant we choose.

if z == 0

return 0

else

return Multiply(cy, floor (z/c)) + y . (z mod c)

(a) Do you believe the algorithm is correct for all pairs of values (y, z) which satisfy the precondition? Do not be concerned with issues of computer arithmetic such as overflow. If you think the algorithm is incorrect, give a counter-example which shows an incorrect result. If this is the case, how might you fix the algorithm? If you think the algorithm is correct provide some evidence in the form of a couple of simple invocations of the function carried through to conclusion with the correct product returned.

(b) Prove the original algorithm (or your corrected version if you do not think the original is correct) does successfully compute the product.