Question

Mystery(y, z: positive integer)

1 x=0

2 while z > 0

3       if z mod 2 ==1 then

4                x = x + y

5       y = 2y

6       z = floor(z/2)           //floor is the rounding down operation

7 return x

Simulate this algorithm for y=4 and z=7 and answer the following questions:

(3 points) At the end of the first execution of the while loop, x=_____, y=______ and z=_______.

(3 points) At the end of the second execution of the while loop, x=_____, y=______ and z=_______.

(3 points) At the end of the third execution of the while loop, x=_____, y=______ and z=_______.

(2 points) Value returned by the algorithm = __________________

(2 points) What does this algorithm compute?   _________________

Answer 1

Given Algorithm is

1 x=0

2 while z > 0

3       if z mod 2 ==1 then

4                x = x + y

5       y = 2y

6       z = floor(z/2)           //floor is the rounding down operation

7 return x

Input are : z = 7 and y = 4.

First Iteration -

Step 3 is (7 mod 2 == 1) is true as mod operator calculates reminder when 7 is divided by 2.

Step 4 is x = 0 + 4 = 4

Step 5 is y = 2 * 4 = 8

Step 6 is z = floor(7/2) evaluates to 3.

So at the end of first iteration x = 4, y = 8 and z = 3

Second Iteration -

Step 3 is (3 mod 2 == 1) is true as mod operator calculates reminder when 3 is divided by 2.

Step 4 is x = 4 + 8 = 12

Step 5 is y = 2 * 8 = 16

Step 6 is z = floor(3/2) evaluates to 1.

So at the end of Second iteration x = 12, y = 16 and z = 1

Third Iteration -

Step 3 is (1 mod 2 == 1) is true as mod operator calculates reminder when 1 is divided by 2.

Step 4 is x = 12 + 16 = 28

Step 5 is y = 2 * 16 = 32

Step 6 is z = floor(1/2) evaluates to 0.

So at the end of Third iteration x = 28, y = 32 and z = 0

Loop ends.

Finally the algorithm returns x value as 28 which is the multipled value of z(=7) and y (=4).