3,002 views

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;
}

1. 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?
2. Complete the following statement "The first count elements of __________contain values i such that set (_________________) has been called".
3. 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.

Question C. Can be understand by taking specific example though it is told for arbitrary
Question A's Solution's call to
Set(3)

Cz @ time
i=3
Count=2
q[2]=3
p[3]=2
....
and if set(3) is not called then it will always return false.

For the (c) part of the question which says us to show that $P\rightarrow Q$ .  Here P is set(i) has not been called for some i and Q is regardless of what p[i] contains, is_set(i) will return false.

So we have to prove just that if set(i) has not been called for some i then regardless of what p[i] contains, is_set(i) will return false. We do not concern ourselves to the case when set(i) has been called for some i .
So having assumed that set(i) has not been called, we can say that it can return true only when the first if condition and second condition are both false.
The first if condition will only be false when p[i]>0 && p[i] <= count. Let garbage value that p[i] contains is such that p[i]>0 && p[i]<= count. Now for this to return true second condition should be made false too which cannot be, because if p[i]<=count it means Array Q has been filled from index 1 to index count and q contain only the i values for which set(i) has been called , so there is no possibility for q[p[i]]=i because set(i) has not been called.

NOT GETTING THE C PART
edited

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

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.?

Subscribe to GO Classes for GATE CSE 2022

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.

by

@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?
edited

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

@
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.

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$.

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

Page - 1:

Page - 2:

1 comment

Nice explanation!! thanks :)