Description: GATE Exam Previous Year Question Paper Solution Computer Science(CS) - 2013 | |

Number of Questions: 63 | |

Created by: Aliensbrain Bot | |

Tags: Computer Science GATE CS Previous Year Paper |

Attempted
0/62
Correct 0
Score 0

‹
›

P: Number of odd degree vertices is even.

Q: Sum of degrees of all vertices is even.

Which one of the following expressions does NOT represent exclusive NOR of x and y?

Which one of the following functions is continuous at x = 3?

(1) The problem of determining whether there exists a cycle in an undirected graph is in P.

(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.

(3) If a problem A is NP-complete, there exists a non-deterministic polynomial time algorithm to solve A.

(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.

(2) Turing recognisable languages are closed under union and complementation.

(3) Turing decidable languages are closed under intersection and complementation.

(4) Turing recognisable languages are closed under union and intersection.

An index is clustered, if

_{1} = $\phi$ and L_{2} = {a}. Which one of the following represents L_{1} ^{$L_2^$$UL_2^$}?

The smallest integer that can be represented by an 8-bit number in 2’s complement form is

Fetch Instruction (FI), Decode Instruction (DI), Fetch Operand (FO), Execute Instruction (EI) and Write Operand (WO). The stage delays for FI, DI, FO, EI and WO are 5 ns, 7 ns, 10 ns, 8 ns and 6 ns respectively. There are intermediate storage buffers after each stage and the delay of each buffer is 1 ns. A program consisting of 12 instructions I_{1}, I_{2}, I_{3}, ….. I_{12} is executed in this pipelined processor. Instruction I_{4} is the only branch instruction and its branch target is 9 I_{9}. If the branch is taken during the execution of this program, the time (in ns) needed to complete the program is

What is the return value of f(p, p) if the value of p is initialised to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.

```
int f(int &x, int c) {
c = c – 1;
if (c == 0) return 1;
x = x + 1;
return f (x, c) * x;
}
```

Match the problem domains in Group I with the solution technologies in Group II.

Group I |
Group II |

(P) Services oriented computing | (1) Interoperability |

(Q) Heterogeneous communicating systems | (2) BPMN |

(R) Information representation | (3) Publish-find bind |

(S) Process description | (4) XML |

Which of the following is/are undecidable?

- G is a CFG. Is L (G) = $\phi$?
- G is a CFG. IS L (G) = $\sum *$?
- M is a Turning machine. Is L (M) regular?
- A is a DFA and N is an NFA. Is L (A) = L (N)?

Consider the following two sets of LR (1) items of an LR (1) grammar

X $\rightarrow$ c. X c / d X $\rightarrow$ c.X, $

X $\rightarrow$ .Cx, c / d X $\rightarrow$.Cx, $

X $\rightarrow$ .d, c / d X $\rightarrow$.d, $

Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?

- Cannot be merged since look aheads are different
- Can be merged but will result in S–R conflict
- Can be merged but will result in R–R conflict
- Cannot be merged since goto on c will lead to two different sets

Function f(x) is known at the following points:

x 0 0.3 0.6 0.9 1.2 1.5 1.8 2.1 2.4 2.7 3.0 f(x) 0 0.09 0.36 0.81 1.44 2.25 3.24 4.41 5.76 7.29 9.00

The value of ^{$\int_0^2 f$} (x) dx computed using the trapezoidal rule is

Consider the following relational schema.

Students(rollno: integer, sname: string)

Courses(courseno: integer, cname: string)

Registration(rollno: integer, courseno: integer, percent: real)

Which of the following queries are equivalent to this query in English?

“Find the distinct names of all students who score more than 90% in the course numbered 107”

(I)

```
SELECT DISTINCT S.sname
FROM Students as S, Registration as R
WHERE R.rollno=S.rollno AND R.courseno=107 AND R.percent >90
```

(II) $ \prod_{sname}(σ_{courseno=107 ∧ percent > 90} (Registration ⋈ Students)) $

(III) $\left\{T \mid ∃S \in Students, ∃R \in Registration ( S.rollno=R.rollno \land R.courseno=107 ∧ R.percent>90 ∧T.sname=S.sname)\right \}$

(IV) $\left\{ \langle S_N\rangle \mid ∃S_R∃R_P (\langle S_R,S_N\rangle ∈Students ∧ \ \langle S_R,107,R_P\rangle ∈Registration ∧ R_P>90) \right\}$

Consider the following languages:

L_{1} = {0^{p} 1 ^{q}_{0}^{r} | p, q, r ^{$\ge$} 0}

L_{2} = {0^{p}1^{q}0^{r} | p, p, r ^{$\ge$} 0, p ^{$\ne$ }r}

Which of the following statements is FALSE?

^{$\oplus$}on a set of integers is defined as x ^{$\oplus$}y = x^{2} + y^{2}. Which of the following is TRUE about ^{$\oplus$}?

MBR$\leftarrow$ PC

MAR $\leftarrow$X

PC $\leftarrow$Y

Memory MBR

Which one of the following is a possible operation performed by this sequence?

The number of elements that can be sorted in $Θ(\log n)$ time using heap sort is

Consider the following function.

```
int unknown (int n) {
int i, j, k 0;
for i n / 2; i
```

What is the logical translation of the following statement?

“None of my friends is perfect.”

• There is exactly one vertex v(e) in L(G) for each edge e in G.

• For any two edges e and e’ in G, L(G) has an edge between v(e) and v(e’), if and only if e and e’ are incident with the same vertex in G.

Which of the following statements is/are TRUE?

(P) The line graph of a cycle is a cycle.

(Q) The line graph of a clique is a clique.

(R) The line graph of a planar graph is planar.

(S) The line graph of a tree is a tree.

A certain computation generates two arrays a and b such that a [i] = f (i) for 0 $\le$ i < n and b [i] = g (a [i]) for 0 $\le$ i < n. Suppose this computation is decomposed into two concurrent processes X and Y such that X computes the array a and Y computes the array b. The processes employ two binary semaphores R and S, both initialised to zero. The array a is shared by the two processes. The structures of the processes are shown below.

```
Process X;
Process Y;
private i;
private i;
for (i = 0; i < n; i + +) {
for (i = 0; i < n; i + +) {
a [i] = f (i);
EntryY (R, S);
ExitX (R, S);
b [i] = g (a [i]);
}
}
```

Which one of the following represents the CORRECT implementations of ExitX and EntryY?

Consider the DFA given below.

Which of the following are FALSE?

- Complement of L (A) is context–free.
- $ L(A) = L((11^
*0+0)(0 + 1)^*0^*1^*) $ - For the language accepted by A, A is the minimal DFA.
- A accepts all strings over {0, 1} of length at least 2.

** Direction:** The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have almost two source operands and one destination operand. Assume that all variables are dead after this code segment.

c = a + b;

d = c * a;

e = c + a;

x = c * c;

if (x > a) {

y = a* a;

}

else {

d = d * d;

e = e * e;

}

Suppose the instruction set architecture of the processor has only two registers. The only allowed compiler optimisation is code motion, which moves statements from one place to another while preserving correctness. What is the minimum number of spills to memory in the compiled code?

** Direction:** The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have almost two source operands and one destination operand. Assume that all variables are dead after this code segment.

```
c = a + b;
d = c * a;
e = c + a;
x = c * c;
if (x > a) {
y = a* a;
}
else {
d = d * d;
e = e * e;
}
```

What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimisation other than optimising register allocation.

The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed.

```
void find_and_replace (char *A, char *oldc, char *newc) {
for (int i=0; i<5; i++)
for (int j=0; j<3; j++)
if (A[i] == oldc[j])
A[i] = newc[j];
}
```

The procedure is tested with the following four test cases.

(1) oldc = “abc”, newc = “dab” (2) oldc = “cde”, newc = “bcd”

(3) oldc = “bca”, newc = “cda” (4) oldc = “abc”, newc = “bac”

Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values.

F = {CH $\leftarrow$ G, A $\rightarrow$ BC, B $\rightarrow$ CFH, E $\rightarrow$ A, F $\rightarrow$ EG} is a set of functional dependencies (FDs) so that F+ is exactly the set of FDs that hold for R.

How many candidate keys does the relation R have?

A computer uses 46–bit virtual address, 32–bit physical address and a three–level paged page table organisation. The page table base register stores the base address of the first–level table (T_{1}) which occupies exactly one page. Each entry of T_{1} stores the base address of a page of the second–level table (T_{2}). Each entry of T_{2} stores the base address of a page of the third–level table (T_{3}). Each entry of T_{3} stores a page table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has a 1 MB 16 way set associative virtually indexed physically tagged cache. The cache block size is 64 bytes.

What is the size of a page in KB in this computer?

In the following truth table, V = 1 if and only if the input is valid.

Inputs |
Outputs |

--- | --- |

D_{0} |
D_{1} |

0 | 0 |

1 | 0 |

0 | 1 |

1 | X |

X | X |

What function does the truth table represent?

Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values.

F = {CH $\rightarrow$ G, A $\rightarrow$ BC, B $\rightarrow$ CFH, E $\rightarrow$ A, F $\rightarrow$ EG} is a set of functional dependencies (FDs) so that F+ is exactly the set of FDs that hold for R.

The relation R is

__ Directions:__ Fill in the blank.

Were you a bird, you ___________ in the sky.

Which one of the following assertions is best supported by the above information?

Complete the following sentence.

Universalism is to particularism as diffuseness is to _______.

A computer uses 46–bit virtual address, 32–bit physical address, and a three–level paged page table organization. The page table base register stores the base address of the first–level table (T_{1}) which occupies exactly one page. Each entry of T_{1} stores the base address of a page of the second–level table (T_{2}). Each entry of T_{2} stores the base address of a page of the third–level table (T_{3}). Each entry of T_{3} stores a page table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has a 1 MB 16 way set associative virtually indexed physically tagged cache. The cache block size is 64 bytes.

What is the minimum number of page colours needed to guarantee that no two synonyms map to different sets in the processor cache of this computer?

Choose the grammatically INCORRECT sentence from the given options.

Which one of the following options is the closest in meaning to the word given below?

Nadir

Which one of the following is NOT logically equivalent to $¬∃x(∀ y (α)∧∀z(β ))$?