GATE CS question library

Consider the partial implementation of a $2-bit$ counter using $T$ flip-flops following the sequence $0-2-3-1-0,$ as shown below. To complete the circuit, the input $X$ should be

Consider a multiplexer with $X$ and $Y$ as data inputs and $Z$ the as the control input. $Z=0$ selects input $X$, and $Z=1$ selects input $Y$. What are the connections required to realize the 2-variable Boolean function $f=T+R$, without using any additional hardware?

Which are the essential prime implicants of the following Boolean function? $f(a, b, c)= a' c+ ac'+b' c$

A circuit outputs a digit in the form of $4$ bits. $0$ is represented by $0000, 1$ by $0001, \ldots, 9$ by $1001$. A combinational circuit is to be designed which takes these $4$ bits as input and outputs $1$ if the digit $\geq$ $5$, and $0$ otherwise. If only $\textsf{AND}, \textsf{OR}$ and $\textsf{NOT}$ gates may be used, what is …

The routing table of a router is shown below: …

Consider three IP networks $A, B$ and $C$. Host $H_A$ in network $A$ sends messages each containing $180$ bytes of application data to a host $H_C$ in network $C$. The $\text{TCP}$ layer prefixes $20$ byte header to the message. This passes through an intermediate network $B$.The maximum packet size, including $20$ byte IP header, in …

$A$ and $B$ are the only two stations on an Ethernet. Each has a steady queue of frames to send. Both $A$ and $B$ attempt to transmit a frame, collide, and $A$ wins the first backoff race. At the end of this successful transmission by $A$, both $A$ and $B$ attempt to transmit and collide. The probability that $A$ wins the second backoff …

The employee information in a company is stored in the relation Employee (name, sex, salary, deptName) Consider the following SQL query Select deptName From Employee Where sex = ‘M’ Group by deptName Having avg(salary) > (select avg (salary) from Employee) It returns the names of the department in which

The order of an internal node in a $B+$ tree index is the maximum number of children it can have. Suppose that a child pointer takes $6$ bytes, the search field value takes $14$ bytes, and the block size is $512$ bytes. What is the order of the internal node?

Consider the relation Student (name, sex, marks), where the primary key is shown underlined, pertaining to students in a class that has at least one boy and one girl. What does the following relational algebra expression produce? (Note: $\rho$ is the rename operator). …

The relation scheme $\text{Student Performance (name, courseNo, rollNo, grade)}$ has the following functional dependencies: name, courseNo, $\rightarrow$ grade rollNo, courseNo $\rightarrow$ grade name $\rightarrow$ rollNo rollNo $\rightarrow$ name The highest normal form of this relation scheme is

A unix-style I-nodes has $10$ direct pointers and one single, one double and one triple indirect pointers. Disk block size is $1$ Kbyte, disk block address is $32$ bits, and $48$-bit integers are used. What is the maximum possible file size?

Consider the following set of processes, with the arrival times and the CPU-burst times gives in milliseconds. …

Consider the grammar with the following translation rules and $E$ as the start symbol …

Consider two processes $P_1$ and $P_2$ accessing the shared variables $X$ and $Y$ protected by two binary semaphores $S_X$ and $S_Y$ respectively, both initialized to 1. $P$ and $V$ denote the usual semaphore operators, where $P$ decrements the semaphore value, and $V$ increments the semaphore value. The pseudo-code of $P_1$ and $P_2$ …

Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed graph with vertex $P$ as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?

Consider the following C program segment struct CellNode{ struct CellNode *leftChild int element; struct CellNode *rightChild; }; int Dosomething (struct CellNode *ptr) { int value = 0; if(ptr != NULL) { if (ptr -> leftChild != NULL) value = 1 + DoSomething (ptr -> leftChild); if (ptr -> rightChild != NULL) value = max(value, 1 + Dosomething (ptr …

Consider the following C program main() { int x, y, m, n; scanf("%d %d", &x, &y); /* Assume x>0 and y>0*/ m = x; n = y; while(m != n) { if (m > n) m = m-n; else n = n-m; } printf("%d", n); } The program computes

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among $\text{union, intersection, membership, cardinality}$ will be the slowest?

What does the following algorithm approximate? (Assume $m > 1, \epsilon >0$). x = m; y = 1; While (x-y > ϵ) { x = (x+y)/2; y = m/x; } print(x);