GATE IT 2005 | Question: 84b

Question

A sink in a directed graph is a vertex i such that there is an edge from every vertex $j \neq i$ to $i$ and there is no edge from $i$ to any other vertex. A directed graph $G$ with $n$ vertices is represented by its adjacency matrix $A$, where $A[i] [j] = 1$ if there is an edge directed from vertex $i$ to $j$ and $0$ otherwise. The following algorithm determines whether there is a sink in the graph $G$.

i = 0;
do {
    j = i + 1;
    while ((j < n) && E1) j++;
    if (j < n) E2;
} while (j < n);
flag = 1;
for (j = 0; j < n; j++)
    if ((j! = i) && E3) flag = 0;
if (flag) printf("Sink exists") ;
else printf ("Sink does not exist");

Choose the correct expression for $E_3$

• A. $(A[i][j] \ \&\& \ !A[j][i])$
• B. $(!A[i][j] \ \&\& \ A[j][i])$
• C. $(!A[i][j] \ \left | \right | A[j][i])$
• D. $(A[i][j] \ \left | \right | \ !A[j][i])$

Comments

Question is already bonkers for those who haven’t read the algorithm for finding universal sink before and then Gate professors also introduced the twist in the second part. It goes like this :

$(!A[i][j] \land  A[j][i])$

But by changing the meaning of the flag variable , they’ve asked the opposite of it.

---

Can anyone tell counterexample: Why Opt a is not correct for E3?

---

@harshitraj12 please refer to Link 

Answer 1

First read @Arjun sir's answer then trace and analyse like below. 

Answer 2

 

For better vizualization