GATE CSE
{ $$\Phi $$ | $$\Phi $$ is a satisfiable propositional formula in CNF with at most two literal per clause}
For example, $$\Phi = \left( {{x_1} \vee {x_2}} \right) \wedge \left( {{x_1} \vee {{\overline x }_3}} \right) \wedge \left( {{x_2} \vee {x_4}} \right)$$ is a Boolean formula and it is in 2CNFSAT.The decision problem 2CNFSAT is
Consider the basic block given below.
a = b + c
c = a + d
d = b + c
e = d - b
a = e + b
The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are

The identifier of the output interface on which this packet will be forwarded is ______.
(i) TTL
(ii) Checksum
(iii) Fragment Offset
$$P1:$$ Four-stage pipeline with stage latencies $$1$$ $$ns,$$ $$2$$ $$ns,$$ $$2$$ $$ns,$$ $$1$$ $$ns.$$
$$P2:$$ Four-stage pipeline with stage latencies $$1$$ $$ns,$$ 1$$.5$$ $$ns,$$ $$1.5$$ $$ns,$$ $$1.5$$ $$ns.$$
$$P3:$$ Five-stage pipeline with stage latencies $$0.5$$ $$ns,$$ $$1$$ $$ns,$$ $$1$$ $$ns,$$ $$0.6$$ $$ns,$$ $$1$$ $$ns.$$
$$P4:$$ Five-stage pipeline with stage latencies $$0.5$$ $$ns,$$ $$0.5$$ $$ns,$$ $$1$$ $$ns,$$ $$1$$ $$ns,$$ $$1.1$$ $$ns.$$
Which processor has the highest peak clock frequency?
typedef struct treeNode* treeptr;
Struct treeNode
{
Treeptr leftMostchild, rightSibiling;
};
Int Dosomething (treeptr tree)
{
int value =0;
if (tree ! = NULL) {
If (tree -> leftMostchild = = NULL)
value=1;
else
value = Dosomething (tree->leftMostchild);
value = value + Dosometing (tree->rightsibiling);
}
return (value);
}
When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the 
int ProcessArray(int *listA, int x, int n)
{
int i, j, k;
i = 0;
j = n-1;
do
{
k = (i+j)/2;
if (x <= listA[k])
j = k-1;
if (listA[k] <= x)
i = k+1;
}
while (i <= j);
if (listA[k] == x)
return(k);
else
return -1;
}
Which one of the following statements about the function ProcessArray is CORRECT?
Consider the following relational schema:
employee (empId, empName, empDept )
customer (custId, custName, salesRepId, rating)
SalesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the following query return?SELECT empName
FROM employee E
WHERE NOT EXISTS (SELECT custId
FROM customer C
WHERE C.salesRepId = E.empId
AND C.rating <> 'GOOD');
employee (empId, empName, empAge)
dependent (depId, eId, depName, depAge)
Consider the following relational algebra query: $$\Pi_{empId}\:(employee) - \Pi_{empId}\:(employee \bowtie_{(empId=eID) \wedge (empAge \leq depAge)} dependent)$$The above query evaluates to the set of empIds of employees whose age is greater than that of
T1 : r1 (X) ; r1 (Z) ; w1 (X) ; w1 (Z)
T2 : r2 (X) ; r2 (Z) ; w2 (Z)
T3 : r3 (X) ; r3 (X) ; w3 (Y)
S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z); w3(Y); w2(Z); r1(Z); w1(X); w1(Z)
S2: r1(X); r3(Y); r2(Y); r3(X); r1(Z); r2(Z); w3(Y); w1(X); w2(Z); w1(Z)
Which one of the following statements about the schedules is TRUE?$$b$$ where $$x, a, b$$ are inputs and $$y$$ is the output.

Which one of the following digital logic blocks is the most suitable for implementing this function?
$$F\left( {P,Q} \right) = \left( {1 \oplus P} \right) \oplus \left( {P \oplus Q} \right) \oplus \left( {P \oplus Q} \right) \oplus \left( {Q \oplus 0} \right)$$
The equivalent expression for $$F$$ is
$$F\left( {P,\,Q,\,R,\,S} \right) = \sum {0,2,5,7,8,10,13,15} $$
The minterms $$2, 7, 8$$ and $$13$$ are 'do not care' terms. The minimal sum-of-products form for $$F$$ is _______

The above synchronous sequential circuit built using $$JK$$ flip-flops is initialized with $${Q_2}{Q_1}{Q_0} = 000.\,\,$$ The state sequence for this circuit for the next $$3$$ clock cycles is
$$P$$. For each such function it must be the case that for every $$i$$, $$f\left( i \right) = i$$
$$Q$$. For each such function it must be the case that for some $$i$$, $$f\left( i \right) = 1$$
$$R$$. Each such function must be onto.
Which one of the following id CORRECT?
$$x * x = y * y = x * y * x * y = y * x * y * x = e$$
where $$e$$ is the identity element. The maximum number of elements in such a group is ______.
P: Good mobile phones are not cheap
Q: Cheap mobile phones are not good
L: P implies Q
M: Q implies P
N: P is equivalent to Q
Which of the following about L, M, and N is Correct?
Process | Arrival Time | Burst Time |
---|---|---|
P1 | 0 | 12 |
P2 | 2 | 4 |
P3 | 3 | 6 |
P4 | 8 | 5 |
The average waiting time (in milliseconds) of the processes is ________.
1) Static allocation of all data areas by a compiler makes it impossible to implement recursion.
2) Automatic garbage collection is essential to implement recursion.
3) Dynamic allocation of activation records is essential to implement recursion.
4) Both heap and stack are essential to implement recursion.
C = 100;
for i = 0 to n do
for j = 1 to n do
{
Temp = A[ i ][ j ] + C ;
A[ i ][ j ] = A[ j ][ i ] ;
A[ j ][ i ] = Temp - C ;
}
for i = 0 to n do
for j = 1 to n do
output(A[ i ][ j ]);
$$\eqalign{ & {L_1} = \left\{ {{0^n}\,{1^n}\,\left| {n \ge } \right.0} \right\} \cr & {L_2} = \left\{ {wc{w^r}\,\left| {w \in \left\{ {0,\,1} \right\}{}^ * } \right.} \right\} \cr & {L_3} = \left\{ {w{w^r}\,\left| {w \in \left\{ {0,\,1} \right\}{}^ * } \right.} \right\} \cr} $$
Here, $${w^r}$$ is the reverse of the string $$w.$$ Which of these languages are deterministic Context- free languages?