GATE CS 2016 — Previous Year Questions

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

Let \(G\) be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5 and 6. The maximum possible weight that a minimum weight spanning tree of \(G\) can have is ______.

Consider the following code segment:

x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y;

The minimum number of total variables required to convert the above code segment to static single assignment form is ______.

The attributes of three arithmetic operators in some programming language are given below.

The value of the expression 2 − 5 + 1 − 7 * 3 in this language is ______.

A sender uses the Stop-and-Wait ARQ protocol for reliable transmission of frames. Frames are of size 1000 bytes and the transmission rate at the sender is 80 Kbps (1 Kbps = 1000 bits/second). Size of an acknowledgement is 100 bytes and the transmission rate at the receiver is 8 Kbps. The one-way propagation delay is 100 milliseconds. Assuming no frame is lost, the sender throughput is ________ bytes/second.

A processor can support a maximum memory of 4 GB, where the memory is word-addressable (a word consists of two bytes). The size of the address bus of the processor is at least ______ bits.

Which one of the following is NOT a superkey in a relational schema with attributes \(V, W, X, Y, Z\) and primary key \(VY\)?

Let \(X\) be the number of distinct 16-bit integers in 2's complement representation. Let \(Y\) be the number of distinct 16-bit integers in sign magnitude representation. Then \(X - Y\) is _______ .

Consider an eight-bit ripple-carry adder for computing the sum of \(A\) and \(B\), where \(A\) and \(B\) are integers represented in 2's complement form. If the decimal value of \(A\) is one, the decimal value of \(B\) that leads to the longest latency for the sum to stabilize is _______ .

The coefficient of \(x^{12}\) in \((x^{3} + x^{4} + x^{5} + x^{6} + \cdots)^{3}\) is ______.

Consider the following expressions:

(i) false
(ii) \(Q\)
(iii) true
(iv) \(P \vee Q\)
(v) \(\neg Q \vee P\)

The number of expressions given above that are logically implied by \(P \wedge (P \Rightarrow Q)\) is ______.

Two eigenvalues of a \(3\times 3\) real matrix \(P\) are \((2+\sqrt{-1})\) and \(3\). The determinant of \(P\) is ______.

Consider the following experiment.

Step 1. Flip a fair coin twice.
Step 2. If the outcomes are (TAILS, HEADS) then output Y and stop.
Step 3. If the outcomes are either (HEADS, HEADS) or (HEADS, TAILS), then output N and stop.
Step 4. If the outcomes are (TAILS, TAILS), then go to Step 1.

The probability that the output of the experiment is Y is (up to two decimal places) ______.

A cube is built using 64 cubic blocks of side one unit. After it is built, one cubic block is removed from every corner of the cube. The resulting surface area of the body (in square units) after the removal is ________.

A train that is 280 metres long, travelling at a uniform speed, crosses a platform in 60 seconds and passes a man standing on the platform in 20 seconds. What is the length of the platform in metres?

Two and a quarter hours back, when seen in a mirror, the reflection of a wall clock without number markings seemed to show 1:30. What is the actual current time shown by the clock?

Consider a computer system with 40-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per process and each page table entry requires 48 bits, then the size of the per-process page table is _______ megabytes.

Suppose that a shop has an equal number of LED bulbs of two different types. The probability of an LED bulb lasting more than 100 hours given that it is of Type 1 is \(0.7\), and given that it is of Type 2 is \(0.4\). The probability that an LED bulb chosen uniformly at random lasts more than 100 hours is ______.

Consider the following C program:

void f(int, short);

void main() {
    int i = 100;
    short s = 12;
    short *p = &s;
    __________ ;   /* call to f() */
}

Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?

Language \(L_1\) is defined by the grammar: \(S_1 \rightarrow a S_1 b \mid \varepsilon\)

Language \(L_2\) is defined by the grammar: \(S_2 \rightarrow ab S_2 \mid \varepsilon\)

Consider the following statements:

P: \(L_1\) is regular
Q: \(L_2\) is regular

Which one of the following is TRUE?