GATE 2025 CSE & IT

A schedule of three database transactions $T_1, T_2$, and $T_3$ is shown. $R_i(A)$ and $W_i(A)$ denote read and write of data item $A$ by transaction $T_i, i=1,2,3$. The transactio...

Consider the following two languages over the alphabet $\{a, b, c\}$, where $m$ and $n$ are natural numbers. $$\begin{aligned} & L_1=\left\{a^m b^m c^{m+n} \mid m, n \geq 1\right\}...

Consider the following two languages over the alphabet $\{a, b\}$ : $$\begin{aligned} & L_1=\left\{\alpha \beta \alpha \mid \alpha \in\{a, b\}^{+} \text {AND } \beta \in\{a, b\}^{+...

Consider the following context-free grammar $G$, where $S, A$, and $B$ are the variables (nonterminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and the ru...

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...

Consider the given function $f(x)$. $$f(x)=\left\{\begin{array}{cc} a x+b & \text { for } x If the function is differentiable everywhere, the value of $b$ must be _________ (Rounde...

A regular language $L$ is accepted by a non-deterministic finite automaton (NFA) with $n$ states. Which of the following statement(s) is/are FALSE?

A box contains 5 coins: 4 regular coins and 1 fake coin. When a regular coin is tossed, the probability $P($ head $)=0.5$ and for a fake coin, $P($ head $)=1$. You pick a coin at r...

A processor has 64 general-purpose registers and 50 distinct instruction types. An instruction is encoded in 32-bits. What is the maximum number of bits that can be used to store t...

Consider the following four variable Boolean function in sum-of-product form $$F\left(b_3, b_2, b_1, b_0\right)=\Sigma(0,2,4,8,10,11,12)$$ where the value of the function is comput...

Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is ________ . (Answer in integer) $$\begin{aligned} & \text {...

Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$. For any two vertices, $u$ and $v$, let $d_1(u, v)$ and $d_2(u, v)$ be the sho...

Consider the following recurrence relation : $$T(n)=2 T(n-1)+n 2^n \text { for } n>0, T(0)=1$$ Which ONE of the following options is CORRECT?

$$\text { 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[]]>A[j + 1]) then swap A[j] and A[j+1] } Let $A[...

Ravi had __________ younger brother who taught at __________ university. He was widely regarded as _________ honorable man. Select the option with the correct sequence of articles...

The CEO's decision to downsize the workforce was considered $$\underline {myopic} $$ because it sacrificed long-term stability to accommodate short-term gains. Select the most appr...

The average marks obtained by a class in an examination were calculated as 30.8 . However, while checking the marks entered, the teacher found that the marks of one student were en...

"I put the brown paper in my pocket along with the chalks, and possibly other things. I suppose every one must have reflected how primeval and how poetical are the things that one...

A fair six-faced dice, with the faces labelled ' 1 ', ' 2 ', ' 3 ', ' 4 ', ' 5 ', and ' 6 ', is rolled thrice. What is the probability of rolling ' 6 ' exactly once?

A shop has 4 distinct flavors of ice-cream. One can purchase any number of scoops of any flavor. The order in which the scoops are purchased is inconsequential. If one wants to pur...

Consider the relationships among $P, Q, R, S$, and $T$ : $\bullet$ $P$ is the brother of $Q$. $\bullet$ $S$ is the daughter of $Q$. $\bullet$ $T$ is the sister of $S$. $\bullet$ $R...

Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. T...

Consider two relations describing teams and players in a sports league: $\bullet$ teams(tid, tname): tid, tname are team-id and team-name, respectively. $\bullet$ players(pid, pnam...

Let $A$ be a $2 \times 2$ matrix as given. $$A=\left[\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}\right]$$ What are the eigenvalues of the matrix $A^{13}$ ?

Consider a demand paging memory management system with 32-bit logical address, 20 -bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable,...

The number -6 can be represented as 1010 in 4-bit 2's complement representation. Which of the following is/are CORRECT 2's complement representation(s) of $-6$ ?

A disk of size 512 M bytes is divided into blocks of 64 K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to sto...

Consider the given system of linear equations for variables $x$ and $y$, where $k$ is a realvalued constant. Which of the following option(s) is/are CORRECT? $$\begin{aligned} & x+...

Consider a probability distribution given by the density function $P(x)$. $$P(x)=\left\{\begin{array}{cc} C x^2, & \text { for } 1 \leq x \leq 4 \\ 0, & \text { for } x 4 \end{arra...

Which ONE of the following techniques used in compiler code optimization uses live variable analysis?

Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: "Everyone has exactly one mother"? The meanings of the predicates used ar...

Let $S$ be the set of all ternary strings defined over the alphabet $\{a, b, c\}$. Consider all strings in $S$ that contain at least one occurrence of two consecutive symbols, that...

Consider a relational schema team(name, city, owner), with functional dependencies \{name $\rightarrow$ city, name $\rightarrow$ owner}. The relation team is decomposed into two re...

The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node. Suppose a Min-Heap $T$ stores 32 keys. The height of $T$ is...

In a double hashing scheme, $h_1(k)=k \bmod 11$ and $h_2(k)=1+(k \bmod 7)$ are the auxiliary hash functions. The size $m$ of the hash table is 11 . The hash function for the $i^{\t...

Which of the following statement(s) is/are TRUE while computing First and Follow during top down parsing by a compiler?

$A=\{0,1,2,3, \ldots\}$ is the set of non-negative integers. Let $F$ be the set of functions from $A$ to itself. For any two functions, $f_1, f_2 \in \mathrm{~F}$ we define $$\left...

Identify the ONE CORRECT matching between the OSI layers and their corresponding functionalities as shown. OSI Layers Functionalities (a) Network layer (I) Packet routing (b) Trans...

Let $G(V, E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maxi...

Suppose a 5-bit message is transmitted from a source to a destination through a noisy channel. The probability that a bit of the message gets flipped during transmission is 0.01. F...

Consider a memory system with 1 M bytes of main memory and 16 K bytes of cache memory. Assume that the processor generates 20-bit memory address, and the cache block size is 16 byt...

Which ONE of the following statements is FALSE regarding the symbol table?

#include <stdio.h> int foo(int S[ ], int size) { if(size == 0) return 0; if(size == 1) return 1; if(S[0]!=S[1]) return 1 + foo(S + 1, size - 1); return foo(S + 1, size - 1); } int...

A packet with the destination IP address 145.36.109.70 arrives at a router whose routing table is shown. Which interface will the packet be forwarded to? Subnet Address Subnet Mask...

#include void foo(int *p, int x) { *p = x; } int main( ) { int *z; int a = 20, b=25; z = &a; foo(z, b); printf("%d", a); return 0; } The output of the given C program is _________....

$g(.)$ is a function from A to B, $f(.)$ is a function from B to C, and their composition defined as $f(g(.))$ is a mapping from A to C. If $f(.)$ and $f(g(.))$ are onto (surjectiv...

Let $X$ be a 3-variable Boolean function that produces output as ' 1 ' when at least two of the input variables are ' 1 '. Which of the following statement(s) is/are CORRECT, where...

Consider the 3-way handshaking protocol for TCP connection establishment. Let the three packets exchanged during the connection establishment be denoted as P1, P2 and P3, in order....

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?

Consider the following C program : #include int gate (int n) { int d, t, newnum, turn; newnum = turn = 0; t=1; while (n>= t) t*= 10; t/=10; while (t>0) { d=n/t; n=n%t; t/= 10; if (...

Suppose in a multiprogramming environment, the following C program segment is executed. A process goes into I/O queue whenever an I/O related operation is performed. Assume that th...

A computer has two processors, $M_1$ and $M_2$. Four processes $P_1, P_2, P_3, P_4$ with CPU bursts of $20,16,25$, and 10 milliseconds, respectively, arrive at the same time and th...

In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algori...

In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is _________. (Answer in integer)

Consider the following statements : (i) Address Resolution Protocol (ARP) provides a mapping from an IP address to the corresponding hardware (link-layer) address. (ii) A single TC...

A 5-stage instruction pipeline has stage delays of $180,250,150,170$, and 250 , respectively, in nanoseconds. The delay of an inter-stage latch is 10 nanoseconds. Assume that there...

Bird : Nest :: Bee : ________ Select the correct option to complete the analogy.

Let $p_1$ and $p_2$ denote two arbitrary prime numbers. Which one of the following statements is correct for all values of $p_1$ and $p_2$ ?

If $P e^x=Q e^{-x}$ for all real values of $x$, which one of the following statements is true?

Given the following syntax directed translation rules : Rule 1 : $R \rightarrow A B\{B . i=R . i-1 ; A . i=B . i R . i=A . i+1 ;\}$ Rule 2 : $P \rightarrow C D\{P . i=C . i+D . i ;...

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...

Consider the routing protocols given in List-I and the names given in List-II: List - I List - II (i) Distance vector routing (a) Bellman-Ford (ii) Link state routing (b) Dijkstra...

Which of the following is/are part of an Instruction Set Architecture of a processor?

Consider the following statements about the use of backpatching in a compiler for (I) Backpatching can be used to generate code for Boolean expression in one pass. (II) Backpatchin...

Consider the following relational schema along with all the functional dependencies that hold on them. $$\begin{aligned} & R 1(A, B, C, D, E):\{D \rightarrow E, E A \rightarrow B,...

Despite his initial hesitation, Rehman's __________ to contribute to the success of the project never wavered. Select the most appropriate option to complete the above sentence.

Which one of the following options is correct for the given data in the table? Iteration ($i$) 0 1 2 3 Input ($I$) 20 $-$4 10 15 Output ($X$) 20 16 26 41 Output ($Y$) 20 $-$80 $-$8...

Based only on the conversation below, identify the logically correct inference: "Even if I had known that you were in the hospital, I would not have gone there to see you", Ramya t...

The value of $x$ such that $x>1$, satisfying the equation $\int_1^x t \ln t d t=\frac{1}{4}$ is

The following two signed 2's complement numbers (multiplicand M and multiplier Q ) are being multiplied using Booth's algorithm : M : 1100110111101101 and Q : 1010010010101010 The...

A machine receives an IPv4 datagram. The protocol field of the IPv4 header has the protocol number of a protocol X . Which ONE of the following is NOT a possible candidate for X ?

Given a computing system with two levels of cache (L1 and L2) and a main memory. The first level (L1) cache access time is 1 nanosecond (ns) and the "hit rate" for L1 cache is $90...

If $A=\left(\begin{array}{cc}1 & 2 \\ 2 & -1\end{array}\right)$, then which ONE of the following is $A^8$ ?

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

Consider the following C program : #include <stdio.h> void stringcopy(char *, char *); int main( ) { char a[30] = "@#Hello world!"; stringcopy(a,a+2); printf("%s\n", a); return 0;...

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...

Let $P(x)$ be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?

Given a Context-Free Grammar G as follows : $S \rightarrow A a|b a c| d c \mid b d a$ $A \rightarrow d$ Which ONE of the following statements is TRUE?

Suppose the values $10,-4,15,30,20,5,60,19$ are inserted in that order into an initially empty binary search tree. Let $T$ be the resulting binary search tree. The number of edges...

In a $\mathrm{B}^{+}$- tree where each node can hold at most four key values, a root to leaf path consists of the following nodes: $$A=(49,77,83,-), B=(7,19,33,44), C=\left(20^*, 2...

Processes $P 1, P 2, P 3, P 4$ arrive in that order at times $0,1,2$, and 8 milliseconds respectively, and have execution times of $10,13,6$, and 9 milliseconds respectively. Short...

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 oth...

Consider the following C program : #include <stdio.h> int g(int n) { return (n+10); } int f(int n) { return g(n*2); } int main() { int sum, n; sum=0; for (n=1; n The output of the...

The unit interval $(0,1)$ is divided at a point chosen uniformly distributed over $(0,1)$ in $R$ into two disjoint subintervals. The expected length of the subinterval that contain...

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 UD...

A computer system supports a logical address space of 232 bytes. It uses two-level hierarchical paging with a page size of 4096 bytes. A logical address is divided into a b-bit ind...

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

If IMAGE and FIELD are coded as FHBNJ and EMFJG respectively then, which one among the given options is the most appropriate code for BEACH ?

Three floating point numbers $X, Y$, and $Z$ are stored in three registers $R_X, R_Y$, and $R_Z$, respectively in IEEE 754 single precision format as given below in hexadecimal: $$...

Consider a binary tree $T$ in which every node has either zero or two children. Let $n>0$ be the number of nodes in $T$. Which ONE of the following is the number of nodes in $T$ th...

int x = 126, y = 105; do{ if(x > y) x = x - y; else y = y - x; }while(x!=y); printf('%d", x); The output of the given C code segment is __________. (Answer in integer)

Consider two grammars $G_1$ and $G_2$ with the production rules given below: $G_1: S \rightarrow$ if $E$ then $S \mid$ if $E$ then $S$ else $S \mid a$ $$\mathrm{E} \rightarrow \mat...

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

Consider the two lists List-I and List-II given below: List - I List - II (i) Context free languages (a) Closed under union (ii) Recursive languages (b) Not closed under complement...

Let $G_1, G_2$ be Context Free Grammars (CFGs) and $R$ be a regular expression. For a grammar $G$, let $L(G)$ denote the language generated by $G$. Which ONE among the following qu...

Let $\Sigma=\{a, b, c\}$. For $x \in \Sigma^{\star}$, and $\alpha \in \Sigma$, let $\#_\alpha(x)$ denote the number of occurrences of a in $x$. Which one or more of the following o...

Let $\Sigma=\{1,2,3,4\}$ For $x \in \Sigma^*$, let prod $(x)$ be the product of symbols in $x$ modulo 7 . We take $\operatorname{prod}(\varepsilon)=1$, where $\varepsilon$ is the n...

Let $F$ be the set of all functions from $\{1, \ldots, n\}$ to $\{0,1\}$. Define the binary relation $\preccurlyeq$ on $F$ as follows: $\forall f . g \in F, f \preccurlyeq g$ if an...

Consider the following relational schema: Students ($$\mathrm{\underline {rollno:integer}}$$, name: string, age: integer, cgpa: real) Courses ($$\mathrm{\underline {courseno:intege...

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures: P: Unsorted doubly...

Suppose we are transmitting frames between two nodes using Stop-and-Wait protocol. The frame size is 3000 bits. The transmission rate of the channel is 2000 bps (bits/ second) and...

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

A quadratic polynomial $(x-\alpha)(x-\beta)$ over complex numbers is said to be square invariant if $(x-\alpha)(x-\beta)=\left(x-\alpha^2\right)\left(x-\beta^2\right)$. Suppose fro...

Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct. We wi...

$P=\left\{P_1, P_2, P_3, P_4\right\}$ consists of all active processes in an operating system. $R=\left\{R_1, R_2, R_3, R_4\right\}$ consists of single instances of distinct types...

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 state...

Consider an unordered list of $N$ distinct integers. What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

An array $A$ of length $n$ with distinct elements is said to be bitonic if there is an index $1=i=n$ such that $A[1 . . i]$ is sorted in the non-decreasing order and $A[i+1 . . n]$...

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

Consider the following C program : #include <stdio.h> int main( ) { int a; int arr[5]={30,50,10}; int *ptr; ptr = &arr[0] + 1; a = *ptr; (*ptr)++; ptr++; printf("%d",a + (*ptr) + a...

Ravi had _______ younger brother who taught at _______ university. He was widely regarded as _______ honorable man. Select the option with the correct sequence of articles to fill...

The CEO's decision to downsize the workforce was considered myopic because it sacrificed long-term stability to accommodate short-term gains. Select the most appropriate option tha...

The average marks obtained by a class in an examination were calculated as 30.8. However, while checking the marks entered, the teacher found that the marks of one student were ent...

Consider the relationships among P, Q, R, S, and T: * P is the brother of Q. * S is the daughter of Q. * T is the sister of S. * R is the mother of Q. The following statements are...

According to the map shown in the figure, which one of the following statements is correct? Note: The figure shown is representative.

“I put the brown paper in my pocket along with the chalks, and possibly other things. I suppose every one must have reflected how primeval and how poetical are the things that one...

In the diagram, the lines QR and ST are parallel to each other. The shortest distance between these two lines is half the shortest distance between the point P and line QR. What is...

A fair six-faced dice, with the faces labelled '1', '2', '3', '4', '5', and '6', is rolled thrice. What is the probability of rolling '6' exactly once?

A square paper, shown in figure (I), is folded along the dotted lines as shown in the figures (II) and (III). Then a few cuts are made as shown in figure (IV). Which one of the fol...

A shop has 4 distinct flavors of ice-cream. One can purchase any number of scoops of any flavor. The order in which the scoops are purchased is inconsequential. If one wants to pur...

Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. T...

Which ONE of the following statements is FALSE regarding the symbol table?

Which ONE of the following techniques used in compiler code optimization uses live variable analysis?

Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, w...

A schedule of three database transactions T1, T2, and T3 is shown. Ri(A) and Wi(A) denote read and write of data item A by transaction Ti, i = 1,2,3. The transaction T1 aborts at t...

Identify the ONE CORRECT matching between the OSI layers and their corresponding functionalities as shown. OSI Layers (a) Network layer (b) Transport layer (c) Datalink layer Funct...

g(.) is a function from A to B, f(.) is a function from B to C, and their composition defined as f(g(.)) is a mapping from A to C. If f(.) and f(g(.)) are onto (surjective) functio...

Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices, u and v, let d₁(u, v) and d₂(u, v) be the shortest distances...

Consider the following context-free grammar G, where S, A, and B are the variables (non-terminals), a and b are the terminal symbols, S is the start variable, and the rules of G ar...

Consider the following recurrence relation: T(n) = 2T(n - 1) + n2^n for n > 0, T(0) = 1. Which ONE of the following options is CORRECT?

Consider the following B+ tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the B+ tree. Which of the following options(s) is/are C...

Consider the 3-way handshaking protocol for TCP connection establishment. Let the three packets exchanged during the connection establishment be denoted as P1, P2, and P3, in order...

Consider the given system of linear equations for variables x and y, where k is a real-valued constant. Which of the following option(s) is/are CORRECT? x + ky = 1 kx + y = -1

Let X be a 3-variable Boolean function that produces output as '1' when at least two of the input variables are '1'. Which of the following statement(s) is/are CORRECT, where a, b,...

The number -6 can be represented as 1010 in 4-bit 2's complement representation. Which of the following is/are CORRECT 2's complement representation(s) of -6?

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having n distinct integers?

A partial data path of a processor is given in the figure, where RA, RB, and RZ are 32-bit registers. Which option(s) is/are CORRECT related to arithmetic operations using the data...

A regular language L is accepted by a non-deterministic finite automaton (NFA) with n states. Which of the following statement(s) is/are FALSE?

Suppose in a multiprogramming environment, the following C program segment is executed. A process goes into I/O queue whenever an I/O related operation is performed. Assume that th...

Let S be the set of all ternary strings defined over the alphabet {a, b, c}. Consider all strings in S that contain at least one occurrence of two consecutive symbols, that is, "aa...

Consider the given function $f(x)$. $f(x) = \begin{cases} ax + b & \text{for } x < 1 \\ x^3 + x^2 + 1 & \text{for } x \ge 1 \end{cases}$ If the function is differentiable everywher...

A box contains 5 coins: 4 regular coins and 1 fake coin. When a regular coin is tossed, the probability P(head) = 0.5 and for a fake coin, P(head) = 1. You pick a coin at random an...

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, ...,29] be an array...

#include void foo(int *p, int x) { *p=x; } int main() { int *z; int a = 20, b = 25; z = &a; foo(z,b); printf("%d",a); return 0; } The output of the given C program is __________. (...

The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node. Suppose a Min-Heap T stores 32 keys. The height of T is ___...

Consider a memory system with 1M bytes of main memory and 16K bytes of cache memory. Assume that the processor generates 20-bit memory address, and the cache block size is 16 bytes...

A processor has 64 general-purpose registers and 50 distinct instruction types. An instruction is encoded in 32-bits. What is the maximum number of bits that can be used to store t...

A computer has two processors, M₁ and M₂. Four processes P₁, P₂, P₃, P₄ with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the...

Consider two relations describing teams and players in a sports league: * teams (tid, tname): tid, tname are team-id and team-name, respectively * players(pid, pname, tid): pid, pn...

A packet with the destination IP address 145.36.109.70 arrives at a router whose routing table is shown. Which interface will the packet be forwarded to? Subnet Address Subnet Mask...

Let A be a 2 x 2 matrix as given. $A = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$ What are the eigenvalues of the matrix $A^{13}$ ?

Consider the following four variable Boolean function in sum-of-product form $F(b_3, b_2, b_1, b_0) = \Sigma(0, 2, 4, 8, 10, 11, 12)$. where the value of the function is computed b...

Let G(V, E) be an undirected and unweighted graph with 100 vertices. Let d(u, v) denote the number of edges in a shortest path between vertices u and v in V. Let the maximum value...

Consider the following two languages over the alphabet {a, b}: L₁ = { αβα |α ∈ {a,b}+ AND β∈ {a,b}+ } L₂ = {αβα|α ∈ {a}+ AND β∈ {a,b}+ } Which ONE of the following statements is CO...

Consider the following two languages over the alphabet {a, b, c}, where m and n are natural numbers. L₁ = {a^m b^m c^(m+n) | m, n ≥ 1} L₂ = {a^m b^n c^(m+n) | m, n ≥ 1} Which ONE o...

Which of the following statement(s) is/are TRUE while computing First and Follow during top down parsing by a compiler?

Consider a relational schema team (name, city, owner), with functional dependencies {name → city, name → owner}. The relation team is decomposed into two relations, t1(name, city)...

Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: "Everyone has exactly one mother"? The meanings of the predicates used ar...

A = {0, 1, 2, 3, ...} is the set of non-negative integers. Let F be the set of functions from A to itself. For any two functions, f1, f2 ∈ F, we define (f1⨀f2)(n) = f1(n) + f2(n) f...

Consider the following deterministic finite automaton (DFA) defined over the alphabet, $\Sigma = \{a, b\}$. Identify which of the following language(s) is/are accepted by the given...

A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store...

Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is ________. (Answer in integer) 1001: i = 1 1002: j = 1 1003:...

A computer has a memory hierarchy consisting of two-level cache (L1 and L2) and a main memory. If the processor needs to access data from memory, it first looks into L1 cache. If t...

In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algori...

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 S...

Suppose a 5-bit message is transmitted from a source to a destination through a noisy channel. The probability that a bit of the message gets flipped during transmission is 0.01. F...

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 tr...

Consider a probability distribution given by the density function P(x). P(x) = {Cx^2, for 1 ≤ x ≤ 4 0, for x 4 The probability that x lies between 2 and 3, i.e., P(2 ≤ x ≤ 3) 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...

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 thr...

#include int foo(int S[],int size) { if(size == 0) return 0; if(size == 1) return 1; if(S[0] != S[1]) return 1+foo(S+1,size-1); return foo(S+1,size-1); } int main() { int A[]={0,1,...

Let LIST be a datatype for an implementation of linked list defined as follows: typedef struct list { int data; struct list *next; } LIST; Suppose a program has created two linked...

Consider the following C program: #include int gate (int n) { int d, t, newnum, turn; newnum = turn = 0; t=1; while (n>=t) t *= 10; t /=10; while (t>0) { d = n/t; n = n%t; t /= 10;...

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)

In a double hashing scheme, h₁(k) = k mod 11 and h₂(k) = 1 + (k mod 7) are the auxiliary hash functions. The size m of the hash table is 11. The hash function for the i-th probe in...

Despite his initial hesitation, Rehman's ________ to contribute to the success of the project never wavered. Select the most appropriate option to complete the above sentence.

Bird : Nest :: Bee : ________ Select the correct option to complete the analogy.

If $Pe^x = Qe^{-x}$ for all real values of $x$, which one of the following statements is true?

The paper as shown in the figure is folded to make a cube where each square corresponds to a particular face of the cube. Which one of the following options correctly represents th...

Let $p_1$ and $p_2$ denote two arbitrary prime numbers. Which one of the following statements is correct for all values of $p_1$ and $p_2$?

Based only on the conversation below, identify the logically correct inference: "Even if I had known that you were in the hospital, I would not have gone there to see you", Ramya t...

If IMAGE and FIELD are coded as FHBNJ and EMFJG respectively then, which one among the given options is the most appropriate code for BEACH ?

Which one of the following options is correct for the given data in the table?

In the given figure, PQRS is a square of side 2 cm and PLMN is a rectangle. The corner L of the rectangle is on the side QR. Side MN of the rectangle passes through the corner S of...

The diagram below shows a river system consisting of 7 segments, marked P, Q, R, S, T, U, and V. It splits the land into 5 zones, marked Z1, Z2, Z3, Z4, and Z5. We need to connect...

If A = $\begin{pmatrix} 1 & 2 \ -2 & -1 \end{pmatrix}$, then which ONE of the following is A⁸ ?

The value of x such that x > 1, satisfying the equation $\int_{1}^{x} t \ln t \, dt = \frac{1}{4}$ is

Consider a binary tree T in which every node has either zero or two children. Let n > 0 be the number of nodes in T. Which ONE of the following is the number of nodes in T that hav...

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

Let P(x) be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?

Consider the following statements: (i) Address Resolution Protocol (ARP) provides a mapping from an IP address to the corresponding hardware (link-layer) address. (ii) A single TCP...

Consider the routing protocols given in List I and the names given in List II: List I (i) Distance vector routing (ii) Link state routing List II (a) Bellman-Ford (b) Dijkstra For...

A machine receives an IPv4 datagram. The protocol field of the IPv4 header has the protocol number of a protocol X. Which ONE of the following is NOT a possible candidate for X?

Consider the following C program: #include void stringcopy (char *, char *); int main() { char a [30] = "@#Hello World!"; stringcopy (a, a + 2); printf("%s\n", a); return 0; } void...

Consider an unordered list of N distinct integers. What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

Consider the following statements about the use of backpatching in a compiler for intermediate code generation: (I) Backpatching can be used to generate code for Boolean expression...

Given the following syntax directed translation rules: Rule 1: R → AB {B.i = R.i - 1; A.i = B.i; R.i = A.i + 1; } Rule 2: P → CD {P.i = C.i + D.i; D.i = C.i + 2; } Rule 3: Q → EF {...

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 UD...

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

Let G1, G2 be Context Free Grammars (CFGs) and R be a regular expression. For a grammar G, let L(G) denote the language generated by G. Which ONE among the following questions is d...

Processes P1, P2, P3, P4 arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Re...

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...

Which of the following is/are part of an Instruction Set Architecture of a processor?

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

Consider the two lists List I and List II given below: List I (i) Context free languages (ii) Recursive languages (iii) Regular languages List II (a) Closed under union (b) Not clo...

Consider the following logic circuit diagram. Which is/are the CORRECT option(s) for the output function F?

The following two signed 2's complement numbers (multiplicand M and multiplier Q) are being multiplied using Booth's algorithm: M: 1100 1101 1110 1101 and Q: 1010 0100 1010 1010 Th...

int x=126,y=105; do { if (x>y) x=x-y; else y=y-x; } while(x!=y); printf("%d",x); The output of the given C code segment is __________. (Answer in integer)

In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is __________. (Answer in integer...

Suppose the values 10, -4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let T be the resulting binary search tree. The number of edg...

Suppose we are transmitting frames between two nodes using Stop-and-Wait protocol. The frame size is 3000 bits. The transmission rate of the channel is 2000 bps (bits/second) and t...

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 stateme...

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures: P: Unsorted doubly...

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 oth...

Given a Context-Free Grammar G as follows: S→Aa | bAc | dc | bda A→d Which ONE of the following statements is TRUE?

An array A of length n with distinct elements is said to be bitonic if there is an index 1 ≤ i ≤ n such that A[1..i] is sorted in the non-decreasing order and A[i + 1..n] is sorted...

Let F be the set of all functions from {1,..., n} to {0,1}. Define the binary relation ≤ on F as follows: ∀f,g∈F, f≤ g if and only if ∀x ∈ {1, ..., n}, f(x) ≤ g(x), where 0 ≤ 1. Wh...

Given the following Karnaugh Map for a Boolean function F(w,x, y, z): Which one or more of the following Boolean expression(s) represent(s) F?

Consider a system of linear equations $PX = 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 $L =...

Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct. We wi...

Consider the following relational schema along with all the functional dependencies that hold on them. R1(A, B, C, D, E): { D → E, EA → B, EB → C} R2(A, B, C, D): { A → D, A → B, C...

Consider a demand paging system with three frames, and the following page reference string: 123454164513 2. The contents of the frames are as follows initially and after each refer...

P = {P1, P2, P3, P4} consists of all active processes in an operating system. R = {R1, R2, R3, R4} consists of single instances of distinct types of resources in the system. The re...

Three floating point numbers X, Y, and Z are stored in three registers Rx, Ry, and Rz, respectively in IEEE 754 single precision format as given below in hexadecimal: Rx = 0xC11000...

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

Consider two grammars G₁ and G₂ with the production rules given below: G₁: S → if E then S | if E then S else S | a E → b G₂: S → if E then S | M M → if E then M else S | c E → b w...

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

Consider the database transactions T1 and T2, and data items X and Y. Which of the schedule(s) is/are conflict serializable? Transaction T1 R1(X) W1(Y) R1(X) W1(X) COMMIT(T1) Trans...

Consider the following relational schema: Students (rollno: integer, name: string, age: integer, cgpa: real) Courses (courseno: integer, cname: string, credits: integer) Enrolled (...

Given a computing system with two levels of cache (L1 and L2) and a main memory. The first level (L1) cache access time is 1 nanosecond (ns) and the "hit rate" for L1 cache is 90%...

A 5-stage instruction pipeline has stage delays of 180, 250, 150, 170, and 250, respectively, in nanoseconds. The delay of an inter-stage latch is 10 nanoseconds. Assume that there...

In a B+- tree where each node can hold at most four key values, a root to leaf path consists of the following nodes: A = (49, 77, 83, -), B = (7, 19, 33, 44), C = (20*, 22*, 25*, 2...

A computer system supports a logical address space of 2^32 bytes. It uses two-level hierarchical paging with a page size of 4096 bytes. A logical address is divided into a b-bit in...

Consider the following algorithm someAlgo that takes an undirected graph G as input. someAlgo (G) 1. Let v be any vertex in G. Run BFS on G starting at v. Let u be a vertex in G at...

Let Σ = {1,2,3,4}. For x ∈ Σ*, let prod(x) be the product of symbols in x modulo 7. We take prod(ε) = 1, where ε is the null string. For example, prod(124) = (1 × 2 × 4) mod 7 = 1....

An application executes 6.4 × 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...

Consider the following C program: #include int main() { int a; int arr[5] = {30,50,10}; int *ptr; ptr = &arr[0] + 1; a = *ptr; (*ptr)++; ptr++; printf("%d", a + (*ptr) + arr[1]); r...

Consider the following C program: #include int g(int n) { return (n+10); } int f(int n) { return g(n*2); } int main(){ int sum, n; sum=0; for (n=1; n<3; n++) sum += g(f(n)); printf...

A quadratic polynomial $(x - \alpha)(x - \beta)$ over complex numbers is said to be square invariant if $(x - \alpha)(x - \beta) = (x - \alpha^2)(x - \beta^2)$. Suppose from the se...

The unit interval (0,1) is divided at a point chosen uniformly distributed over (0,1) in R into two disjoint subintervals. The expected length of the subinterval that contains 0.4...