GATE CS 2018 — Previous Year Questions

Assume that multiplying a matrix \(G_1\) of dimension \(p \times q\) with another matrix \(G_2\) of dimension \(q \times r\) requires \(pqr\) scalar multiplications. Computing the product of \(n\) matrices \(G_1 G_2 G_3 \ldots G_n\) using dynamic programming, the time complexity is

Consider the following intermediate program in three address code:

p = a - b
q = p * c
p = u * v
q = p + q

Which one of the following corresponds to a static single assignment form of the above code?

Consider a long-lived TCP session with an end-to-end bandwidth of 1 Gbps (= \(10^{9}\) bits-per-second). The session starts with a sequence number of 1234. The minimum time (in seconds, rounded to the closest integer) before this sequence number can be used again is ________.

The size of the physical address space of a processor is \(2^{P}\) bytes. The word length is \(2^{W}\) bytes. The capacity of cache memory is \(2^{N}\) bytes. The size of each cache block is \(2^{M}\) words. For a \(K\)-way set-associative cache memory, the length (in number of bits) of the tag field is

Consider the minterm list form of a Boolean function \(F\) given below.

\(F(P,Q,R,S) = \sum m(0,\,2,\,5,\,7,\,9,\,11) + d(3,\,8,\,10,\,12,\,14)\)

Here, \(m\) denotes a minterm and \(d\) denotes a don't care term. The number of essential prime implicants of the function \(F\) is _______ .

Let \(\mathbb{N}\) be the set of natural numbers. Consider the following sets.

P: Set of rational numbers (positive and negative)
Q: Set of functions from \(\{0, 1\}\) to \(\mathbb{N}\)
R: Set of functions from \(\mathbb{N}\) to \(\{0, 1\}\)
S: Set of finite subsets of \(\mathbb{N}\)

Which of the sets above are countable?

“Going by the ________ that many hands make light work, the school ________ involved all the students in the task.”

The words that best fill the blanks in the above sentence are

Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is \(M\) units if the corresponding memory page is available in memory, and \(D\) units if the memory access causes a page fault. It has been experimentally measured that the average time taken for a memory access in the process is \(X\) units.

Which one of the following is the correct expression for the page fault rate experienced by the process?

Consider the following C program:

#include <stdio.h>

struct Ournode {
    char x, y, z;
};

int main() {
    struct Ournode p = {'1', '0', 'a' + 2};
    struct Ournode *q = &p;
    printf("%c, %c", *((char *)q + 1), *((char *)q + 2));
    return 0;
}

The output of this program is: