GATE CSE 2015 Set 3 | Question: 49

Question

Suppose $c = \langle c[0], \dots, c[k-1]\rangle$ is an array of length $k$, where all the entries are from the set $\{0, 1\}$. For any positive integers $a \text{ and } n$, consider the following pseudocode.

DOSOMETHING (c, a, n)

$z \leftarrow 1$
for $i \leftarrow 0 \text{ to } k-1$
     do $z \leftarrow z^2 \text{ mod } n$
     if $c[i]=1$
           then $z \leftarrow (z \times a) \text{ mod } n$
return z

If $k=4, c = \langle 1, 0, 1, 1 \rangle , a = 2, \text{ and } n=8$, then the output of DOSOMETHING(c, a, n) is _______.

Comments

Is there some misprint? As there's no indentation between do and if. So we should consider them separately right? Then do loop won't end. So for question like this if a person challenges would it be considered?

---

 

In question, 

  do z←(z^2) mod n

it is normal statement equivalent to,

              z=(z^2) mod n  

Am i correct or it is do while loop… like above comment saying.

---

There needs to be a “while” for a do-while loop, or at least a condition.

This form of pseudocode notation → generally means assignment operator, unless and until specified.

You are correct.

Answer 1

Initially $k = 4$, $c = [1, 0, 1, 1]$, $a = 2$, $n = 8$.

Now let's iterate through the function step by step :

$z = 1$ (at the start of do-something)

$i = 0$ (start of external for loop)

In the do loop

$z = 1*1 % 8 = 1$ (non zero value so considered as true and continue)

$c[0] = 1$, so in the if clause, $z = 1*2 \% 8 = 2$

In the do loop

$z = 2*2 \% 8 = 4$ (since now $z = 2$) (non zero value so considered as true and continue)

$c[0] = 1$, so in the if clause, $z = 4*2 \% 8 = 0$

Now no need to check further :

Reason :  All the operations that update $Z$ are multiplicative operations and hence the value of $Z$ will never change from $0$.

Comments

@Anup , It is written in Pseudocode which follows Indentation .  it does not use brackets to show blocks. Given question follows pseudocode convention of CLRS. 

PFA from CLRS

---

yes indentation pattern

---

//The code in simplied form:- 
Do(c,2,8)
{
    z=1
    for(i=0;i<=3;i++)
    {
        z = pow(z,2)%8;
        if(c[i] == 1)
        {
            z = (z*2)%8;
        }
    }
    return z;
}

 

Answer 2

z=1  k = 4, c = [1, 0, 1, 1], a = 2, n = 8

now if we analyze the code we will get table like this Hence Ans is 0.

i	z
0	2
1	4
2	0
3	0

Answer 3

Answer is 0. By manually iterating through the steps by pencil and paper we can get this answer

Answer 4

we can do it mentally , at one stage value of z will be zero , beyond that , for any value of K it will be 0 only.

Ans :0