GATE CS question library

Consider the following languages. $$\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}$$ Which one of the following is TRUE?

Each of a set of $n$ processes executes the following code using two semaphores $a$ and $b$ initialized to $1$ and $0$, respectively. Assume that $\text{count}$ is a shared variable initialized to $0$ and not used in CODE SECTION P. $\begin{array}{|c|} \hline \textbf{CODE SECTION P} \\ \hline \end{array}$ wait(a); count=count+1; if (count==n) …

Consider the productions $A \rightarrow PQ$ and $A \rightarrow XY$. Each of the five non-terminals $A, P, Q, X,$ and $Y$ has two attributes: $s$ is a synthesized attribute, and $i$ is an inherited attribute. Consider the following rules. Rule $1: P . i = A.i + 2, \: Q.i = P. i + A.i,$ and $A.s = P.s +Q. s$ Rule $2: X.i = A.i + Y.s$ and …

Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time. $(P, 155), (Q,85), (R,110),(S, 30), (T,115)$ Assume the head is positioned at cylinder $100$. The scheduler follows Shortest Seek Time First scheduling to service the requests. Which one of the following …

Consider a relational table $R$ that is in $3NF$, but not in BCNF. Which one of the following statements is TRUE?

Which one of the following predicate formulae is NOT logically valid? Note that $W$ is a predicate formula without any free occurrence of $x$.

Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in E$, define ${w}'(u,v)$ as $w(u,v)+f(u)-f(v)$. Which one of the options completes the following sentence so that it is TRUE? “The shortest paths in $G$ under $w$ are shortest …

An organization requires a range of IP address to assign one to each of its $1500$ computers. The organization has approached an Internet Service Provider (ISP) for this task. The ISP uses CIDR and serves the requests from the available IP address space $202.61.0.0/17$. The ISP wants to assign an address space to the organization which will minimize the …

In a balanced binary search tree with $n$ elements, what is the worst case time complexity of reporting all elements in range $[a,b]$? Assume that the number of reported elements is $k$.

The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is ______.

Consider a non-pipelined processor operating at $2.5$ GHz. It takes $5$ clock cycles to complete an instruction. You are going to make a $5$- stage pipeline out of this processor. Overheads associated with pipelining force you to operate the pipelined processor at $2$ GHz. In a given program, assume that $30\%$ are memory instructions, $60 \%$ …

A processor has $64$ registers and uses $16$-bit instruction format. It has two types of instructions: I-type and R-type. Each I-type instruction contains an opcode, a register name, and a $4$-bit immediate value. Each R-type instruction contains an opcode and two register names. If there are $8$ distinct I-type opcodes, then the maximum number of …

For $n>2$, let $a \in \{0,1\}^n$ be a non-zero vector. Suppose that $x$ is chosen uniformly at random from $\{0,1\}^n$. Then, the probability that $\displaystyle{} \Sigma_{i=1}^n a_i x_i$ is an odd number is______________

Consider the following C functions. int fun1(int n) { static int i= 0; if (n > 0) { ++i; fun1(n-1); } return (i); } int fun2(int n) { static int i= 0; if (n>0) { i = i+ fun1 (n) ; fun2(n-1) ; } return (i); } The return value of $\text{fun}2 (5)$ is _________

Consider the array representation of a binary min-heap containing $1023$ elements. The minimum number of comparisons required to find the maximum in the heap is ___________.

Consider the following C functions. int tob (int b, int* arr) { int i; for (i = 0; b>0; i++) { if (b%2) arr [i] = 1; else arr[i] = 0; b = b/2; } return (i); } int pp(int a, int b) { int arr[20]; int i, tot = 1, ex, len; ex = a; len = tob(b, arr); for (i=0; i<len ; i++) { if (arr[i] ==1) tot = tot * ex; ex= ex*ex; } return (tot) ; } The value returned …

Consider a graph $G = (V,E)$, where $V = \{v_1,v_2, \dots ,v_{100}\}$, $E = \{(v_i,v_j) \mid 1\leq i < j \leq 100\}$, and weight of the edge $(v_i,v_j)$ is $\mid i – j \mid$. The weight of minimum spanning tree of $G$ is _________

Consider the following set of processes, assumed to have arrived at time $0$. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order$P_1, P_2, P_3, P_4$. …

Consider the following language. $L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$ The minimum number of states in DFA that accepts $L$ is _________

Consider a paging system that uses $1$-level page table residing in main memory and a $\textsf{TLB}$ for address translation. Each main memory access takes $100$ ns and $\textsf{TLB}$ lookup takes $20$ ns. Each page transfer to/from the disk takes $5000$ ns. Assume that the $\textsf{TLB}$ hit ratio is $95 \%$, page fault rate is $10 \%$. …