List of top Questions asked in GATE CS

Let \(L_1\) be the language represented by the regular expression \(b^*ab^*(ab^*ab^*)^*\) and \(L_2 = \{ w \in (a + b)^* \mid |w| \leq 4 \\), where \(|w|\) denotes the length of string \(w\). The number of strings in \(L_2\) which are also in \(L_1\) is ............}

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is ............ \begin{center} \includegraphics[width=0.3\textwidth]{60.png} \end{center}

A processor uses a 32-bit instruction format and supports byte-addressable memory access. The ISA of the processor has 150 distinct instructions. The instructions are equally divided into two types, namely R-type and I-type, whose formats are shown below. R-type Instruction Format: \begin{center} \setlength{\tabcolsep}{15pt} % Adjust column spacing \renewcommand{\arraystretch}{1.5} % Adjust row spacing \begin{tabular}{|c|c|c|c|c|} \hline OPCODE & UNUSED & DST Register & SRC Register1 & SRC Register2
\hline \end{tabular} \end{center} \vspace{0.5cm} I-type Instruction Format: \begin{center} \setlength{\tabcolsep}{15pt} % Adjust column spacing \renewcommand{\arraystretch}{1.5} % Adjust row spacing \begin{tabular}{|c|c|c|c|} \hline OPCODE & DST Register & SRC Register & \# Immediate Value/Address
\hline \end{tabular} \end{center} In the OPCODE, 1 bit is used to distinguish between I-type and R-type instructions, and the remaining bits indicate the operation. The processor has 50 architectural registers, and all register fields in the instructions are of equal size. Let \(X\) be the number of bits used to encode the UNUSED field, \(Y\) be the number of bits used to encode the OPCODE field, and \(Z\) be the number of bits used to encode the immediate value/address field. The value of \(X + 2Y + Z\) is ............

Consider 4-variable functions \(f_1, f_2, f_3, f_4\) expressed in sum-of-minterms form as given below. \[ f_1 = \Sigma(0,2,3,5,7,8,11,13)
f_2 = \Sigma(1,3,5,7,11,13,15)
f_3 = \Sigma(0,1,4,11)
f_4 = \Sigma(0,2,6,13) \] The circuit is represented as: \begin{center} \includegraphics[width=6cm]{50.png} \end{center} With respect to the circuit given above, which of the following options is/are CORRECT?

Consider a context-free grammar \(G\) with the following 3 rules: \[ S \to aS, \quad S \to aSbS, \quad S \to c \] Let \(w \in L(G)\). Let \(n_a(w), n_b(w), n_c(w)\) denote the number of times \(a, b, c\) occur in \(w\), respectively. Which of the following statements is/are TRUE?

A functional dependency \(F: X \to Y\) is termed as a useful functional dependency if and only if it satisfies all the following three conditions: \(X\) is not the empty set. \(Y\) is not the empty set. Intersection of \(X\) and \(Y\) is the empty set. For a relation \(R\) with 4 attributes, the total number of possible useful functional dependencies is ............

Consider a multi-threaded program with two threads \(T1\) and \(T2\). The threads share two semaphores: \(s1\) (initialized to 1) and \(s2\) (initialized to 0). The threads also share a global variable \(x\) (initialized to 0). The threads execute the code shown below. \begin{verbatim} // code of T1 // code of T2 wait(s1); wait(s1); x = x+1; x = x+1; print(x); print(x); wait(s2); signal(s2); signal(s1); signal(s1); \end{verbatim} Which of the following outcomes is/are possible when threads \(T1\) and \(T2\) execute concurrently?

Let \(S1\) and \(S2\) be two stacks. \(S1\) has a capacity of 4 elements, and \(S2\) has a capacity of 2 elements. \(S1\) already has 4 elements: 100, 200, 300, and 400, whereas \(S2\) is empty, as shown below. \begin{center} \includegraphics[width=8cm]{48.png} \end{center} Only the following three operations are available:
\texttt{PushToS2:} Pop the top element from \(S1\) and push it on \(S2\).
\texttt{PushToS1:} Pop the top element from \(S2\) and push it on \(S1\).
\texttt{GenerateOutput:} Pop the top element from \(S1\) and output it to the user. Note: - The pop operation is not allowed on an empty stack.
- The push operation is not allowed on a full stack. Which of the following output sequences can be generated by using the above operations?

The relation schema, \( \text{Person(pid, city) \), describes the city of residence for every person uniquely identified by \( \text{pid} \). The following relational algebra operators are available: \texttt{selection}, \texttt{projection}, \texttt{cross product}, and \texttt{rename}.} To find the list of cities where at least 3 persons reside, using the above operators, the minimum number of \texttt{cross product operations that must be used is ...........\_.}

Consider the following expression: \(x[i] = (p + r) * -s[i] + u / w\). The following sequence shows the list of triples representing the given expression, with entries missing for triples (1), (3), and (6). \begin{center} \begin{tabular}{|c|c|c|c|} \hline (0) & \(+\) & \(p\) & \(r\)
\hline (1) & & &
\hline (2) & \texttt{uminus} & \((1)\) &
\hline (3) & & &
\hline (4) & \(/\) & \(u\) & \(w\)
\hline (5) & \(+\) & \((3)\) & \((4)\)
\hline (6) & & &
\hline (7) & \(=\) & \((6)\) & \(x[i]\)
\hline \end{tabular} \end{center} Which one of the following options fills in the missing entries CORRECTLY?

Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, and the second value is its CPU burst time. \[ A (0, 10), \, B (2, 6), \, C (4, 3), \, D (6, 7). \] Which one of the following options gives the average waiting times when preemptive Shortest Remaining Time First (SRTF) and Non-Preemptive Shortest Job First (NP-SJF) CPU scheduling algorithms are applied to the processes?

Consider an array \(X\) that contains \(n\) positive integers. A subarray of \(X\) is defined to be a sequence of array locations with consecutive indices. The C code snippet given below has been written to compute the length of the longest subarray of \(X\) that contains at most two distinct integers. The code has two missing expressions labelled \((P)\) and \((Q)\). \begin{verbatim} int first=0, second=0, len1=0, len2=0, maxlen=0; for (int i=0; i<n; i++) { if (X[i] == first) { len2++; len1++; } else if (X[i] == second) { len2++; len1 = (P); second = first; } else { len2 = (Q); len1 = 1; second = first; } if (len2>maxlen) { maxlen = len2; } first = X[i]; } \end{verbatim} Which one of the following options gives the CORRECT missing expressions?

Let \(M\) be the 5-state NFA with \(\epsilon\)-transitions shown in the diagram below. \begin{center} \includegraphics[width=0.2\textwidth]{41.png} \end{center} Which one of the following regular expressions represents the language accepted by \(M\)?

You are given a set \(V\) of distinct integers. A binary search tree \(T\) is created by inserting all elements of \(V\) one by one, starting with an empty tree. The tree \(T\) follows the convention that, at each node, all values stored in the left subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in which these values were inserted into \(T\), and you do not have access to \(T\). Which one of the following statements is TRUE?