Hi, please provide me a detailed answer for the problem below, thank you!

5. Read the Repeated Squaring, Binary Search handout on Moodle. Consider Algorithm 2 below for the multiplication of natural numbers: Algorithm 2 Algorithm for the multiplication of natural numbers procedure MULTIPLY(y, z) C-0 while z > 0 do if z mod 2 = 1 then x + x + y y + 2y z+ [2/2] return x (a) (10 pts) Prove that the algorithm is correct: state and prove a useful loop invariant, check initialization condition and derive correctness as a consequence of the loop invariant at the termination of the loop. (b) (5 pts) Let M(x,y) denote the number of times line y + 2y gets executed. Give a closed-form expression for M(x,y). Prove your