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 ← 1
for i ← 0 to k-1
     do z ← z² mod n
     if c[i]=1
           then z ← (z × a) 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

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.

---

At first glance this question might look very intimidating in exam and many would leave without reading..

---

the for loop runs as :-

z←1
for i←0 to k−1

 {
     do z←z2 mod n
     if c[i]=1
           then z←(z×a) mod n

}
return z

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

May be this works ...........

Comments

nice explaination

Answer 4

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

Answer 5

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

Answer 6

this is the algorithm to find  a^c mod n.

here a =2, c =(1011)₂ = 11, n=8

hence 2¹¹ mod 8 = 0

Comments

How can u assume this thing ?

---

Any Proof ? Which Text Book It From ? @y mint