List of top Questions asked in GATE CS

The following two signed 2’s complement numbers (multiplicand $ M $ and multiplier $ Q $) are being multiplied using Booth’s algorithm:

Multiplicand ($ M $)	Multiplier ($ Q $)
1100 1101 1110 1101	1010 0100 1010 1010

The total number of addition and subtraction operations to be performed is __________. (Answer in integer)

The maximum value of $x$ such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is __________ (answer in integer).

Consider the following C program

The value printed by the given C program is __________ (Answer in integer).

The value printed by the given C program is __________ (Answer in integer).

Consider the given sequential circuit designed using D-Flip-flops. The circuit is initialized with some value (initial state). The number of distinct states the circuit will go through before returning back to the initial state is:

Consider a finite state machine (FSM) with one input $X$ and one output $f$, represented by the given state transition table. The minimum number of states required to realize this FSM is __________ (Answer in integer).

Consider a probability distribution given by the density function $ P(x) $. \[ P(x) = \begin{cases} Cx^2, & \text{for } 1 \leq x \leq 4, \\ 0, & \text{for } x < 1 \text{ or } x > 4. \end{cases} \] The probability that $ x $ lies between 2 and 3, i.e., $ P(2 \leq x \leq 3) $, is ___________. (rounded off to three decimal places)

Suppose a message of size 15000 bytes is transmitted from a source to a destination using IPv4 protocol via two routers as shown in the figure. Each router has a defined maximum transmission unit (MTU) as shown in the figure, including IP header. The number of fragments that will be delivered to the destination is ___________. (Answer in integer)

Consider the following database tables of a sports league. player ($ pid $, $ pname $, $ age $) coach ($ cid $, $ cname $) team ($ tid $, $ tname $, $ city $, $ cid $) members ($ pid $, $ tid $) An instance of the table and an SQL query are given. Player table

coach table:

team table:

members table:

SQL query: \[ {SELECT MIN(P.age)} \] \[ {FROM player P} \] \[ {WHERE P.pid IN (} \] \[ { SELECT M.pid} \] \[ { FROM team T, coach C, members M} \] \[ { WHERE C.cname = 'Mark'} \] \[ { AND T.cid = C.cid} \] \[ { AND M.tid = T.tid)} \] The value returned by the given SQL query is __________. (Answer in integer)

The pseudocode of a function $ fun() $ is given below:

fun(int A[0, ..., n-1]) {
    for i = 0 to n-2
        for j = 0 to n - i - 2
            if (A[j] > A[j+1])
                then swap A[j] and A[j+1]
}

Let $ A[0, \ldots, 29] $ be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function $ fun() $ is called with $ A[0, \ldots, 29] $ as argument, is __________ (Answer in integer).

Consider the given function $ f(x) $. \[ f(x) = \begin{cases} ax + b & \text{for } x < 1 \\ x^3 + x^2 + 1 & \text{for } x \geq 1 \end{cases} \] If the function is differentiable everywhere, the value of $ b $ must be __________ (rounded off to one decimal place).

Let $ G $ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $ \alpha $ is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in $ G $ before and after the edge weight update?

Let $ L, M, $ and $ N $ be non-singular matrices of order 3 satisfying the equations: \[ L^2 = L^{-1}, \quad M = L^8, \quad N = L^2. \] Which ONE of the following is the value of the determinant of $ (M - N) $?

The value of $ x $ such that $ x%gt;1 $ , satisfying the equation \[ \int_{1}^{x} t \ln t \, dt = 1 \] is

Which of the following Boolean algebraic equation(s) is/are CORRECT?

The unit interval $(0, 1)$ is divided at a point chosen uniformly distributed over $(0, 1)$ in $\mathbb{R}$ into two disjoint subintervals. The expected length of the subinterval that contains 0.4 is ___________. (rounded off to two decimal places)

Consider a system of linear equations $ P X = Q $ where $ P \in \mathbb{R}^{3 \times 3} $ and $ Q \in \mathbb{R}^{3 \times 1} $. Suppose $ P $ has an LU decomposition, $ P = LU $, where:

Which of the following statement(s) is/are TRUE?

Consider a network that uses Ethernet and IPv4. Assume that IPv4 headers do not use any options field. Each Ethernet frame can carry a maximum of 1500 bytes in its data field. A UDP segment is transmitted. The payload (data) in the UDP segment is 7488 bytes. Which ONE of the following choices has the CORRECT total number of fragments transmitted and the size of the last fragment including IPv4 header?

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

Consider the following relational schema:

Which of the following options is/are correct SQL query/queries to retrieve the names of the students enrolled in course number (i.e., courseno) 1470?

Let $\Sigma = \{a, b, c\}$. For $x \in \Sigma^*$, and $\alpha \in \Sigma$, let $\#\alpha(x)$ denote the number of occurrences of $\alpha$ in $x$. Which one or more of the following option(s) define(s) regular language(s)?

For a direct-mapped cache, 4 bits are used for the tag field and 12 bits are used to index into a cache block. The size of each cache block is one byte. Assume that there is no other information stored for each cache block. Which ONE of the following is the CORRECT option for the sizes of the main memory and the cache memory in this system (byte addressable), respectively?

An application executes $ 6.4 \times 10^8 $ number of instructions in 6.3 seconds. There are four types of instructions, the details of which are given in the table. The duration of a clock cycle in nanoseconds is ___________. (rounded off to one decimal place) \begin{center} \begin{tabular}{|c|c|c|} \hline Instruction type & Clock cycles per instruction (CPI) & Number of instructions executed
\hline Branch & 2 & $ 2.25 \times 10^8 $
Load & 5 & $ 1.20 \times 10^8 $
Store & 4 & $ 1.65 \times 10^8 $
Arithmetic & 3 & $ 1.30 \times 10^8 $
\hline \end{tabular} \end{center}

An audit of a banking transactions system has found that on an earlier occasion, two joint holders of account $ A $ attempted simultaneous transfers of Rs. 10000 each from account $ A $ to account $ B $. Both transactions read the same value, Rs. 11000, as the initial balance in $ A $ and were allowed to go through. $ B $ was credited Rs. 10000 twice. $ A $ was debited only once and ended up with a balance of Rs. 1000. Which of the following properties is/are certain to have been violated by the system?