GATE CSE
I. (n + k)m = $$\Theta \,({n^m})$$ where k and m are constants
II. 2n+1 = O(2n)
III. 22n = O(22n)
Which of those claims are correct?
$$$A[j,k] = \left\{ {\matrix{ {1\,if\,(j,\,k)} \cr {1\,otherwise} \cr } } \right.$$$ Consider the following algorithm.
for i = 1 to n
for j = 1 to n
for k = 1 to n
A [j , k] = max (A[j, k] (A[j, i] + A [i, k]); Consider the grammar shown below.
$$\eqalign{ & S \to CC \cr & C \to cC\,|\,d \cr} $$This grammar is
Consider the translation scheme shown below
$$\eqalign{ & S \to TR \cr & R \to + T\left\{ {pr{\mathop{\rm int}} (' + ');} \right\}\,R\,|\,\varepsilon \cr & T \to num\,\left\{ {pr{\mathop{\rm int}} (num.val);} \right\} \cr} $$Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string '9 + 5 + 2', this translation scheme will print
Consider the syntax directed definition shown below.
Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. Assume that ti's are the temporary variable names generated by newtemp. For the statement 'X : = Y + Z', the 3-address code sequence generated by this definition is
Consider the grammar shown below
$$\eqalign{ & S \to iEtSS'\,|\,\,a \cr & S' \to eS\,|\,\,\varepsilon \cr & E \to b \cr} $$In the predictive parse table, $$M$$, of this grammar, the entries $$M\left[ {S',e} \right]$$ and $$M\left[ {S',\phi } \right]$$ respectively are
$$1.\,\,\,\,\,$$ The $$j+1$$ instruction uses the result of the $$j$$-$$th$$ instruction as an operand
$$2.\,\,\,\,\,$$ The execution of a conditional jump instruction
$$3.\,\,\,\,\,$$ The $$j$$-$$th$$ and $$j+1$$ instruction require the $$ALU$$ at the same time
Which of the above can cause a hazard?
Let $$s, e,$$ and $$m$$ be the numbers represented in binary in the sign, exponent, and mantissa fields respectively. Then the floating point number represented is
$$\left\{ {\matrix{ {{{\left( { - 1} \right)}^s}\left( {1 + m \times {2^{ - 9}}} \right){2^{e - 31}},} & {if\,the\,{\mathop{\rm exponent}\nolimits} \, \ne \,111111} \cr {\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,0} & {otherwise\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,} \cr } } \right.$$
What is the maximum difference between two successive real numbers representable in this system?
I. a b e g h f
II. a b f e h g
III. a b f h g e
IV. a f g h b e
What are depth first traversals of the above graph?struct item {
int data;
struct item * next;
};
int f(struct item *p) {
return ((p == NULL) || (p ->next == NULL) ||
((p->data <= p -> next -> data) &&
f(p-> next)));
}
Which of the following statements is correct?
Select distinct a1, a2, ..., an
From r1, r2, ..., rm
Where P; Students: (Roll_number, Name, Date_of_birth)
Courses: (Course number, Course_name, Instructor)
Grades: (Roll_number, Course_number, Grade)
Select distinct Name
From Students, Courses, Grades
Where Students.Roll_number = Grades.Roll_number
and Courses.Instructor = 'Korth'
and Courses.Course_number = Grades.Course_number
and Grades.grade = 'A';$$\eqalign{ & \,\,\,\,Date\,\,of\,\,Birth\,\, \to \,\,Age \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,Age\,\, \to \,\,Eligibility \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,Name\,\, \to \,\,Roll\_number \cr & \,\,\,\,\,Roll\_number\,\, \to \,\,Name \cr & Course\_number\, \to \,\,Course\_name \cr & Course\_number\, \to Instructor \cr & (Roll\_Number,\,Course\_number)\,\, \to \,\,Grade \cr} $$
The relation (Roll_number, Name, Date_of_Birth, Age) is
If the operands are in $$2's$$ complement representation, which of the following operations can be performed by suitably setting the control lines $$K$$ and $${C_0}$$ only ( + and - denote addition and subtraction respectively)?
The non-inverting buffers have delays $${\delta _1} = 2$$ $$ns$$ and $${\delta _2} = 4$$ $$ns$$ as shown in the figure. Both $$XOR$$ gates and all wires have zero delay. Assume that all gate inputs, outputs and wires are stable at logic level $$0$$ at time$$0.$$ If the following waveform is applied at input $$A$$, how many transition(s) (change of logic levels) occurs(s) at $$B$$ during the interval from $$0$$ to $$10$$ $$ns?$$
Let $${z_k},\,{n_k}$$ denote the number of $$0’s$$ and $$1’s$$ respectively in initial $$k$$ bits of the input
$$\left({{z_k} + {n_k} = k} \right).$$ The circuit outputs $$00$$ until one of the following conditions holds.
$$ * \,\,\,\,\,$$ $${z_k} = {n_k} + 2.\,\,\,$$ In this case, the output at the $$k$$-th and all subsequent clock ticks is $$10.$$
$$ * \,\,\,\,\,$$ $${n_k} = {z_k} + 2.\,\,\,$$ In this case, the output at the $$k$$-th and all subsequent clock ticks is $$01.$$
What is the minimum number of states required in the state transition graph of the above circuit?
Notice that the second and the third columns of the coefficient matrix are linearly dependent. For how many values of $$\alpha $$, does this system of equations have infinitely many solutions?
i) Each is sorted in ascending order.
ii) $$B$$ has $$5$$ and $$C$$ has $$3$$ elements, and
iii) The result of merging $$B$$ $$C$$ gives $$A$$?
Which of the following statements related to this rule is FALSE?
Suppose a process has only the following pages in its virtual address space: two contiguous code pages starting at virtual address $$0 \times 00000000,$$ two contiguous data pages starting at virtual address $$0 \times 00400000,$$ and a stack page starting at virtual address $$0 \times FFFFF000.$$ The amount of memory required for storing the page tables of this process is
Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest $$0.5$$ ns)
Process P:
while(1){
W:
Print '0';
Print '0';
X:
}
Process Q:
while(1){
Y:
Print '1';
Print '1';
Z:
}
Which of the following will ensure that the output string never contains a substring of the form 01n0 or 10n1 where n is odd?
Process P:
while(1){
W:
Print '0';
Print '0';
X:
}
Process Q:
while(1){
Y:
Print '1';
Print '1';
Z:
}
Which of the following will always lead to an output starting with 001100110011
#include < stdio.h >
#define print(x) printf("%d ", x)
int x;
void Q(int z) {
z += x; print(z);
}
void P(int *y) {
int x = *y+2;
Q(x); *y = x-1;
print(x);
}
main(void) {
x = 5;
P(&x);
print(x);
}global int i = 100, j = 5;
void P(x) {
int i = 10;
print(x + 10);
i = 200;
j = 20;
print (x);
}
main() {
P(i + j);
}float f,(float x, int y) {
float p, s; int i;
for (s=1,p=1,i=1; i < y; i++) {
p *= x/i;
s+=p;
}
return s;
}Class P {
void f(int i) {
print(i);
}
}
Class Q subclass of P {
void f(int i) {
print(2*i);
}
}Px = new Q();
Qy = new Q();
Pz = new Q();
x.f(1); ((P)y).f(1); z.f(1);
Here ((P)y) denotes a typecast of y to P. The output produced by executing the above program fragment will be
int * A[10], B[10][10];
Of the following expressionsI. A[2]
II. A[2] [3]
III. B[1]
IV. B[2] [3]
Which will not give compile-time errors if used as left hand sides of assignment statements in a C program?
global int i = 100, j = 5;
void P(x) {
int i = 10;
print(x + 10);
i = 200;
j = 20;
print (x);
}
main() {
P(i + j);
}
Let the language accepted by $$M$$ be $$L.$$ Let $${L_1}$$ be the language accepted by the $$NFA$$, $${M_1}$$ obtained by changing the accepting state of $$M$$ to a non accepting state and by changing the non accepting state of $$M$$ to accepting states. Which of the following statements is true?
The table is interpreted as illustrated below. The entry $$\left( {{q_1},1,\,R} \right)$$ in row $${{q_0}}$$ and column $$1$$ signifies that if $$M$$ is in state $${{q_0}}$$ and reads $$1$$ on the current tape square, then it writes $$1$$ on the same tape square, moves its tape head one position to the right and transitions to state $${{q_1}}$$.
Which of the following statements is true about $$M?$$
$${L_0} = \left\{ { < M,\,w,\,0 > \left| {M\,\,} \right.} \right.$$ halts on $$\left. w \right\}$$
$${L_1} = \left\{ { < M,w,1 > \left| M \right.} \right.$$ does not halts on $$\left. w \right\}$$
Here $$ < M,\,w,\,i > $$ is a triplet, whose first component, $$M$$ is an encoding of a Turing Machine, second component, $$w$$, is a string, and third component, $$t,$$ is a bit.
Let $$L = {L_0} \cup {L_1}.$$ Which of the following is true?
$$L = \left\{ {\matrix{ {{{\left( {0 + 1} \right)}^ * }\,\,\,if\,\,P = NP} \cr {\,\,\,\,\,\,\,\phi \,\,\,\,Otherwise} \cr } } \right.$$
Which of the following statement is true?
Let $$S$$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $$1$$. The number of strings in $$S$$ that are accepted by $$M$$ is