GATE CS question library

Consider the following $\text{ANSI C}$ program #include <stdio.h> int foo(int x, int y, int q) { if ((x<=0) && (y<=0)) return q; if (x<=0) return foo(x, y-q, q); if (y<=0) return foo(x-q, y, q); return foo(x, y-q, q) + foo(x-q, y, q); } int main( ) { int r = foo(15, 15, 10); printf(“%d”, r); return 0; } The output of the program …

Let $S$ be a set consisting of $10$ elements. The number of tuples of the form $(A,B)$ such that $A$ and $B$ are subsets of $S$, and $A \subseteq B$ is ___________

Consider the following augmented grammar with $\{ \#, @, <, >, a, b, c \}$ as the set of terminals. $$\begin{array}{l} S’ \rightarrow S \\ S \rightarrow S \# cS \\ S \rightarrow SS \\ S \rightarrow S @ \\ S \rightarrow < S > \\ S \rightarrow a \\ S \rightarrow b \\ S \rightarrow c \end{array}$$Let …

Consider a Boolean function $f(w,x,y,z)$ such that $$\begin{array}{lll} f(w,0,0,z) & = & 1 \\ f(1,x,1,z) & =& x+z \\ f(w,1,y,z) & = & wz +y \end{array}$$The number of literals in the minimal sum-of-products expression of $f$ is _________

Consider a network using the pure $\text{ALOHA}$ medium access control protocol, where each frame is of length $1,000$ bits. The channel transmission rate is $1$ Mbps ($=10^6$ bits per second). The aggregate number of transmissions across all the nodes (including new frame transmissions and retransmitted frames due to collisions) is modelled as a …

Consider a pipelined processor with $5$ stages, $\text{Instruction Fetch} (\textsf{IF})$, $\text{Instruction Decode} \textsf{(ID)}$, $\text{Execute } \textsf{(EX)}$, $\text{Memory Access } \textsf{(MEM)}$, and $\text{Write Back } \textsf{(WB)}$. Each stage of the pipeline, except the $\textsf{EX}$ stage, takes one cycle. Assume that the …

In a directed acyclic graph with a source vertex $\textsf{s}$, the $\textit{quality-score}$ of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex $v$ other than $\textsf{s}$, the quality-score of $v$ is defined to be the maximum among the quality-scores of all the paths from $\textsf{s}$ to …