edited by
4,772 views
21 votes
21 votes

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 by

3 Answers

Best answer
21 votes
21 votes

  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
5 votes
5 votes

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

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


Page - 1:

Page - 2:

Related questions

55 votes
55 votes
8 answers
1
Kathleen asked Sep 14, 2014
9,741 views
An $n \times n$ array $v$ is defined as follows:$v\left[i,j\right] = i - j$ for all $i, j, i \leq n, 1 \leq j \leq n$The sum of the elements of the array $v$ is$0$$n-1$$n...
33 votes
33 votes
8 answers
2
Kathleen asked Sep 14, 2014
10,854 views
Consider the following nested representation of binary trees: $(X \ Y \ Z)$ indicates $Y$ and $Z$ are the left and right subtrees, respectively, of node $X$. Note that $Y...