GATE CS question library

If $L1$ is context free language and $L2$ is a regular language which of the following is/are false?

Let $L$ be a set with a relation $R$ which is transitive, anti-symmetric and reflexive and for any two elements $a, b \in L$, let the least upper bound $lub (a, b)$ and the greatest lower bound $glb (a, b)$ exist. Which of the following is/are true?

Two girls have picked $10$ roses, $15$ sunflowers and $15$ daffodils. What is the number of ways they can divide the flowers among themselves?

Consider two events $E_1$ and $E_2$ such that probability of $E_1$, $P_r[E_1]=\frac{1}{2}$, probability of $E_2$, $P_r[E_{2}]=\frac{1}{3}$, and probability of $E_1$, and $E_2$, $P_r[E_1 \: and \: E_2] = \frac{1}{5}$. Which of the following statements is/are true?

Which of the following is correct?

Let $R = (A, B, C, D, E, F)$ be a relation scheme with the following dependencies $C \rightarrow F, E \rightarrow A, EC \rightarrow D, A \rightarrow B$. Which one of the following is a key for $R$?

The Newton-Raphson method is to be used to find the root of the equation $f(x)=0$ where $x_o$ is the initial approximation and $f’$ is the derivative of $f$. The method converges

The main memory of a computer has $2\;\text{cm}$ blocks while the cache has $2\;\text{c}$ blocks. If the cache uses the set associative mapping scheme with $2$ blocks per set, then block $k$ of the main memory maps to the set:

The maximum gate delay for any output to appear in an array multiplier for multiplying two $n$ bit numbers is

Booth's coding in $8$ bits for the decimal number $-57$ is:

The relational algebra expression equivalent to the following tuple calculus expression: $\left\{t \mid t \in r \land \left(t[A] = 10 \land t[B]=20\right)\right\}$ is

Consider the join of a relation $R$ with a relation $S$. If $R$ has $m$ tuples and $S$ has $n$ tuples then the maximum and minimum sizes of the join respectively are

Which of the following is the most powerful parsing method?

If $n$ is a power of $2$, then the minimum number of multiplications needed to compute $a^n$ is

The number of articulation points of the following graph is

If one uses straight two-way merge sort algorithm to sort the following elements in ascending order: $20, \ 47, \ 15, \ 8, \ 9, \ 4, \ 40, \ 30, \ 12, \ 17$ then the order of these elements after second pass of the algorithm is:

Suppose we want to arrange the $n$ numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is

A sorting technique is called stable if

System calls are usually invoked by using

Which of the following disk scheduling strategies is likely to give the best throughput?