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?

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?

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 in the non-increasing order.

Which ONE of the following represents the best possible asymptotic bound for the worstcase number of comparisons by an algorithm that searches for an element in a bitonic array $A$?

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) Backpatching can be used to generate code for flow-of-control statements in one pass.

Which ONE of the following options is CORRECT?

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 ; D . i=C . i+2\}$

Rule 3 : $Q \rightarrow E F\{Q . i=E . i+F . i ;\}$

Which ONE is the CORRECT option among the following?

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?

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 \mathrm{~b}$$

$G_2: S \rightarrow$ if $E$ then $S \mid M$

$E \rightarrow$ if $E$ then $M$ else $S \mid c$

$$\mathrm{E} \rightarrow \mathrm{~b}$$

where if, then, else, $a, b, c$ are the terminals.

Which of the following option(s) is/are CORRECT?

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 segment from a sender $S$ to a receiver $R$ cannot carry both data from $S$ to $R$ and acknowledgement for a segment from $R$ to $S$.

Which ONE of the following is CORRECT?

Consider the routing protocols given in List-I and the names given in List-II:

For matching of items in List-I with those in List-II, which ONE of the following options is CORRECT?

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

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 the propagation delay between the two nodes is 100 milliseconds. Assume that the processing times at the source and destination are negligible. Also, assume that the size of the acknowledgement packet is negligible. Which ONE of the following most accurately gives the channel utilization for the above scenario in percentage?

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

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?

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 \%$ while the processor is accessing the data from L1 cache. Whereas, for the second level (L2) cache, the "hit rate" is $80 \%$ and the "miss penalty" for transferring data from L2 cache to L1 cache is 10 ns . The "miss penalty" for the data to be transferred from main memory to L2 cache is 100 ns . Then the average memory access time in this system in nanoseconds is (rounded off to one decimal place)

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 are no pipeline stalls due to branches and other hazards. The time taken to process 1000 instructions in microseconds is ________ . (Rounded off to two decimal places)

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)

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 have exactly two children?

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are 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 the path from the node containing 19 to the root node of $T$ is ________ (Answer in integer)

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 linked list with pointers to the head node and tail node of the list.

Q: Min-heap implemented using an array.

R: Binary Search Tree.

Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size $n$ of these data structures?

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 wish to augment the stack data structure with an $\mathrm{O}(1)$ time MIN operation that returns a pointer to the record with smallest key present in the stack

1. without deleting the corresponding record, and

2. without increasing the complexities of the standard stack operations.

Which one or more of the following approach(es) can achieve it?

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 maximum distance from $v$ as given by the BFS.

2. Run BFS on $G$ again with $u$ as the starting vertex. Let $z$ be the vertex at maximum distance from $u$ as given by the BFS.

3. Output the distance between $u$ and $z$ in $G$.

The output of someAlgo( $T$ ) for the tree shown in the given figure is $\qquad$ . (Answer in integer)

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?

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, E B \rightarrow C\} \\ & R 2(A, B, C, D):\{A \rightarrow D, A \rightarrow B, C \rightarrow A\} \end{aligned}$$

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

Consider the database transactions T 1 and T 2, and data items X and Y . Which of the schedule(s) is/are conflict serializable?

Consider the following relational schema:

Students ($$\mathrm{\underline {rollno:integer}}$$, name: string, age: integer, cgpa: real)

Courses ($$\mathrm{\underline {courseno:integer}}$$, cname: string, credits: integer)

Enrolled ($$\mathrm{\underline {rollno:integer}}$$, $$\mathrm{\underline {courseno:integer}}$$, grade: string)

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 ?$

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^*, 22^*, 25^*, 26^*\right)$$

The *-marked keys signify that these are data entries in a leaf.

Assume that a pointer between keys $k_1$ and $k_2$ points to a subtree containing keys in [ $k_1, k_2$ ], and that when a leaf is created, the smallest key in it is copied up into A record with key value 23 is inserted into the $\mathrm{B}^{+}$- tree.

The smallest key value in the parent of the leaf that contains $25^*$ is _________ . (Answer in integer)

Consider the following logic circuit diagram.

Which is/are the CORRECT option(s) for the output function?

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 total number of addition and subtraction operations to be performed 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)

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?

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:

$$R_X=0 \times C 1100000, R_Y=0 \times 40 C 00000, \text { and } R_Z=0 \times 41400000$$

Which of the following option(s) is/are CORRECT?

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

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

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

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?

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 and only if $\forall x \in\{1, \ldots, n\}, f(x) \leq g(x)$, where $0=1$.

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

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=\left[\begin{array}{ccc} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{array}\right] \text { and } u=\left[\begin{array}{ccc} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{array}\right]$$

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

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 from the set of all square invariant quadratic polynomials we choose one at random.

The probability that the roots of the chosen polynomial are equal is (rounded off to one decimal place)

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 is _________ . (rounded off to two decimal places)

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. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times.
Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?

Consider a demand paging system with three frames, and the following page reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2 . The contents of the frames are as follows initially and after each reference (from left to right):

The *-marked references cause page replacements.

Which one or more of the following could be the page replacement policy/policies in use?

$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 of resources in the system.

The resource allocation graph has the following assignment and claim edges.

Assignment edges: $R_1 \rightarrow P_1, R_2 \rightarrow P_2, R_3 \rightarrow P_3, R_4 \rightarrow P_4$ (the assignment edge $R_1 \rightarrow P_1$ means resource $R_1$ is assigned to process $P_1$, and so on for others) Claim edges: $P_1 \rightarrow R_2, P_2 \rightarrow R_3, P_3 \rightarrow R_1, P_2 \rightarrow R_4, P_4 \rightarrow R_2$ (the claim edge $P_1 \rightarrow R_2$ means process $P_1$ is waiting for resource $R_2$, and so on for others) Which of the following statement(s) is/are CORRECT?

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 index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry of the inner page table uses eight bytes. All the pages in the system have the same size. The value of $b$ is _________ . (Answer in integer)

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;
}
void sringcopy(char *s, char *t) {
    while(*t)
        *st++ = *t++;
}

Which ONE of the following will be the output of the program?

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 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) + arr[1]);
    return 0;
}

The output of the above program is _________. (Answer in integer)

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<3; n++)
    sum += g(f(n));
    printf("%d", sum);
    return 0;
}

The output of the given C program is ________. (Answer in integer)

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

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 questions is decidable?

Consider the two lists List-I and List-II given below:

For matching of items in List-I with those in List-II, which of the following option(s) is/ are CORRECT?

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 option(s) define(s) regular language(s)?

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

For example, $\operatorname{prod}(124)=(1 \times 2 \times 4) \bmod 7=1$.

Define $L=\left\{x \in \Sigma^{\star} \mid \operatorname{prod}(x)=2\right\}$.

The number of states in a minimum state DFA for $L$ is _________ (Answer in integer)

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 $P e^x=Q e^{-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 the cube?

Note: The figures shown are representative.

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

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

What is the area (in $\mathrm{cm}^2$ ) of the rectangle PLMN?

Note: The figure shown is representative

The diagram below shows a river system consisting of 7 segments, marked $P, Q, R$, $\mathrm{S}, \mathrm{T}, \mathrm{U}$, and V . It splits the land into 5 zones, marked $\mathrm{Z} 1, Z 2, Z 3, Z 4$, and $Z 5$. We need to connect these zones using the least number of bridges. Out of the following options, which one is correct?

Note: The figure shown is representative.