GATE CSE
int j, n;
j=1;
while(j <= n)
j = j * 2;
The number of comparisons made in the execution of the loop for any n > 0 is:int gcd(n,m)
{
if (n % m == 0) return m;
n = n % m;
return gcd(m,n);
}
How many recursive calls are made by this function?int IsPrime(n){
int i, n;
for(i=2; i<=sqrt(n);i++){
if(n % i == 0){
printf("No prime\n"); return 0;
}
return 1;
}
}
Let T(n) denote the number of times the for loop is executed by the program on input n. Which of the following is TRUE?int DoSomething(int n){
if(n <= 2)
return 1;
else
return (floor(sqrt(n)) + n);
}
Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of production rules:
$$\eqalign{ & S \to bA\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,S \to aB \cr & A \to a\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to b \cr & A \to aS\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to bS \cr & S \to bAA\,\,\,\,\,\,\,\,\,\,\,B \to aBB \cr} $$Which of the following strings is generated by the grammar?
Consider the grammar with non-terminals N = { S, C, S1 }, terminals T = { a, b, i, t, e }, with S as the start symbol, and the following set of rules:
$$\eqalign{ & S \to iCtS{S_1}\,|\,\,a \cr & {S_1} \to eS\,|\,\,\varepsilon \cr & C \to b \cr} $$The grammar is NOT LL(1) because:
P: Every regular grammar is LL(1)
Q: Every regular set has a LR(1) grammar
Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of production rules:
$$\eqalign{ & S \to bA\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,S \to aB \cr & A \to a\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to b \cr & A \to aS\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to bS \cr & S \to bAA\,\,\,\,\,\,\,\,\,\,\,B \to aBB \cr} $$For the correct answer strings to the previous question, how many derivation trees are there?
i. A hash function (these are often used for computing digital signatures) is an injective function.
ii. encryption technique such as DES performs a permutation on the elements of its input alphabet.
List - I
(P) SMTP(Q) BGP
(R) TCP
(S) PPP
List - II
(1) Application layer(2) Transport layer
(3) Data link layer
(4) Network layer
(5) Physical layer
$$\,\,\,\,\,$$$$IF:$$ Instruction Fetch
$$\,\,\,\,\,$$$$ID:$$ Instruction Decode and Operand Fetch
$$\,\,\,\,\,$$$$EX:$$ Execute
$$\,\,\,\,\,$$$$WB:$$ Write Back
The $$IF, ID$$ and $$WB$$ stages take one clock cycle each to complete the operation. The number of clock cycles for the $$EX$$ stage depends on the instruction. The $$ADD$$ and $$SUB$$ instructions need $$1$$ clock cycle and the $$MUL$$ instruction needs $$3$$ clock cycles in the $$EX$$ stage. Operand forwarding is used in the pipelined processor. What is the number of clock cycles taken to complete the following sequence of instructions?

