The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+10 votes
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.

   

asked in DS by Veteran (59.4k points)
edited by | 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 Answer

+10 votes
Best answer

  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.
answered by Boss (25.4k points)
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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,770 questions
41,729 answers
118,875 comments
41,381 users