GATE CSE 2000 | Question: 15

Question

Suppose you are given arrays $p [1......N]$  and $q [1......N]$ both uninitialized, that is, each location may contain an arbitrary value), and a variable count, initialized to $0$. Consider the following procedures $set$ and $is\_set$:

set(i) { 
    count = count + 1; 
    q[count] = i; 
    p[i] = count; 
} 
is_set(i) {
    if (p[i] ≤ 0 or p[i] > count)
        return false; 
    if (q[p[i]] ≠ i)
        return false;
    return true;
}

• A. Suppose we make the following sequence of calls: 
  $set(7)$; $set(3)$; $set(9)$; 
  After these sequence of calls, what is the value of count, and what do $q[1], q[2] ,q[3], p[7], p[3]$ and $p[9]$ contain?
• B. Complete the following statement "The first count elements of __________contain values i such that set (_________________) has been called".
• C. Show that if $set(i)$ has not been called for some $i$, then regardless of what $p[i]$ contains, $is\_set(i)$ will return false.

Comments

Deepanshu

Look at the C part carefully. They are saying that if set(i) has not been called for some i, then regardless of what p[i] contains is_set(i) will return false. when we will not call set(i) means that a particular index i will contain some arbitrary value(elements of array p can only be filled when call set function on that particular index), since we are not calling set function for some I that means those I indexes of array p may have contain some arbitrary value. Now if we call  is_set function on that index that means we have to execute the first line of is_set function

if (p[i] ≤ 0 or p[i] > count)

we can not make this expression false because p[i] is containing some arbitrary value and that arbitrary value will be either 0 or some positive or some negative value.

for making this expression false, we have to make p[i] > 0 true and p[i] <=0 true, but we can not do this right because it is not valid So is_Set will always return false

---

@akash.dinkar12-I think your statement

if(p[i] $\leq$0 or p[i] > count)-we cannot make this expression false. is incorrect.

After statements in part (a) have been executed, count contains 3.

Suppose I call is_set(6) and p[6] contains say 2, then above if condition becomes false.

---

FOR LAST PART CAN WE DO LIKE LET i=some value 6 and p[6]=garbage suppose -10 then without calling set(i) it will return false.?

Answer 1

1. 
   Initially $count= 0$;
   
   When we call $set(7)   -  count=1,  q[1] =7,  p[7]= 1$;
   when we call $set(3)    -  count=2,  q[2]=3,  p[3] =2$;
   when we call  $set(9)   - count=3,   q[3]=9,   p[9] = 3$;
    
2. Ans-  "The first count elements of  $array \ q$ contain values $i$ such that $set(i)$ has been called".
    
3. If $set(i)$ has not been called for some $i$, then  regardless of what $p[i]$ contains, When we call $is\_set(i)$ then 

if (q[p[i]] ≠ i)
      return false;

will always execute, because if set(i) is not called then p[i] ≠ count(any) and for then same count q[count] ≠ i. So if statement will be true and will return false.

Comments

@vijaycs ..

variable count is not static...the why the value of count persist...when calling set(I) with different values

---

count must be global variable as both functions are using this. It is not  local to any function.

---

@bikram sir, Isn't there a slightest possibility that the garbage value that the arrays contain are in such a way that is_set becomes true?

---

I am having the same doubt.

if (q[p[i]] ≠ i)
        return false;
will always execute, because if set(i) is not called then p[i] ≠ count(any) and for then same count q[count] ≠ i. So if statement will be true and will return false.

may be p[5] contains 5 as garbage value and q[5] also contains 5.So the statement can become false.We cannot assume what garbage can contains and what it cannot contain as assumed in answer.

I think the first if will always be true.

if (p[i] ≤ 0 or p[i] > count)
        return false; 

If p[i] is <=0 then first condition is true and if is true. If p[i]>0 ,then we know count is zero and hence second condition will be true.SO whatever p[i] may contain it will always enter in this if and return false.Please correct me if wrong 

---

same doubt

---

We can get out of first IF only if p[i]>0 &&p[i]<= count

lets say i= 5 we r checking for 3rd question

so if p[5]< count let's suppose, for that to happen some other value has already been called with set(i) and incremented count more than p[5] because count increases only on calls to set(i)  so q[p[i]]!=i become it's been set with other value to increase count to have condition p[5]< count hence false returned

case 2 (this is a little tricky)

P[5]= count=7 suppose

than that means count has same value as p[5] so so in array q has been filled with 7 values and set(i) called 7 times to have value of p[5] as 7 we have to call set(5) at after count =6 at 7th call to set(I) becoz this can only set p[i] to 7 which is not possible acc to question hence false returned

---

@Laconia can you please elaborate case 2, I didn't get it.

---

@rahul sharma 5  :-
The case you say :- "may be p[5] contains 5 as garbage value and q[5] also contains 5.So the statement can become false.We cannot assume what garbage can contains and what it cannot contain as assumed in answer"

This could not be so because if q[5] has to be 5 then set(5) should have been called because array q values can only be from the list of i values for which set(i) has been called. Say for example, that q[5]=5 then that means set(5) must have been called that is why q[5]=5. But the question says - "if set(i) has not been called for some i, then regardless of what p[i] contains, is_set(i) will return false" which means we have to just prove this statement for the case when set(5) hasn't been called.

---

@skywalker_19:-  This could not be so because if q[5] has to be 5 then set(5) should have been called because array q values can only be from the list of i values for which set(i) has been called. 

Question says q is uninitialized.So it q[5] may contain 5 as garbage value.It is not necessary that it will contain 5 only when we set this.In c you print any variable without assigning value it print garbage,it means it can be anything

---

@rahul sharma 5 
I have also the same doubt as yours.

---

count is not explicitly mentioned as static….should we assume it as static ?

---

The problem boils down to reverse mapping . Key( count ) → Value( i ) . The array q acts as a lookup table. Now the second part is we are using another lookup table Key (i) → Value ( count ), The array p is taking care of that. This is crux of the problem.

---

I have a doubt on Part C of the answer

As given in question p and q are unintialized and may contain an arbitrary value .

What if those garbage values are like this

P[4] = 4

Q[4] = 4

---

what if we assume it is globally declared

Answer 2

Trying to explain the (c) part.

 

We want to show that if set(i) was not called, then is_set(i) will return false. First of all, let us understand what each variable is computing. $count$ is keeping track of how many times the set() method has been called till now. For $1 \leq k \leq count$, $q[k]$ will keep track of the $i$ that was used to invoke set() method for the $k$-th time. Suppose set(i) has not been invoked till now. Then the following is true.

$q[k] \neq i$ for any $1 \leq k \leq count$.

Now the array entry $p[i]$ will either contain a garbage value or the value of $count$ when set(i) was invoked the last time. Since we assumed that set{i) has not been called $p[i]$ is a garbage value.

• Case 1: Clearly if $p[i] < 1$ or $p[i] > count$, then it is definitely a garbage value. This is taken care of the first check of the is_set() method.
   
• Case 2: $p[i]$ is a garbage value that lies between $1,\ldots,count$. But recall that $q[k] \neq i$ for any $1 \leq k \leq count$. Hence $q[p[i]] \neq i$.

Comments

Best explanantion.

Answer 3

Just Trying to explain the PART (C),
See the following attached image


Page - 1:

Page - 2:

Comments

Nice explanation!! thanks :)