How many data cache misses will occur in total?
Which of the following lines of the data cache will be replaced by new blocks in accessing the array?
The expressions for the sum bit $${S_i}$$ and the carry bit $${C_{i + 1}}$$ of the look ahead carry adder are given by $${S_i} = {P_i} \oplus {C_i}$$ and $${C_{i + 1}} = {G_i} + {P_i}{C_i},$$ where $${C_0}$$ is the input carry. Consider a two $$-$$ level logic implementation of the look $$-$$ ahead carry generator. Assume that all $${P_i}$$ and $${G_i}$$ are available for the carry generator circuit and that the $$AND$$ and $$OR$$ gates can have any number of inputs. The number of $$AND$$ gates and $$OR$$ gates needed to implement the look $$-$$ ahead carry generator for a $$4$$-bit adder with $${S_3},\,\,{S_2},\,\,{S_1},\,\,{S_0}$$ and $${C_4}$$ as its outputs are respectively
i. A hash function (these are often used for computing digital signatures) is an injective function.
ii. encryption technique such as DES performs a permutation on the elements of its input alphabet.
Which one of the following options is valid for the above two statements?
struct CellNode
{
struct CellNOde *leftChild;
int element;
struct CellNode *rightChild;
};
int GetValue(struct CellNode *ptr)
{
int value = 0;
if (ptr != NULL)
{
if ((ptr->leftChild == NULL) &&
(ptr->rightChild == NULL))
value = 1;
else
value = value + GetValue(ptr->leftChild)
+ GetValue(ptr->rightChild);
}
return(value);
}
The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:#include
#define EOF -1
void push (int); /* push the argument on the stack */
int pop (void); /* pop the top of the stack */
void flagError ();
int main () {
int c, m, n, r;
while ((c = getchar ()) != EOF) {
if (isdigit (c) )
push (c);
else if ((c == '+') || (c == '*')) {
m = pop ();
n = pop ();
r = (c == '+') ? n + m : n*m;
push (r);
} else if (c != ' ')
flagError ();
}
printf("% c", pop ());
}
What is the output of the program for the following input ?
5 2 * 3 3 2 + * + i. isEmpty (Q) — returns true if the queue is empty, false otherwise.
ii. delete (Q) — deletes the element at the front of the queue and returns its value.
iii. insert (Q, i) — inserts the integer i at the rear of the queue.
Consider the following function:
void f (queue Q) {
int i ;
if (!isEmpty(Q)) {
i = delete(Q);
f(Q);
insert(Q, i);
}
}
What operation is performed by the above function f ? Keys K 15 and then K 25 are inserted into this tree in that order. Exactly how many of the following nodes (disregarding the links) will be present in the tree after the two insertions?
Now the key K 50 is deleted from the B+ tree resulting after the two insertions made earlier. Consider the following statements about the B+ tree resulting after this deletion.
i) The height of the tree remains the same.
ii) The node
(disregarding the links) is present in the tree.
iii) The root node remains unchanged (disregarding the links).
Which one of the following options is true ?T1: read (A); T2: read (B);
read (B); read (A);
if A = 0 then B ← B + 1; if B ≠ 0 then A ← A - 1;
write (B); write (A);
Which of the following schemes, using shared and exclusive locks, satisfy the requirements for strict two phase locking for the above transactions?S1: r1(X); r1(Y); r2(Y); r2(X); w2(Y); w1(X);
S2: r1(X); r2(X); r2(Y); w2(Y); r1(Y); w1(X);
b-Schema = (b-name, b-city, assets)
a-Schema = (a-num, b-name, bal)
d-Schema = (c-name, a-number)
Let branch, account and depositor be respectively instances of the above schemas. Assume that account and depositor relations are much bigger than the branch relation.
Consider the following query:Пc-name (σb-city = “Agra” ⋀ bal < 0 (branch $$ \Join $$ (account $$ \Join $$ depositor))
Which one of the following queries is the most efficient version of the above query ?
Consider the relation employee(name, sex, supervisorName) with name as the key, supervisorName gives the name of the supervisor of the employee under consideration. What does the following Tuple Relational Calculus query produce?
$$\eqalign{ & \{ e.name\,|\,employee(e) \wedge \cr & (\forall x)[\neg employee(x) \vee \cr & x.\sup ervisorName \ne e.name\, \vee \cr & x.sex = 'male']\} \cr} $$Information about a collection of students is given by the relation studInfo(studId, name, sex). The relation enroll(studId, courseId) gives which student has enrolled for (or taken) what course(s). Assume that every course is taken by at least one male and at least one female student. What does the following relational algebra expression represent?
$$\eqalign{ & \prod\nolimits_{courseId} {((\prod\nolimits_{studId} {({\sigma _{sex = 'female'}}} } \cr & (studInfo)) \times \prod\nolimits_{courseId} {(enroll)) - enroll)} \cr} $$Q1:
Select e.empId
From employee e
Where not exists
(Select * From employee s
where s.department = "5" and
s.salary >=e.salary);
Q2:
Select e.empId
From employee e
Where e.salary > Any
( Select distinct salary
From employee s
Where s.department = "5");

The counter is connected as follows:

Assume that the counter and gate delays are negligible. If the counter starts at $$0,$$ then it cycles through the following sequence:
$$(P)\,\,\,$$ $$x'y'z' + w'xy' + wy'z + xz$$
$$(Q)\,\,\,$$ $$w'y'z' + wx'y' + xz$$
$$(R)\,\,\,$$ $$w'y'z' + wx'y' + xyz + xy'z$$
$$(S)\,\,\,$$ $$x'y'z' + wx'y' + w'y$$
$$F\left( {w,\,x,\,y,\,z} \right) = \sum {\left( {1,\,3,\,4,\,6,\,9,\,11,\,12,\,14} \right)} $$ the function is
Which of the following is an eigen value of $$\left[ {\matrix{ {\rm A} & {\rm I} \cr {\rm I} & {\rm A} \cr } } \right]$$, where $$I$$ is the $$4$$ $$x$$ $$4$$ identity matrix?
Suppose that the robot is not allowed to traverse the line segment from $$(4, 4)$$ to $$(5,4)$$. With this constraint, how many distinct path are there for the robot to reach $$(10, 10)$$ starting from $$(0,0)$$?
How many distinct path are there for the robot to reach the point $$(10, 10)$$ starting from the initial position $$(0, 0)$$?
$$P.\,\,f\left( x \right)$$ is continuous for all real values of $$x$$
$$Q.\,\,f\left( x \right)$$ is differentiable for all real values of $$x$$
Which of the following is True?
i) (0, 0) $$ \in \,P$$.
ii) (a, b) $$ \in \,P$$ if and only a %
$$10\, \le $$ b % 10 and
)a/10, b/10) $$ \in \,P$$.
Consider the following ordered pairs:
$$\matrix{
{i)\,\,\,(101,\,22)} & {ii)\,\,\,(22,\,\,101)} \cr
{iii)\,\,\,(145,\,\,265)} & {iv)\,\,\,(0,\,153)} \cr
} $$
Which of these ordered pairs of natural numbers are comtained in P?
Which all of the above represent a lattice?
If optimal page replacement policy is used, how many page faults occur for the above reference string?
$$P:$$ Increasing the number of page frames allocated to a process sometimes increases the page fault rate.
$$Q:$$ Some programs do not exhibit locality of reference.
Which one of the following is TRUE?
Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy?

Group-1
(P) Gang Scheduling
(Q) Rate Monotonic Scheduling
(R) Fair Share Scheduling
Group-2
(1) Guaranteed Scheduling
(2) Real-time Scheduling
(3) Thread Scheduling
Which one of the following statements is FALSE?
/* P1 */
while(true){
want s1=true;
while(wants2 == true){
/* Critical Section */
wants1 = false;
}
/* Reminder Section */
}
/* P2 */
while(true){
want s2=true;
while(wants1 == true){
/* Critical Section */
Wants2 = false;
}
/* Reminder Section */
}

What is the total waiting time for process $$P2?$$
int f(int n)
{
static int r = 0;
if(n <= 0) return 1;
if(n>3)
{
r = n;
return f(n-2)+2;
}
return f(n-1)+r;
}
What is the value of f(5)?

The minimum state automation equivalent to the above $$FSA$$ has the following number of states

The language accepted by this automation is given by the regular expression

Which of the following strings is generated by the grammar?

For the correct string of (earlier question) how many derivation trees are there?