GATE CS question library

Suppose you are asked to design a new reliable byte-stream transport protocol like $\text{TCP}.$ This protocol, named $\textsf{myTCP}$, runs over a $100 \mathrm{~Mbps}$ network with Round Trip Time of $150$ milliseconds and the maximum segment lifetime of $2$ minutes. Which of the following is/are valid lengths of the Sequence Number field in the …

Suppose in a web browser, you click on the $\textsf{www. gate-2023.in}\; \text{URL}$. The browser cache is empty. The $\text{IP address}$ for this $\text{URL}$ is not cached in your local host, so a $\text{DNS}$ lookup is triggered (by the local $\text{DNS}$ server deployed on your local host) over the $3$-tier $\text{DNS}$ hierarchy in an …

Consider a random experiment where two fair coins are tossed. Let $A$ be the event that denotes $\text{HEAD}$ on both the throws, $B$ be the event that denotes $\text{HEAD}$ on the first throw, and $C$ be the event that denotes $\text{HEAD}$ on the second throw. Which of the following statements is/are $\text{TRUE}?$

Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=\{1,2, \ldots\}$ denote the set of all possible colors. Color the vertices of $G$ using the following greedy strategy: for $i=1, \ldots, n$ …

Consider functions $\textsf{Function\_1}$ and $\textsf{Function\_2}$ expressed in pseudocode as follows: Function_1 while n>1 do for i=1 to n do x = x + 1; end for n = ⌊n/2⌋; end while Function_2 for i = 1 to 100 * n do x = x + 1; end for Let $f_{1}(n)$ and $f_{2}(n)$ denote the number of times the statement $\textsf{“x = x + 1”}$ is executed in …

Let $U=\{1,2,3\}$. Let $2^{U}$ denote the powerset of $U$. Consider an undirected graph $G$ whose vertex set is $2^{U}$. For any $A, B \in 2^{U},(A, B)$ is an edge in $G$ if and only if (i) $A \neq B$, and (ii) either $A \subsetneq B$ or $B \subsetneq A$. For any vertex $A$ in $G$, the set of all possible orderings in which the …

Consider a computer system with $57$-bit virtual addressing using multi-level tree-structured page tables with $\mathrm{L}$ levels for virtual to physical address translation. The page size is $4 \mathrm{~KB}(1 \mathrm{~KB}=1024 \mathrm{~B})$ and a page table entry at any of the levels occupies $8$ bytes. The value of $\mathrm{L}$ is …

Consider the following two-dimensional array $\text{D}$ in the $\text{C}$ programming language, which is stored in row-major order: int D[128][128]; Demand paging is used for allocating memory and each physical page frame holds $512$ elements of the array $\text{D}.$ The Least Recently Used $\text{(LRU)}$ page-replacement policy is used by the …

Consider a sequence $a$ of elements $a_{0}=1, a_{1}=5, a_{2}=7, a_{3}=8, a_{4}=9$, and $a_{5}=2$. The following operations are performed on a stack $S$ and a queue $Q,$ both of which are initially empty. $\textsf{push}$ the elements of $a$ from $a_{0}$ to $a_{5}$ in that order into $S$. $\textsf{enqueue}$ the elements of $a$ from …

Consider the following table named $\text{Student}$ in a relational database. The primary key of this table is $\text{rollNum}.$ $\text{Student}$ …

Consider the syntax directed translation given by the following grammar and semantic rules. Here $N, I, F$ and $B$ are non-terminals. $N$ is the starting non-terminal, and $\#, \mathbf{0}$ and $\mathbf{1}$ are lexical tokens corresponding to input letters $\text{“\#", “0" and “1"},$ respectively. $X.val$ denotes the synthesized attribute (a …

Consider the language $L$ over the alphabet $\{0,1\}$, given below: $$L=\left\{w \in\{0,1\}^{*} \mid w \text{ does not contain three or more consecutive } 1 \text{ 's }\right\} .$$ The minimum number of states in a Deterministic Finite-State Automaton $\text{(DFA)}$ for $L$ is ____________.

Consider a database of fixed-length records, stored as an ordered file. The database has $25,000$ records, with each record being $100$ bytes, of which the primary key occupies $15$ bytes. The data file is block-aligned in that each data record is fully contained within a block. The database is indexed by a primary index file, which is also stored as a …

An $8$-way set associative cache of size $64 \mathrm{~KB} \;(1 \mathrm{~KB}=1024\; \text{bytes})$ is used in a system with $32$-bit address. The address is sub-divided into $\text{TAG, INDEX},$ and $\text{BLOCK OFFSET.}$ The number of bits in the $\text{TAG}$ is ___________.

The forwarding table of a router is shown below. …

We reached the station late, and _______ missed the train.

Kind : _______ : : Often : Frequently (By word meaning)

A series of natural numbers $F_1, F_2, F_3, F_4, F_5, F_6, F_7, \ldots$ obeys $F_{n+1}=F_n+F_{n-1}$ for all integers $n \geq 2$. If $F_6=37,$ and $F_7=60,$ then what is $F_1 ?$

A survey for a certain year found that $90\%$ of pregnant women received medical care at least once before giving birth. Of these women, $60\%$ received medical care from doctors, while $40\%$ received medical care from other healthcare providers. Given this information, which one of the following statements can be inferred with certainty?

Looking at the surface of a smooth $3$-dimensional object from the outside, which one of the following options is $\text{TRUE}?$