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

edited | 701 views
0
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.

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.
edited by
+2
@vijaycs ..

variable count is not static...the why the value of count persist...when calling set(I) with different values
+6
count must be global variable as both functions are using this. It is not  local to any function.
+1
@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?
+1

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

0
same doubt
0
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