599 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 | 599 views
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
@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