This is a discerete maths assignment 0:[(3r,s/3,a)8(r, s,a) = {(3r, (s - 1)/3,a+r)if 3 | sif 3 | (s– 1)(3r, (s – 2)/3,a+ 2r) otherwise.1. List the sequence of steps that appears in the execution...

This is a discerete maths assignment

Extracted text: Writing Prompt Consider the following algorithmic procedure: Input :Non-negative integers x, y Output : Non-negative integer a r:= x; s:= y; a := 0; while s + 0 do if 3 | s then r:=r+r+r; s:= s/3; end else if 3 | (s-1) then а:3а+r; r:=r+r+r; s:= (s – 1)/3; end else а:3а+r+r; r:=r+r+r; s:= (s – 2)/3; end end return a Algorithm 1: Multiply We can model Algorithm I as a state machine whose states are triples of non-negative integers (r, s, a). The initial state is (x, y, 0). The transitions are given by the rule & that for s > 0: [(3r,s/3,a) 8(r, s,a) = {(3r, (s - 1)/3,a+r) if 3 | s if 3 | (s– 1) (3r, (s – 2)/3,a+ 2r) otherwise. 1. List the sequence of steps that appears in the execution of the algorithm for inputs x = 20 and y = 21. In other words, walk us through the algorithm starting from the initial state, showing the values of r, s, a after each transition, and ending with the final state. Note that for the rest of the prompt, you are considering arbitrary inputs x, y. The above example inputs are just to help you familiarize yourself with the algorithm. 2. Verify the partial correctness of Algorithm [I (a) Define a predicate P on the states that you believe is a preserved invariant. (Suggestion: Think about why the loop condition is s # 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 [] terminates. (a) Define 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).)