Discrete Math.

Consider the following algorithmic procedure: Input :Non-negative integers x. y Output :Non-negative integer a r := x; S := y; a := 0; while it at: 0 do if 3 | s then r:=r+r+r; s:=s/3; end elseif3 | (s])then a:=a+r; r:=r+r+r; s:=(s1)/3; end else a := a+r+r; r := r+r+r; s := (s2)/3; end end returner Algorithm 1: Multiply We can model Algorithm 1 as a state machine whose states are triples of non-negative integers (335,0). The initial state is (x,y,0). The transitions are given by the rule 5 that for s > 0: (3r,sf3,a) if3 I s 5(r,s,a}= (3r,(sl)/3,a+r) if3|(sl) (3r, (5 2)]3,a + 2r) otherwise. 1. List the sequence of steps that appears in the execution of the algorithm for inputs x = 5 and y = 10. In other words, walk us through the algorithm starting from the initial state and ending with the nal state. 2. Verify the partial correctness of Algorithm 1. (3) Dene a predicate P on the states that you believe is a preserved invariant. (Suggestion: Think about why the loop condition is 5 =1: 0 and look at your sequence of steps from Part 1.) (b) Prove that P is a preserved invariant. (c) Apply the Invariant Principle to prove that if s = 0, then a = xy. 3. Verify that Algorithm 1 tem'rinates. (a) Dene a strictly decreasing derived variable on the states. (b) Prove that the algorithm terminates after at most 1 + log y executions of the body of the do statement. (Suggestion: Review the Fast Exponentiation program in [1].)