GATE CS question library

Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is $N$. Three semaphores $empty$, $full$ and $mutex$ are defined with respective initial values of $0, N$ and $1$. Semaphore $empty$ denotes the number of available slots in the buffer, for the consumer to read from. Semaphore $full$ …

Consider the unsigned 8-bit fixed point binary number representation, below, $$b_7 \: \: b_6 \: \: b_5 \: \: b_4 \: \: b_3 \: \: \cdot b_2 \: \: b_1 \: \: b_0$$ where the position of the primary point is between $b_3$ and $b_2$ . Assume $b_7$ is the most significant bit. Some of the decimal numbers listed below cannot be represented exactly in the …

Consider the following C code. Assume that unsigned long int type length is $64$ bits. unsigned long int fun(unsigned long int n) { unsigned long int i, j=0, sum = 0; for( i=n; i>1; i=i/2) j++; for( ; j>1; j=j/2) sum++; return sum; } The value returned when we call fun with the input $2^{40}$ is:

Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ is between two nodes neither of which is an ancestor of the other in $T_D$). For every edge …

#include<stdio.h> void fun1(char* s1, char* s2){ char* temp; temp = s1; s1 = s2; s2 = temp; } void fun2(char** s1, char** s2){ char* temp; temp = *s1; *s1 = *s2; *s2 = temp; } int main(){ char *str1="Hi", *str2 = "Bye"; fun1(str1, str2); printf("%s %s", str1, str2); fun2(&str1, &str2); printf("%s %s", str1, str2); return 0; } The output of the …

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_1G_2G_3 \dots G_n$ can be done by parenthesizing in different ways. Define $G_i G_{i+1}$ as an explicitly computed pair for a given …

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

Consider the first-order logic sentence $$\varphi \equiv \exists \: s \: \exists \: t \: \exists \: u \: \forall \: v \: \forall \: w \forall \: x \: \forall \: y \: \psi(s, t, u, v, w, x, y)$$ where $\psi(s, t, u, v, w, x, y, )$ is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. …

Let $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 $N$ $R:$ Set of functions from $N$ to $\{0, 1\}$ $S:$ Set of finite subsets of $N$ Which of the above sets are countable?

Consider a system with $3$ processes that share $4$ instances of the same resource type. Each process can request a maximum of $K$ instances. Resources can be requested and releases only one at a time. The largest value of $K$ that will always avoid deadlock is ___

Consider a matrix P whose only eigenvectors are the multiples of $\begin{bmatrix} 1 \\ 4 \end{bmatrix}$. Consider the following statements. P does not have an inverse P has a repeated eigenvalue P cannot be diagonalized Which one of the following options is correct?

Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered $\text{D}$ flip-flops. The number of states in the state transition diagram of this circuit that have a transition back to the same state on some value of "in" is ____

A $32\text{-bit}$ wide main memory unit with a capacity of $1\;\textsf{GB}$ is built using $256\textsf{M} \times 4\text{-bit}$ DRAM chips. The number of rows of memory cells in the DRAM chip is $2^{14}$. The time taken to perform one refresh operation is $50\;\text{nanoseconds}$. The refresh period is $2\;\text{milliseconds.}$ The percentage …

The postorder traversal of a binary tree is $\text{8, 9, 6, 7, 4, 5, 2, 3, 1}$. The inorder traversal of the same tree is ${8, 6, 9, 4, 7, 2, 5, 1, 3}$. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is _____

Let $G$ be a finite group on $84$ elements. The size of a largest possible proper subgroup of $G$ is _____

The chromatic number of the following graph is _____

Consider the following $\text{C}$ program: #include<stdio.h> int counter=0; int calc (int a, int b) { int c; counter++; if(b==3) return (a*a*a); else { c = calc(a, b/3); return (c*c*c); } } int main() { calc(4, 81); printf("%d", counter); } The output of this program is ______.

Consider a matrix $A= uv^T$ where $u=\begin{pmatrix}1 \\ 2 \end{pmatrix} , v = \begin{pmatrix}1 \\1 \end{pmatrix}$. Note that $v^T$ denotes the transpose of $v$. The largest eigenvalue of $A$ is ____

The value of $\int^{\pi/4} _0 x \cos(x^2) dx$ correct to three decimal places (assuming that $\pi = 3.14$) is ____

Two people, $P$ and $Q$, decide to independently roll two identical dice, each with $6$ faces, numbered $1$ to $6$. The person with the lower number wins. In case of a tie, they roll the dice repeatedly until there is no tie. Define a trial as a throw of the dice by $P$ and $Q.$ Assume that all $6$ numbers on each dice are equi-probable and …