The antonym of the word protagonist is ________.

B. Answer: (B) antagonist A protagonist is the leading character or a champion of a cause. Its opposite is the antagonist, the one who opposes the protagonist. The other words are unrelated: an agnostic doubts that God's existence can be known, an arsonist sets fires on purpose, and an anarchist rejects all government.

The figure shows two 4-tile patterns. Either one or both of the patterns can be used any number of times and in any orientation to construct a new pattern. Which one of the options below cannot be constructed by using only these two 4-tile patterns assuming there are no overlaps among them?

C. Answer: (C) Quick test: every piece has 4 tiles, so any shape built from them must have a tile count that is a multiple of 4. • (A) 2 × 4 = 8 tiles: two 2 × 2 squares, or two horizontal bars. • (B) 3 × 4 = 12 tiles: three horizontal bars. • (C) 3 × 5 = 15 tiles: 15 is not a multiple of 4, so it is impossible. • (D) 4 × 5 = 20 tiles: five vertical bars.

Consider a knock-out women’s badminton singles tournament where there are no ties. The loser in each game is eliminated from the tournament. Every player plays until she is defeated or remains the last undefeated player. The last undefeated player is declared the winner of the tournament. If there are 64 players in the beginning of the tournament, how many games should be played in total to declare the winner of the tournament?

C. Answer: (C) 63 Each game eliminates exactly one player. To go from 64 players to 1 winner, 63 players must be eliminated, so 63 games are needed. Round by round: 32 + 16 + 8 + 4 + 2 + 1 = 63.

A student needs to enroll for a minimum of 60 credits. A student cannot enroll for more than 70 credits. The credits are divided amongst project and three distinct sets of courses namely, core courses, specialization courses, and elective courses. It is compulsory for a student to enroll for exactly 15 credits of core courses and exactly 20 credits of project. In addition, a student has to enroll for a minimum of 10 credits of specialization courses. The maximum credits of elective courses that

D. Answer: (D) 25 To maximise electives, take the overall maximum and the minimum everywhere else: \text{Electives} = 70 - 15\ (\text{core}) - 20\ (\text{project}) - 10\ (\text{specialisation}) = 25

‘When the teacher is in the room, all students stand silently.’ If the above statement is true, which one of the following statements is not necessarily true?

C. Answer: (C) Write the statement as T \Rightarrow S, where T = "teacher in room" and S = "all students stand silently". • (A) is the contrapositive \neg S \Rightarrow \neg T, so it is always true. • (B) and (D) are weaker parts of S ("silent", "standing"), so they follow. • (C) says "standing \Rightarrow T". That is a form of the converse, which does not follow. Students may stand even when the teacher is away.

Combinatorics deals with problems involving counting. For example, “How many distinct arrangements of N distinct objects in M spaces on a circle are possible?” is a typical problem in combinatorics. This kind of counting is sometimes used in the modeling of several physical phenomena. Often, in such models, the different combinatorial possibilities are assigned probability values. Assigning probabilities enables the computation of the average values of physical quantities. Consider the following

B. Answer: (B) P is false. The passage says counting is sometimes used in modelling. "Always" overstates it. Q is true. It restates the last two sentences: in such models, possibilities are assigned probabilities so that average values can be computed.

In Panel I of the figure below, the front view and top view of a structure are shown. Which one of the 3D structures shown in Panel II possesses the views shown in Panel I?

D. Answer: (D) (iv) (official key) Method: check each structure against one view at a time and drop it as soon as one feature disagrees. • Front view: only one column reaches the top level, and it sits at the far left. Below it, the right-hand part is one step lower, with a separate small cube at the bottom right. • Top view: a strip runs along the left, and the right part forms an L-shape with the front-right corner cut away. • (i) The right part is one continuous slab, so the front view would hav

For positive real numbers S and K, the function H_K(S) is defined as: H_K(S) = \max(S-K,\,0). The max function is defined as: \max(a,b) = \begin{cases} a, & \text{when } a > b \\ b, & \text{when } a \le b \end{cases} The graph below shows the plot of a function N(S) versus S. N(S) can be expressed as _____.

A. Answer: (A) H_K(S) is a "hinge": 0 up to K, then a line of slope 1. Read the graph off as slopes: slope 0 before 10, slope +1 from 10 to 20, then slope 0 again. Switching the slope on at 10 gives +H_{10}, and switching it off at 20 gives -H_{20}. Check: N(25) = 15 - 5 = 10 ✓, N(15) = 5 - 0 = 5 ✓, N(5) = 0 ✓. (B) would make the graph slope down after 20, (C) would go negative between 10 and 20, and (D) would start rising at 15.

In the 2020 summer Olympics’ Javelin throw finals, Neeraj Chopra exhibited a spectacular performance to win the gold medal. The silver medal was won by Jakub Vadlejch and the bronze medal was won by Vitezlav Vesely. There were six rounds of throws with each athlete having one throw per round. The best of all the throws of each athlete is considered for the medal. Following were the observations about the throws: • The first and second rounds were dominated by Neeraj Chopra with a gold medal perf

A. Answer: (A) Third • (i) His best throw was not in round 1 or 2. • (ii) Round 6 was a foul. • (iii) His best came within the first four rounds and was never improved, so it is in round 3 or 4. • Suppose it was round 4. By (iv), Jakub's round-4 throw beat it, so Jakub would be ahead of Vesely after four rounds. That contradicts (iii), which puts Vesely second. So the best throw was in round 3.

An urn contains one red ball and one blue ball. At each step, a ball is picked uniformly at random from the urn, and this ball together with another ball of the same color is put back in the urn. The probability that there are equal number of red and blue balls after two steps is

B. Answer: (B) 1/3 Start with (R, B) = (1, 1). After two steps there are 4 balls, so "equal" means (2, 2). That needs one red pick and one blue pick. • Red then blue: \tfrac12 \times \tfrac13 = \tfrac16. After the red pick the urn is (2, 1), so blue has probability 1/3. • Blue then red: \tfrac12 \times \tfrac13 = \tfrac16, by symmetry. Total = \tfrac16 + \tfrac16 = \tfrac13. (This is Pólya's urn: after n steps, every red count from 1 to n+1 is equally likely, so the chance is \tfrac13.)

Consider 4 \times 4 matrices with their elements from \{0, 1\}. The number of such matrices with even number of 1s in every row and every column is

A. Answer: (A) 512 Fill the top-left 3 \times 3 block freely: 2^9 ways. Then: • the last entry of each of the first three rows is forced, to make that row's parity even; • the last entry of each of the first three columns is forced the same way; • the bottom-right corner is forced too, and both its row and its column agree on it, because the total number of 1s in the first three rows equals the total in the first three columns (mod 2). Count = 2^{(n-1)^2} = 2^9 = 512.

For n > 1, the maximum multiplicity of any eigenvalue of an n \times n matrix with elements from \mathbb{R} is

A. Answer: (A) n The characteristic polynomial has degree n, so no eigenvalue can repeat more than n times. The bound is reached by the identity matrix I_n, whose eigenvalue 1 has multiplicity n.

Match each addressing mode in List I with a data element or an element of a data structure (in a high-level language) in List II: List I | List II ---------------------------------+----------------------- P. Immediate | 1. Element of an array Q. Indirect | 2. Pointer R. Base with index | 3. Element of a record S. Base with offset/displacement | 4. Constant

B. Answer: (B) P–4, Q–2, R–1, S–3 • Immediate: the operand is in the instruction itself, so it is a constant. • Indirect: the instruction holds the address of the address, which is how a pointer is dereferenced. • Base + index: base address of the array plus a variable index register gives a[i]. • Base + fixed displacement: the start of a struct plus a fixed field offset gives r.field.

Consider a processor P whose instruction set architecture is the load-store architecture. The instruction format is such that the first operand of any instruction is the destination operand. Which one of the following sequences of instructions corresponds to the high-level language statement Z = X + Y ? Note: X, Y, and Z are memory operands. R0, R1, and R2 are registers.

D. Answer: (D) In a load-store (RISC-style) ISA, only LOAD and STORE touch memory, and every ALU instruction works on registers only. (A), (B) and (C) each have an ADD with a memory operand, so they are illegal. (D) loads both operands, adds them in registers, then stores the result.

Which one of the following dependencies among the register operands of different instructions can cause a data hazard in a pipelined processor?

B. Answer: (B) Read-after-write RAW is a true data dependence: a later instruction needs a value that an earlier one has not yet written back. In an in-order pipeline this causes stalls or needs forwarding. RAR is never a hazard. WAR and WAW are name dependences, and they become hazards only in out-of-order or multi-path pipelines. The official key accepts only RAW.

Consider the following recurrence relations: For all n > 1, T_1(n) = 4T_1\!\left(\tfrac{n}{2}\right) + T_2(n) \qquad T_2(n) = 5T_2\!\left(\tfrac{n}{4}\right) + \Theta(\log_2 n) Assume that for all n \le 1, T_1(n) = 1 and T_2(n) = 1. Which one of the following options is correct?

A. Answer: (A) \Theta(n^2) Step 1, solve T_2: a=5, b=4, so n^{\log_4 5} \approx n^{1.16}. This dominates \log n polynomially (Master theorem case 1), giving T_2(n) = \Theta(n^{\log_4 5}). Step 2, solve T_1: a=4, b=2, so n^{\log_2 4} = n^2. The extra term n^{1.16} is polynomially smaller than n^2 (case 1 again), giving T_1(n) = \Theta(n^2).

With respect to a TCP connection between a client and a server, which one of the following statements is true?

D. Answer: (D) • (A) False: TCP uses a three-way handshake (SYN, SYN-ACK, ACK). • (B) False: either end may send the first FIN. • (C) False: TCP is full-duplex. • (D) True: simultaneous close is a defined case, in which both sides send FIN, pass through CLOSING, then TIME_WAIT.

Which of the following statements is/are true with respect to the interaction of a web browser with a web server using HTTP 1.1?

A, C, D. Answer: A, C, D • (A) True: HTTP/1.1 uses persistent connections by default. • (B) False: a TCP connection has exactly two endpoints, so objects on another server need another connection. • (C) True: pipelining lets the browser send the next request before the previous response finishes. • (D) True: a persistent connection is not tied to one page and can carry several pages from the same server.

Let n > 1. Consider an n \times n matrix M with its elements from \mathbb{R}. Let the vector (0, 1, 0, 0, \ldots, 0) \in \mathbb{R}^n be in the null space of M. Which of the following options is/are always correct?

B, D. Answer: B, D Me_2 = 0 with e_2 \ne 0 means the second column of M is all zeros. • (B) True: a nonzero null vector means M is singular, so \det M = 0. This also makes (A) false. • (C) Not always: the remaining columns can be independent, giving rank n-1. • (D) True: e_2 and 2e_2 are both nonzero and both lie in the null space.

Consider the following Boolean expression of a function F : F(P,Q) = (\overline{P} + Q) \oplus (\overline{P}Q) Which of the following expressions is/are equivalent to F ?

A, C. Answer: (A) and (C) Boolean-algebra (theorem) method Let A=\overline P+Q and B=\overline P\,Q. The product term \overline P\,Q is contained in \overline P+Q, so B\subseteq A and therefore A\oplus B=A\cdot\overline B. F=(\overline P+Q)\cdot\overline{\overline P\,Q}=(\overline P+Q)(P+\overline Q) by De Morgan \big(\overline{\overline P\,Q}=P+\overline Q\big). Expanding: F=\underbrace{\overline P\,P}_{0}+\overline P\,\overline Q+Q\,P+\underbrace{Q\,\overline Q}_{0}=PQ+\overline P\,\overline Q=\over

Consider the 8-bit signed integers X, Y and Z represented using the sign-magnitude form. The binary representations of X and Y are as follows: X: 10110100 Y: 01001100 Which of the following operations to compute Z result(s) in an arithmetic overflow?

B, C. Answer: B, C 8-bit sign-magnitude covers -127 \ldots +127. X: sign 1, magnitude 0110100_2 = 52, so X = -52. Y = 1001100_2 = +76. • (A) X + Y = 24: fits. • (B) X - Y = -128: overflow, because −128 has no sign-magnitude form in 8 bits. • (C) -X + Y = 128: overflow. • (D) -X - Y = -24: fits.

Let n be an odd number greater than 100. Consider a binary minheap with n elements stored in an array P whose index starts from 1. Which of the following indices of P do/does NOT correspond to any leaf node of the minheap?

B, C. Answer: B, C In a 1-indexed heap, node i has a child if 2i \le n. So the internal nodes are 1 \ldots \lfloor n/2 \rfloor and the leaves are \lfloor n/2\rfloor + 1 \ldots n. For odd n, \lfloor n/2 \rfloor = \tfrac{n-1}{2}, so the leaves start at \tfrac{n+1}{2}. • \tfrac{n+1}{2} and n are leaves. • \tfrac{n-1}{2} and \tfrac{n-3}{2} are internal (not leaves). Example: n = 101 has leaves 51…101, while 50 and 49 are internal.

Consider the following grammar where S is the start symbol, and a and b are terminal symbols. S \to aSbS \mid bS \mid \epsilon Which of the following statements is/are true?

A, B, C. Answer: A, B, C "abb" has two parse trees. In S \to a\,S_1\,b\,S_2, the extra b can come from either S_1 or S_2: Two distinct trees make the grammar ambiguous, so (A) and (B) are true. (C) "abab": the first symbol forces S \to aS_1bS_2, so S_1\,b\,S_2 must give "bab". Either S_1 = \epsilon, S_2 = ab (possible), or S_1 = ba (impossible, because every a needs a later matching b). There is only one tree, so only one rightmost derivation. True. (D) False: the language is context-free, and every CFL

Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equivalent to M?

B, D. Answer: B, D Subset construction gives at most 2^6 = 64 DFA states, and the minimal DFA can be no larger. So 65 and 128 are impossible. 1 is possible (for example \Sigma^* or \emptyset), and so is 32, since anything from 1 to 64 can occur.

Consider the following C statements: char *str1 = "Hello; /* Statement S1 */ char *str2 = "Hello;"; /* Statement S2 */ int *str3 = "Hello"; /* Statement S3 */ Which of the following options is/are correct?

C. Answer: C • S1: the string literal is never closed, so the lexer cannot form a valid token. That is a lexical error. • S2: "Hello;" is a valid string, so there is no error. • S3: the tokens and syntax are fine, but a char* is assigned to an int*. That type mismatch is caught during type checking, so it is a semantic error.

Which of the following statements is/are true?

C. Answer: C • (A) False: LL(1) is predictive and picks the production from one lookahead symbol, so it never backtracks. • (B) False: left recursion makes a grammar not LL(1). • (C) True: two alternatives with a common prefix share FIRST symbols and cause a table conflict, so the grammar must be left-factored. • (D) False: bottom-up SLR parsers handle grammars LL(1) cannot, such as left-recursive expression grammars.

With respect to deadlocks in an operating system, which of the following statements is/are FALSE?

A, C. Answer: A, C (the question asks for FALSE statements) • (A) FALSE: the Banker's algorithm is deadlock avoidance, not prevention. • (B) True: breaking hold-and-wait is a prevention technique. • (C) FALSE: an assignment edge points resource → process. A request edge points process → resource. • (D) True: a safe sequence exists, by definition.

Let P, Q, R and S be the attributes of a relation in a relational schema. Let X \to Y indicate functional dependency in the context of a relational database, where X, Y \subseteq \{P, Q, R, S\}. Which of the following options is/are always true?

C, D. Answer: C, D • (A) False: PQ \to R already follows from P \to R and says nothing about Q alone. • (B) False: a composite determinant does not have to split. Example: (roll, subject) → marks. • (C) True: augment P \to R to PQ \to RQ, and Q \to S to PQ \to PS, then take the union to get PQ \to RS. • (D) True: by augmentation, adding attributes to the left side keeps the dependency.

In the context of relational database normalization, which of the following statements is/are true?

A, B, C. Answer: A, B, C • (A) True: the 3NF synthesis algorithm always gives a lossless, dependency-preserving decomposition. • (B) True: with atomic attributes nothing needs to be split, so all FDs are kept. • (C) True: the classic example is R(A,B,C) with AB \to C,\ C \to B. BCNF must split on C \to B, which loses AB \to C. • (D) False: every 3NF decomposition is also in 2NF, and (A) says one always exists.

Consider the function f: \mathbb{R} \to \mathbb{R} defined as follows: f(x) = \begin{cases} c_1 e^{x} - c_2 \log_e\!\left(\dfrac{1}{x}\right), & \text{if } x > 0 \\ 3, & \text{otherwise} \end{cases} where c_1, c_2 \in \mathbb{R}. If f is continuous at x = 0, then c_1 + c_2 = _________. (answer in integer)

3. Answer: 3 -c_2 \ln(1/x) = c_2 \ln x, and as x \to 0^+, \ln x \to -\infty. For the right-hand limit to be finite, c_2 = 0. Then \lim_{x\to0^+} c_1 e^x = c_1 must equal f(0) = 3, so c_1 = 3. c_1 + c_2 = 3 + 0 = \mathbf{3}.

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is _________. (answer in integer)

11. Answer: 11 In a full binary tree (every node has 0 or 2 children), n = 2i + 1, so i = (23-1)/2 = 11 internal nodes. The height is greatest when the tree is a "caterpillar": each internal node has one leaf child and one internal child. Each internal node then adds one level, so the height is 11.

Consider the following program in C: #include void func(int i, int j) { if(i < j) { int i = 0; while (i < 10) { j += 2; i++; } } printf("%d", i); } int main() { int i = 9, j = 10; func(i, j); return 0; } The output of the program is _________. (answer in integer) Note: Assume that the program compiles and runs successfully.

9. Answer: 9 Inside the if block, int i = 0; declares a new i that shadows the parameter. The loop changes only that inner i (and j). The inner i goes out of scope when the block ends, so printf sees the parameter i = 9.

Consider a system consisting of k instances of a resource R, being shared by 5 processes. Assume that each process requires a maximum of two instances of resource R and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only after acquiring the first instance. The minimum value of k for the system to be deadlock-free is ________. (answer in integer)

6. Answer: 6 Worst case: every process holds one instance and waits for its second. With k = 5, all 5 instances are held and everyone waits, which is a deadlock. One more instance breaks this: k = 5(2-1) + 1 = \mathbf{6}. Some process can then finish and release its instances.

Consider the real valued variables X, Y and Z represented using the IEEE 754 single-precision floating-point format. The binary representations of X and Y in hexadecimal notation are as follows: X: 35C00000 Y: 34A00000 Let Z = X + Y. Which one of the following is the binary representation of Z, in hexadecimal notation?

C. Answer: (C) 35E80000 Both X and Y are positive (sign bit =0) single-precision numbers; bias =127, so the true exponent is e-127. hex | exponent field | mantissa | value -------------+-----------------+----------+---------------- X 35C00000 | 0110 1011 = 107 | 1000... | 1.1b x 2^-20 Y 34A00000 | 0110 1001 = 105 | 0100... | 1.01b x 2^-20 Decoding each number: X = 1.1_2 \times 2^{107-127} = 1.1_2 \times 2^{-20} = 1.5 \times 2^{-20} Y = 1.01_2 \times 2^{105-127} = 1.01_2 \times 2^{-22} = 0.0101_2 \t

Consider a 2-bit saturating up/down counter that performs the saturating up count when the input P is 0, and the saturating down count when P is 1. The Next State table of the counter is as shown. The counter is built as a synchronous sequential circuit using D flip-flops. Next State table (present state Q_1Q_0 → next state Q_1^{+}Q_0^{+}): P | Q1 Q0 | Q1+ Q0+ ---+-------+-------- 0 | 0 0 | 0 1 0 | 0 1 | 1 0 0 | 1 0 | 1 1 0 | 1 1 | 1 1 1 | 0 0 | 0 0 1 | 0 1 | 0 0 1 | 1 0 | 0 1 1 | 1 1 | 1 0 Whic

B. Answer: (B) For a D flip-flop, D = Q^+. Plot each next-state column on a 3-variable K-map, with minterm index = P\,Q_1\,Q_0. D_1 = Q_1^+ = 1 at minterms 1, 2, 3, 7. D_0 = Q_0^+ = 1 at minterms 0, 2, 3, 6. D_1 = \overline{P}Q_1 + \overline{P}Q_0 + Q_1Q_0 and D_0 = \overline{P}\,\overline{Q_0} + \overline{P}Q_1 + Q_1\overline{Q_0}. This matches (B) term for term. Shortcut: at state 00 with P=0 the counter must go to 01, so D_0(P{=}0, 00) = 1. Only (B) has a \overline{P}\,\overline{Q_0} term that g

The size of the physical address space of a processor is 2^{32} bytes. The capacity of a cache memory unit is 2^{23} bytes. The cache block size is 128 bytes. The cache memory unit can be built as a direct mapped cache or as a K-way set-associative cache, where K = 2^L and L \in \{1, 2, 3\}. Let the length of the TAG field be M bits for the direct mapped cache, and N bits for the set-associative cache. Which one of the following options is true?

A. Answer: (A) N = M + L • Offset: 128 = 2^7, so 7 bits. • Direct mapped: 2^{23}/2^7 = 2^{16} lines, so a 16-bit index and M = 32 - 16 - 7 = 9. • K-way: 2^{16}/2^L sets, so the index is 16 - L bits and N = 32 - (16 - L) - 7 = 9 + L. Every doubling of associativity moves one bit from the index to the tag.

Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head. struct node{ int elt; struct node *next; }; int getListSize (struct node *head) { if( E1 ) return 1; return E2; } Which one of the following options gives the correct replacements for the expressions E1 and E2?

B. Answer: (B) The base case returns 1, so it must fire at the last node, where head->next == NULL. Otherwise, count this node and recurse on the rest. • (A), (D): recursing on head itself never ends. • (C): returns 1 for NULL, which counts one node too many (a 3-node list gives 4).

Let P be the set of all integers from 1 to 15. Consider any order of insertion of the elements of P into a binary search tree that creates a complete binary tree. Which one of the following elements can NEVER be the third element that is inserted?

D. Answer: (D) 5 Fifteen keys in a complete BST have a fixed shape: the root is 8, level 1 is {4, 12}, and level 2 is {2, 6, 10, 14}. A node can be inserted only after its parent. So 8 goes first, then 4 or 12 second, and the third is the other of 4/12 or a child of the second (2, 6, 10 or 14). 5 is on level 3 and needs 8, 4 and 6 before it. It can never be third.

Let G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path. Let s \in V be a vertex in G. For every u \in V and for every k \ge 0, let d_k(u) denote the weight of a shortest path (in terms of weight) from s to u of length at most k. If there is no path from s to u of length at most k, then d_k(u) = \infty. Consider the statements: S1: For every k \ge 0 a

A. Answer: (A) Only S1 is true S1 is true: every path of length \le k also has length \le k+1, so allowing more edges can only keep or lower the minimum. (This is the Bellman-Ford invariant.) S2 is false. Counterexample: edges s–a (1), a–b (1), b–u (1), u–v (1), and s–v (10). The shortest path to v is s-a-b-u-v with weight 4, so edge (u, v) lies on it. But with k = 1: d_1(u) = \infty and d_1(v) = 10, so d_1(u) > d_1(v).

Consider the control flow graph shown in the figure. Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B4 and B5? Note: All the variables are integers.

Consider a relational database schema with two relations R(P, Q) and S(X, Y). Let E = \{\langle u\rangle \mid \exists v\, \exists w\ \langle u, v\rangle \in R \wedge \langle v, w\rangle \in S\} be a tuple relational calculus expression. Which one of the following relational algebraic expressions is equivalent to E?

B. Answer: (B) Map the variables: in \langle u, v\rangle \in R, u is R.P and v is R.Q. In \langle v, w\rangle \in S, the same v is S.X. So the join condition is R.Q = S.X, and the output is u = R.P: \Pi_P(S \bowtie_{S.X=R.Q} R). Join order does not matter.

A TCP sender successfully establishes a connection with a TCP receiver and starts the transmission of segments. The TCP congestion control mechanism’s slow-start threshold is set to 10000 segments. Assume that the round-trip time is fixed at 1 millisecond. Assume that the sender always has data to send, the segments are numbered from 1, and no segment is lost. Let t denote the time (in milliseconds) at which the transmission of segment number 2000 starts. Which one of the following options is co

B. Answer: (B) 10 \le t < 11 In slow start (the threshold of 10000 is never reached), cwnd doubles every RTT. The round starting at t = k ms sends 2^k segments. Round starts at t (ms) | cwnd | Segments sent -----------------------+------+-------------- 0 | 1 | 1 1 | 2 | 2–3 2 | 4 | 4–7 … | … | … 9 | 512 | 512–1023 10 | 1024 | 1024–2047 Segment 2000 lies in the round that starts at 10 ms, so 10 \le t < 11.

Consider the implementation of sliding window protocol over a lossless link, with a window size of W frames, where each frame is of size 1000 bits (including header). The bandwidth of the link is 100 kbps (1k = 10^3) and the one-way propagation delay is 100 milliseconds. Assume that processing times at the sender and receiver are zero and the transmission time of acknowledgements is also zero. Which one of the following options gives the minimum size of W (in number of frames) required to achiev

B. Answer: (B) 21 T_t = \dfrac{1000}{10^5} = 10 ms and T_p = 100 ms. The first ACK comes back after T_t + 2T_p = 210 ms. To keep the link busy all that time, the sender needs W \ge \dfrac{T_t + 2T_p}{T_t} = \dfrac{210}{10} = 21 frames. The trap is answer 20 (2T_p/T_t), which forgets the first frame's own transmission time.

Let f: \mathbb{R} \to \mathbb{R} be defined as follows: f(x) = \left(\frac{|x|}{2} - x\right)\left(x - \frac{|x|}{2}\right) Which of the following statements is/are true?

A, C, D. Answer: A, C, D Split at 0: • x \ge 0: \left(-\tfrac{x}{2}\right)\left(\tfrac{x}{2}\right) = -\tfrac{x^2}{4}, so f'(x) = -\tfrac{x}{2}. • x < 0: \left(-\tfrac{3x}{2}\right)\left(\tfrac{3x}{2}\right) = -\tfrac{9x^2}{4}, so f'(x) = -\tfrac{9x}{2}. • (A) True: f(0) = 0 \ge f(x) for all x. • (B) False: f decreases on both sides of 0 forever, so there is no local minimum. • (C) True: f'(0^-) = f'(0^+) = 0, so f' is continuous. • (D) True: f''(0^-) = -\tfrac92 \ne f''(0^+) = -\tfrac12, so f' is not di

Let G(V, E) be a simple, undirected graph. A vertex cover of G is a subset V' \subseteq V such that for every (u, v) \in E, u \in V' or v \in V'. Let the size of the smallest vertex cover in G be k. Let S be any vertex cover of size k. For a vertex v \in V, which of the following constraints will always ensure that v \in S?

A. Answer: A (A) True. If v \notin S, every edge at v must be covered by its other end, so all \ge k+1 neighbours are in S. Then |S| \ge k+1, a contradiction. (B) False. Path 1–2–3–4–5: k = 2 with S = \{2, 4\}. Vertex 1 lies on the path 1-2-3-4 of length 3 = k+1, yet 1 \notin S. (C) False. Triangle {1, 2, 3}: k = 2 with S = \{1, 2\}. Vertex 3 lies on a cycle of length 3 = k+1, yet 3 \notin S. (D) False. In the same triangle, {1, 3} is a clique of size k = 2 containing 3, and 3 \notin S. A clique ne

Consider a Boolean function F with the following minterm expression: F(P, Q, R, S) = \sum m(1, 2, 3, 4, 5, 7, 10, 12, 13, 14) Which of the following options is/are the minimal sum-of-products expression(s) of F ?

B, D. Answer: B, D Essential prime implicants: \overline{P}S (covers 1, 3, 5, 7) and Q\overline{R} (covers 4, 5, 12, 13). That leaves 2, 10, 14 to cover. The prime implicants for the remaining cells are \overline{P}\,\overline{Q}R (2, 3), \overline{Q}R\overline{S} (2, 10), PR\overline{S} (10, 14) and PQ\overline{S} (12, 14). Two of them must cover 2, 10 and 14: • (A) \overline{P}\,\overline{Q}R + \overline{Q}R\overline{S}: 14 is not covered. ✗ • (B) \overline{P}\,\overline{Q}R + PR\overline{S}: covers

Let G(V, E) be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of G is/are true?

A, D. Answer: A, D (with unique weights the MST is unique) • (A) True: this is the cycle property. The heaviest edge of any cycle can be swapped out for a lighter one. • (B) False: in triangle u-v-w with weights 5, 6, 7, add a path u-x-v with weights 1, 1. Edge u-v (5) is the lightest in its triangle but is not in the MST. • (C) False: for a leaf vertex, its only edge is both its heaviest and its lightest, and it must be in the MST. • (D) True: this is the cut property applied to the cut \{v\} vs V -

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph G(V, E) as input, where d[v] and f[v] are the discovery time and finishing time, respectively, of the vertex v \in V. DFS(G): Explore(G, v, t): unmark all v ∈ V mark v t ← 0 t ← t + 1 for each v ∈ V d[v] ← t if v is unmarked for each (v, w) ∈ E t ← Explore(G, v, t) if w is unmarked end if t ← Explore(G, w, t) end for end if end for t ← t + 1 f[v] ← t return t Suppose that the input directed grap

B, D. Answer: B, D Key fact: in a DAG, every edge (u, v) satisfies f[v] < f[u]. This is why reverse finishing order is a topological sort. • (A) Tree or forward edge: possible. • (B) u is nested inside v, so (u, v) is a back edge, which means a cycle. Never. • (C) Cross edge to an already finished v: possible. • (D) The intervals partly overlap, which the parenthesis theorem rules out for any DFS. Never.

Let L_1 and L_2 be two languages over a finite alphabet, such that L_1 \cap L_2 and L_2 are regular languages. Which of the following statements is/are always true?

C. Answer: C Take L_2 = \emptyset. Then L_1 \cap L_2 = \emptyset is regular for any L_1, even an undecidable one. • (A) and (D) fail for such an L_1. • (B) L_1 \cup \emptyset = L_1, which also fails. • (C) is always true: every regular language is context-free.

GATE CS 2026 Set 1 — All 65 Questions with Solutions

Computer Science (CS). Every question from this paper with the official answer key and a step-by-step solution. 100 marks total.

Attempt in GATE exam mode →All papers

Question 1General Aptitudemcq1 mark
The antonym of the word protagonist is ________.
- A.
  agnostic
- B.
  antagonist
  ✓
- C.
  arsonist
- D.
  anarchist
Answer: B
Solution
Answer: (B) antagonist A protagonist is the leading character or a champion of a cause. Its opposite is the antagonist, the one who opposes the protagonist. The other words are unrelated: an agnostic doubts that God's existence can be known, an arsonist sets fires on purpose, and an anarchist rejects all government.
Question 2General Aptitudemcq1 mark
The figure shows two 4-tile patterns. Either one or both of the patterns can be used any number of times and in any orientation to construct a new pattern. Which one of the options below cannot be constructed by using only these two 4-tile patterns assuming there are no overlaps among them?
- A.
- B.
- C.✓
- D.
Answer: C
Solution
Answer: (C) Quick test: every piece has 4 tiles, so any shape built from them must have a tile count that is a multiple of 4. • (A) 2 × 4 = 8 tiles: two 2 × 2 squares, or two horizontal bars. • (B) 3 × 4 = 12 tiles: three horizontal bars. • (C) 3 × 5 = 15 tiles: 15 is not a multiple of 4, so it is impossible. • (D) 4 × 5 = 20 tiles: five vertical bars.
Question 3General Aptitudemcq1 mark
Consider a knock-out women’s badminton singles tournament where there are no ties. The loser in each game is eliminated from the tournament. Every player plays until she is defeated or remains the last undefeated player. The last undefeated player is declared the winner of the tournament. If there are 64 players in the beginning of the tournament, how many games should be played in total to declare the winner of the tournament?
- A.
  127
- B.
  64
- C.
  63
  ✓
- D.
  32
Answer: C
Solution
Answer: (C) 63 Each game eliminates exactly one player. To go from 64 players to 1 winner, 63 players must be eliminated, so 63 games are needed. Round by round: 32 + 16 + 8 + 4 + 2 + 1 = 63.
Question 4General Aptitudemcq1 mark
A student needs to enroll for a minimum of 60 credits. A student cannot enroll for more than 70 credits. The credits are divided amongst project and three distinct sets of courses namely, core courses, specialization courses, and elective courses. It is compulsory for a student to enroll for exactly 15 credits of core courses and exactly 20 credits of project. In addition, a student has to enroll for a minimum of 10 credits of specialization courses. The maximum credits of elective courses that a student can enroll for is ______
- A.
  10
- B.
  15
- C.
  20
- D.
  25
  ✓
Answer: D
Solution
Answer: (D) 25 To maximise electives, take the overall maximum and the minimum everywhere else:
$Electives = 70 - 15 (core) - 20 (project) - 10 (specialisation) = 25$
Question 5General Aptitudemcq1 mark
‘When the teacher is in the room, all students stand silently.’ If the above statement is true, which one of the following statements is not necessarily true?
- A.
  If any student is not standing silently, then the teacher is not in the room.
- B.
  When the teacher is in the room, all students are silent.
- C.
  If all students are standing, then the teacher is in the room.
  ✓
- D.
  When the teacher is in the room, all students are standing.
Answer: C
Solution
Answer: (C) Write the statement as $T \Rightarrow S$ , where $T$ = "teacher in room" and $S$ = "all students stand silently". • (A) is the contrapositive $\neg S \Rightarrow \neg T$ , so it is always true. • (B) and (D) are weaker parts of $S$ ("silent", "standing"), so they follow. • (C) says "standing $\Rightarrow T$ ". That is a form of the converse, which does not follow. Students may stand even when the teacher is away.
Question 6General Aptitudemcq2 marks
Combinatorics deals with problems involving counting. For example, “How many distinct arrangements of N distinct objects in M spaces on a circle are possible?” is a typical problem in combinatorics. This kind of counting is sometimes used in the modeling of several physical phenomena. Often, in such models, the different combinatorial possibilities are assigned probability values. Assigning probabilities enables the computation of the average values of physical quantities. Consider the following statements: P: Combinatorics is always invoked in the modeling of physical phenomena. Q: Modeling some physical phenomena involves assigning probabilities to combinatorial possibilities in order to compute average values of physical quantities. Based on the passage above, what can be inferred about statements P and Q?
- A.
  P is False and Q is False
- B.
  P is False and Q is True
  ✓
- C.
  P is True and Q is False
- D.
  P is True and Q is True
Answer: B
Solution
Answer: (B) P is false. The passage says counting is sometimes used in modelling. "Always" overstates it. Q is true. It restates the last two sentences: in such models, possibilities are assigned probabilities so that average values can be computed.
Question 7General Aptitudemcq2 marks
In Panel I of the figure below, the front view and top view of a structure are shown. Which one of the 3D structures shown in Panel II possesses the views shown in Panel I?
- A.
  (i)
- B.
  (ii)
- C.
  (iii)
- D.
  (iv)
  ✓
Answer: D
Solution
Answer: (D) (iv) (official key) Method: check each structure against one view at a time and drop it as soon as one feature disagrees. • Front view: only one column reaches the top level, and it sits at the far left. Below it, the right-hand part is one step lower, with a separate small cube at the bottom right. • Top view: a strip runs along the left, and the right part forms an L-shape with the front-right corner cut away. • (i) The right part is one continuous slab, so the front view would have no separate bottom-right square. Rejected. • (ii) The right part is split into extra cubes, which adds lines the given top view does not have. Rejected. • (iii) A second raised block stands at the back, so the front view would show two top-level parts. Rejected. • (iv) A single tall column at the back left and a stepped right part with a separate lower front cube give both views exactly.
Question 8General Aptitudemcq2 marks
For positive real numbers $S$ and $K$ , the function $H_{K} (S)$ is defined as: $H_{K} (S) = max (S - K, 0)$ . The max function is defined as:
$max (a, b) = {a, b, when a > b when a \leq b$
The graph below shows the plot of a function $N (S)$ versus $S$ . $N (S)$ can be expressed as _____.
- A.
  $H_{10} (S) - H_{20} (S)$
  ✓
- B.
  $H_{10} (S) - 2 H_{20} (S)$
- C.
  $- H_{10} (S) + H_{20} (S)$
- D.
  $H_{15} (S) - H_{20} (S)$
Answer: A
Solution
Answer: (A) $H_{K} (S)$ is a "hinge": 0 up to $K$ , then a line of slope 1. Read the graph off as slopes: slope 0 before 10, slope +1 from 10 to 20, then slope 0 again. Switching the slope on at 10 gives $+ H_{10}$ , and switching it off at 20 gives $- H_{20}$ . Check: $N (25) = 15 - 5 = 10$ ✓, $N (15) = 5 - 0 = 5$ ✓, $N (5) = 0$ ✓. (B) would make the graph slope down after 20, (C) would go negative between 10 and 20, and (D) would start rising at 15.
Question 9General Aptitudemcq2 marks
In the 2020 summer Olympics’ Javelin throw finals, Neeraj Chopra exhibited a spectacular performance to win the gold medal. The silver medal was won by Jakub Vadlejch and the bronze medal was won by Vitezlav Vesely. There were six rounds of throws with each athlete having one throw per round. The best of all the throws of each athlete is considered for the medal. Following were the observations about the throws: • The first and second rounds were dominated by Neeraj Chopra with a gold medal performance in his second throw, while the other two athletes did not have any medal winning throws in these rounds. • The throws in the last round by both Jakub Vadlejch and Vitezlav Vesely were fouls and were not considered for scoring. • After four rounds, Vitezlav Vesely was in the second position and could not improve upon his best throw in the succeeding rounds. • In the fourth round, the throw by Jakub Vadlejch was the best in that round. In which round did Vitezlav Vesely have his best throw?
- A.
  Third
  ✓
- B.
  Fourth
- C.
  Fifth
- D.
  Sixth
Answer: A
Solution
Answer: (A) Third • (i) His best throw was not in round 1 or 2. • (ii) Round 6 was a foul. • (iii) His best came within the first four rounds and was never improved, so it is in round 3 or 4. • Suppose it was round 4. By (iv), Jakub's round-4 throw beat it, so Jakub would be ahead of Vesely after four rounds. That contradicts (iii), which puts Vesely second. So the best throw was in round 3.

Question 10General Aptitudemcq2 marks

An unbiased six-faced dice whose faces are marked with numbers 1, 2, 3, 4, 5, and 6 is rolled twice in succession and the number on the top face is recorded each time. The probability that the number appearing in the second roll is an integer multiple of the number appearing in the first roll is __________

A.
$\frac{1}{6}$
B.
$\frac{5}{18}$
C.
$\frac{7}{18}$
✓
D.
$\frac{5}{6}$

Answer: C

Solution

Answer: (C) 7/18

First roll | Second roll is a multiple | Count
-----------+---------------------------+------
1          | 1,2,3,4,5,6               | 6
2          | 2,4,6                     | 3
3          | 3,6                       | 2
4          | 4                         | 1
5          | 5                         | 1
6          | 6                         | 1

Favourable outcomes = 14 out of 36, so

P = \frac{14}{36} = \frac{7}{18}

Question 11Engineering Mathematicsmcq1 mark
An urn contains one red ball and one blue ball. At each step, a ball is picked uniformly at random from the urn, and this ball together with another ball of the same color is put back in the urn. The probability that there are equal number of red and blue balls after two steps is
- A.
  1/4
- B.
  1/3
  ✓
- C.
  1/2
- D.
  2/3
Answer: B
Solution
Answer: (B) 1/3 Start with (R, B) = (1, 1). After two steps there are 4 balls, so "equal" means (2, 2). That needs one red pick and one blue pick. • Red then blue: $\frac{1}{2} \times \frac{1}{3} = \frac{1}{6}$ . After the red pick the urn is (2, 1), so blue has probability 1/3. • Blue then red: $\frac{1}{2} \times \frac{1}{3} = \frac{1}{6}$ , by symmetry. Total $= \frac{1}{6} + \frac{1}{6} = \frac{1}{3}$ . (This is Pólya's urn: after $n$ steps, every red count from 1 to $n + 1$ is equally likely, so the chance is $\frac{1}{3}$ .)
Question 12Discrete Mathematicsmcq1 mark
Consider $4 \times 4$ matrices with their elements from ${0, 1}$ . The number of such matrices with even number of 1s in every row and every column is
- A.
  512
  ✓
- B.
  1025
- C.
  1023
- D.
  255
Answer: A
Solution
Answer: (A) 512 Fill the top-left $3 \times 3$ block freely: $2^{9}$ ways. Then: • the last entry of each of the first three rows is forced, to make that row's parity even; • the last entry of each of the first three columns is forced the same way; • the bottom-right corner is forced too, and both its row and its column agree on it, because the total number of 1s in the first three rows equals the total in the first three columns (mod 2). Count $= 2^{(n - 1)^{2}} = 2^{9} = 512$ .
Question 13Engineering Mathematicsmcq1 mark
For $n > 1$ , the maximum multiplicity of any eigenvalue of an $n \times n$ matrix with elements from $R$ is
- A.
  $n$
  ✓
- B.
  $n - 1$
- C.
  $1$
- D.
  $n + 1$
Answer: A
Solution
Answer: (A) $n$ The characteristic polynomial has degree $n$ , so no eigenvalue can repeat more than $n$ times. The bound is reached by the identity matrix $I_{n}$ , whose eigenvalue 1 has multiplicity $n$ .
Question 14Computer Organization & Architecturemcq1 mark
Match each addressing mode in List I with a data element or an element of a data structure (in a high-level language) in List II:
```
List I                           | List II
---------------------------------+-----------------------
P. Immediate                     | 1. Element of an array
Q. Indirect                      | 2. Pointer
R. Base with index               | 3. Element of a record
S. Base with offset/displacement | 4. Constant
```
- A.
  P–4, Q–3, R–1, S–2
- B.
  P–4, Q–2, R–1, S–3
  ✓
- C.
  P–1, Q–4, R–3, S–2
- D.
  P–2, Q–3, R–1, S–4
Answer: B
Solution
Answer: (B) P–4, Q–2, R–1, S–3 • Immediate: the operand is in the instruction itself, so it is a constant. • Indirect: the instruction holds the address of the address, which is how a pointer is dereferenced. • Base + index: base address of the array plus a variable index register gives a[i]. • Base + fixed displacement: the start of a struct plus a fixed field offset gives r.field.
Question 15Computer Organization & Architecturemcq1 mark
Consider a processor P whose instruction set architecture is the load-store architecture. The instruction format is such that the first operand of any instruction is the destination operand. Which one of the following sequences of instructions corresponds to the high-level language statement Z = X + Y ? Note: X, Y, and Z are memory operands. R0, R1, and R2 are registers.
- A.
  ADD Z, X, Y
- B.
  LOAD R0, X ADD Z, R0, Y
- C.
  ADD R0, X, Y STORE Z, R0
- D.
  LOAD R0, X LOAD R1, Y ADD R2, R0, R1 STORE Z, R2
  ✓
Answer: D
Solution
Answer: (D) In a load-store (RISC-style) ISA, only LOAD and STORE touch memory, and every ALU instruction works on registers only. (A), (B) and (C) each have an ADD with a memory operand, so they are illegal. (D) loads both operands, adds them in registers, then stores the result.
Question 16Computer Organization & Architecturemcq1 mark
Which one of the following dependencies among the register operands of different instructions can cause a data hazard in a pipelined processor?
- A.
  Read-after-read
- B.
  Read-after-write
  ✓
- C.
  Write-after-read
- D.
  Write-after-write
Answer: B
Solution
Answer: (B) Read-after-write RAW is a true data dependence: a later instruction needs a value that an earlier one has not yet written back. In an in-order pipeline this causes stalls or needs forwarding. RAR is never a hazard. WAR and WAW are name dependences, and they become hazards only in out-of-order or multi-path pipelines. The official key accepts only RAW.
Question 17Algorithmsmcq1 mark
Consider the following recurrence relations: For all $n > 1$ ,
$T_{1} (n) = 4 T_{1} (\frac{n}{2}) + T_{2} (n) T_{2} (n) = 5 T_{2} (\frac{n}{4}) + Θ (lo g_{2} n)$
Assume that for all $n \leq 1$ , $T_{1} (n) = 1$ and $T_{2} (n) = 1$ . Which one of the following options is correct?
- A.
  $T_{1} (n) = Θ (n^{2})$
  ✓
- B.
  $T_{1} (n) = Θ (n^{2} lo g_{2} n)$
- C.
  $T_{1} (n) = Θ (n^{l o g_{4} 5})$
- D.
  $T_{1} (n) = Θ (n^{l o g_{4} 5} lo g_{2} n)$
Answer: A
Solution
Answer: (A) $Θ (n^{2})$ Step 1, solve $T_{2}$ : $a = 5, b = 4$ , so $n^{l o g_{4} 5} \approx n^{1.16}$ . This dominates $lo g n$ polynomially (Master theorem case 1), giving $T_{2} (n) = Θ (n^{l o g_{4} 5})$ . Step 2, solve $T_{1}$ : $a = 4, b = 2$ , so $n^{l o g_{2} 4} = n^{2}$ . The extra term $n^{1.16}$ is polynomially smaller than $n^{2}$ (case 1 again), giving $T_{1} (n) = Θ (n^{2})$ .
Question 18Computer Networksmcq1 mark
With respect to a TCP connection between a client and a server, which one of the following statements is true?
- A.
  The client and server use a two-way handshake mechanism before the start of data transmission
- B.
  The server cannot initiate closing of the connection before the client initiates closing of the connection
- C.
  The TCP connection is half-duplex
- D.
  The client and server can initiate closing of the connection at the same time
  ✓
Answer: D
Solution
Answer: (D) • (A) False: TCP uses a three-way handshake (SYN, SYN-ACK, ACK). • (B) False: either end may send the first FIN. • (C) False: TCP is full-duplex. • (D) True: simultaneous close is a defined case, in which both sides send FIN, pass through CLOSING, then TIME_WAIT.
Question 19Computer Networksmsq1 mark
Which of the following statements is/are true with respect to the interaction of a web browser with a web server using HTTP 1.1?
- A.
  HTTP 1.1 facilitates downloading multiple objects of the same webpage over the same TCP connection, if the objects are stored in the same server
  ✓
- B.
  HTTP 1.1 facilitates downloading multiple objects of the same webpage over the same TCP connection, even if they are stored in different servers
- C.
  HTTP 1.1 facilitates sending a request for downloading one object without waiting for a previously requested object to be downloaded completely
  ✓
- D.
  HTTP 1.1 facilitates downloading multiple webpages on the same server to be downloaded over a single TCP connection
  ✓
Answer: A, C, D
Solution
Answer: A, C, D • (A) True: HTTP/1.1 uses persistent connections by default. • (B) False: a TCP connection has exactly two endpoints, so objects on another server need another connection. • (C) True: pipelining lets the browser send the next request before the previous response finishes. • (D) True: a persistent connection is not tied to one page and can carry several pages from the same server.
Question 20Engineering Mathematicsmsq1 mark
Let $n > 1$ . Consider an $n \times n$ matrix $M$ with its elements from $R$ . Let the vector $(0, 1, 0, 0, \dots, 0) \in R^{n}$ be in the null space of $M$ . Which of the following options is/are always correct?
- A.
  Determinant of $M$ is 1
- B.
  Determinant of $M$ is 0
  ✓
- C.
  Rank of $M$ is 1
- D.
  There are at least two non-zero vectors in the null space of $M$
  ✓
Answer: B, D
Solution
Answer: B, D $M e_{2} = 0$ with $e_{2} \neq = 0$ means the second column of $M$ is all zeros. • (B) True: a nonzero null vector means $M$ is singular, so $det M = 0$ . This also makes (A) false. • (C) Not always: the remaining columns can be independent, giving rank $n - 1$ . • (D) True: $e_{2}$ and $2 e_{2}$ are both nonzero and both lie in the null space.
Question 21Digital Logicmsq1 mark
Consider the following Boolean expression of a function F :
$F (P, Q) = (P + Q) \oplus (P Q)$
Which of the following expressions is/are equivalent to F ?
- A.
  $P \oplus Q$
  ✓
- B.
  $P \oplus Q$
- C.
  $P \oplus Q$
  ✓
- D.
  $P \oplus Q$
Answer: A, C
Solution
Answer: (A) and (C) Boolean-algebra (theorem) method Let $A = P + Q$ and $B = P Q$ . The product term $P Q$ is contained in $P + Q$ , so $B \subseteq A$ and therefore $A \oplus B = A \cdot B$ .
$F = (P + Q) \cdot P Q = (P + Q) (P + Q)$
by De Morgan $(P Q = P + Q)$ . Expanding:
$F = 0 P P + P Q + Q P + 0 Q Q = P Q + P Q = P \oplus Q .$
So $F$ is XNOR $= P \oplus Q$ → option (A). For (C): $P \oplus Q = P Q + P Q = P Q + P Q = F$ (complementing one input of an XOR complements its output, so $P \oplus Q = P \oplus Q$ ). Hence (C) is also equivalent. (B) $P \oplus Q = F$ — wrong. (D) $P \oplus Q = P \oplus Q = F$ — wrong. Truth-table verification (here $P^{'}$ means $P$ ):
```
P  Q  | P'+Q | P'Q | F
------+------+-----+---
0  0  |   1  |  0  | 1
0  1  |   1  |  1  | 0
1  0  |   0  |  0  | 0
1  1  |   1  |  0  | 1
```
$F = 1$ exactly when $P = Q$ , i.e. the XNOR of $P$ and $Q$ — confirming (A) and (C).
Question 22Digital Logicmsq1 mark
Consider the 8-bit signed integers $X$ , $Y$ and $Z$ represented using the sign-magnitude form. The binary representations of $X$ and $Y$ are as follows: X: 10110100 Y: 01001100 Which of the following operations to compute $Z$ result(s) in an arithmetic overflow?
- A.
  $Z = X + Y$
- B.
  $Z = X - Y$
  ✓
- C.
  $Z = - X + Y$
  ✓
- D.
  $Z = - X - Y$
Answer: B, C
Solution
Answer: B, C 8-bit sign-magnitude covers $- 127 \dots + 127$ . $X$ : sign 1, magnitude $011010 0_{2} = 52$ , so $X = - 52$ . $Y = 100110 0_{2} = + 76$ . • (A) $X + Y = 24$ : fits. • (B) $X - Y = - 128$ : overflow, because −128 has no sign-magnitude form in 8 bits. • (C) $- X + Y = 128$ : overflow. • (D) $- X - Y = - 24$ : fits.
Question 23Programming & Data Structuresmsq1 mark
Let $n$ be an odd number greater than 100. Consider a binary minheap with $n$ elements stored in an array $P$ whose index starts from 1. Which of the following indices of $P$ do/does NOT correspond to any leaf node of the minheap?
- A.
  $\frac{n + 1}{2}$
- B.
  $\frac{n - 1}{2}$
  ✓
- C.
  $\frac{n - 3}{2}$
  ✓
- D.
  $n$
Answer: B, C
Solution
Answer: B, C In a 1-indexed heap, node $i$ has a child if $2 i \leq n$ . So the internal nodes are $1 \dots ⌊ n /2 ⌋$ and the leaves are $⌊ n /2 ⌋ + 1 \dots n$ . For odd $n$ , $⌊ n /2 ⌋ = \frac{n - 1}{2}$ , so the leaves start at $\frac{n + 1}{2}$ . • $\frac{n + 1}{2}$ and $n$ are leaves. • $\frac{n - 1}{2}$ and $\frac{n - 3}{2}$ are internal (not leaves). Example: $n = 101$ has leaves 51…101, while 50 and 49 are internal.

Question 24Programming & Data Structuresmsq1 mark

Consider a hash table

P [0, 1, \dots, 10]

that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is

h (x) = (x + 7) mod 11

. Consider the following sequence of insertions performed on

P

: 1, 13, 22, 15, 11, 24 Which of the following positions in the hash table is/are empty after these insertions are performed?

A.
0
B.
10
C.
2
✓
D.
1

Answer: C

Solution

Answer: C (position 2 only)

Key | h(x) = (x+7) mod 11 | Probes               | Slot
----+---------------------+----------------------+-----
1   | 8                   | –                    | 8
13  | 9                   | –                    | 9
22  | 7                   | –                    | 7
15  | 0                   | –                    | 0
11  | 7                   | 7 ✗ → 8 ✗ → 9 ✗ → 10 | 10
24  | 9                   | 9 ✗ → 10 ✗ → 0 ✗ → 1 | 1

Among the options only 2 is empty. The trap is the wrap-around from 10 back to 0 when placing 24.

Question 25Theory of Computationmsq1 mark
Consider the following grammar where $S$ is the start symbol, and $a$ and $b$ are terminal symbols.
$S \to a S b S ∣ b S ∣ ϵ$
Which of the following statements is/are true?
- A.
  The grammar is ambiguous
  ✓
- B.
  The string $abb$ has two distinct derivations in this grammar
  ✓
- C.
  The string $abab$ has only one rightmost derivation
  ✓
- D.
  The language generated by the grammar is undecidable
Answer: A, B, C
Solution
Answer: A, B, C "abb" has two parse trees. In $S \to a S_{1} b S_{2}$ , the extra b can come from either $S_{1}$ or $S_{2}$ : Two distinct trees make the grammar ambiguous, so (A) and (B) are true. (C) "abab": the first symbol forces $S \to a S_{1} b S_{2}$ , so $S_{1} b S_{2}$ must give "bab". Either $S_{1} = ϵ, S_{2} = ab$ (possible), or $S_{1} = ba$ (impossible, because every a needs a later matching b). There is only one tree, so only one rightmost derivation. True. (D) False: the language is context-free, and every CFL is decidable.
Question 26Theory of Computationmsq1 mark
Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equivalent to $M$ ?
- A.
  32
- B.
  65
  ✓
- C.
  1
- D.
  128
  ✓
Answer: B, D
Solution
Answer: B, D Subset construction gives at most $2^{6} = 64$ DFA states, and the minimal DFA can be no larger. So 65 and 128 are impossible. 1 is possible (for example $Σ^{*}$ or $\emptyset$ ), and so is 32, since anything from 1 to 64 can occur.
Question 27Compiler Designmsq1 mark
Consider the following C statements:
```
char *str1 = "Hello;        /* Statement S1 */
char *str2 = "Hello;";      /* Statement S2 */
int  *str3 = "Hello";       /* Statement S3 */
```
Which of the following options is/are correct?
- A.
  S1 and S2 have syntactic errors
- B.
  S2 has a lexical error and S3 has a syntactic error
- C.
  S1 has a lexical error and S3 has a semantic error
  ✓
- D.
  S1 has a syntactic error and S3 has a semantic error
Answer: C
Solution
Answer: C • S1: the string literal is never closed, so the lexer cannot form a valid token. That is a lexical error. • S2: "Hello;" is a valid string, so there is no error. • S3: the tokens and syntax are fine, but a char* is assigned to an int*. That type mismatch is caught during type checking, so it is a semantic error.
Question 28Compiler Designmsq1 mark
Which of the following statements is/are true?
- A.
  LL(1) parser uses backtracking
- B.
  For a grammar to be LL(1), it must be left-recursive
- C.
  For a grammar to be LL(1), it must be left-factored
  ✓
- D.
  The LL(1) parsers are more powerful than the SLR parsers
Answer: C
Solution
Answer: C • (A) False: LL(1) is predictive and picks the production from one lookahead symbol, so it never backtracks. • (B) False: left recursion makes a grammar not LL(1). • (C) True: two alternatives with a common prefix share FIRST symbols and cause a table conflict, so the grammar must be left-factored. • (D) False: bottom-up SLR parsers handle grammars LL(1) cannot, such as left-recursive expression grammars.
Question 29Operating Systemsmsq1 mark
With respect to deadlocks in an operating system, which of the following statements is/are FALSE?
- A.
  Banker’s algorithm is used to prevent deadlocks
  ✓
- B.
  Deadlock formation can be prevented by ensuring that the hold and wait condition is not allowed
- C.
  An assignment edge in a resource allocation graph is marked from a process to a resource
  ✓
- D.
  A safe state guarantees that all processes can finish without formation of a deadlock
Answer: A, C
Solution
Answer: A, C (the question asks for FALSE statements) • (A) FALSE: the Banker's algorithm is deadlock avoidance, not prevention. • (B) True: breaking hold-and-wait is a prevention technique. • (C) FALSE: an assignment edge points resource → process. A request edge points process → resource. • (D) True: a safe sequence exists, by definition.
Question 30Databasesmsq1 mark
Let $P, Q, R$ and $S$ be the attributes of a relation in a relational schema. Let $X \to Y$ indicate functional dependency in the context of a relational database, where $X, Y \subseteq {P, Q, R, S}$ . Which of the following options is/are always true?
- A.
  If ( ${P, Q} \to {R}$ and ${P} \to {R}$ ), then ${Q} \to {R}$
- B.
  If ${P, Q} \to {R}$ , then ( ${P} \to {R}$ or ${Q} \to {R}$ )
- C.
  If ( ${P} \to {R}$ and ${Q} \to {S}$ ), then ${P, Q} \to {R, S}$
  ✓
- D.
  If ${P} \to {R}$ , then ${P, Q} \to {R}$
  ✓
Answer: C, D
Solution
Answer: C, D • (A) False: $P Q \to R$ already follows from $P \to R$ and says nothing about $Q$ alone. • (B) False: a composite determinant does not have to split. Example: (roll, subject) → marks. • (C) True: augment $P \to R$ to $P Q \to R Q$ , and $Q \to S$ to $P Q \to P S$ , then take the union to get $P Q \to R S$ . • (D) True: by augmentation, adding attributes to the left side keeps the dependency.
Question 31Databasesmsq1 mark
In the context of relational database normalization, which of the following statements is/are true?
- A.
  It is always possible to obtain a dependency-preserving 3NF decomposition of a relation
  ✓
- B.
  It is always possible to obtain a dependency-preserving 1NF decomposition of a relation
  ✓
- C.
  It is not always possible to obtain a dependency-preserving BCNF decomposition of a relation
  ✓
- D.
  It is not always possible to obtain a dependency-preserving 2NF decomposition of a relation
Answer: A, B, C
Solution
Answer: A, B, C • (A) True: the 3NF synthesis algorithm always gives a lossless, dependency-preserving decomposition. • (B) True: with atomic attributes nothing needs to be split, so all FDs are kept. • (C) True: the classic example is $R (A, B, C)$ with $A B \to C, C \to B$ . BCNF must split on $C \to B$ , which loses $A B \to C$ . • (D) False: every 3NF decomposition is also in 2NF, and (A) says one always exists.
Question 32Engineering Mathematicsnat1 mark
Consider the function $f : R \to R$ defined as follows:
$f (x) = ⎩ ⎨ ⎧ c_{1} e^{x} - c_{2} lo g_{e} (\frac{1}{x}), 3, if x > 0 otherwise$
where $c_{1}, c_{2} \in R$ . If $f$ is continuous at $x = 0$ , then $c_{1} + c_{2} =$ _________. (answer in integer)
Answer: 3
Solution
Answer: 3 $- c_{2} ln (1/ x) = c_{2} ln x$ , and as $x \to 0^{+}$ , $ln x \to - \infty$ . For the right-hand limit to be finite, $c_{2} = 0$ . Then $lim_{x \to 0^{+}} c_{1} e^{x} = c_{1}$ must equal $f (0) = 3$ , so $c_{1} = 3$ . $c_{1} + c_{2} = 3 + 0 = 3$ .
Question 33Programming & Data Structuresnat1 mark
The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is _________. (answer in integer)
Answer: 11
Solution
Answer: 11 In a full binary tree (every node has 0 or 2 children), $n = 2 i + 1$ , so $i = (23 - 1) /2 = 11$ internal nodes. The height is greatest when the tree is a "caterpillar": each internal node has one leaf child and one internal child. Each internal node then adds one level, so the height is 11.
Question 34Programming & Data Structuresnat1 mark
Consider the following program in C:
```
#include <stdio.h>

void func(int i, int j) {
  if(i < j) {
    int i = 0;
    while (i < 10) {
      j += 2;
      i++;
    }
  }
  printf("%d", i);
}

int main() {
  int i = 9, j = 10;
  func(i, j);
  return 0;
}
```
The output of the program is _________. (answer in integer) Note: Assume that the program compiles and runs successfully.
Answer: 9
Solution
Answer: 9 Inside the if block, int i = 0; declares a new i that shadows the parameter. The loop changes only that inner i (and j). The inner i goes out of scope when the block ends, so printf sees the parameter i = 9.
Question 35Operating Systemsnat1 mark
Consider a system consisting of $k$ instances of a resource $R$ , being shared by 5 processes. Assume that each process requires a maximum of two instances of resource $R$ and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only after acquiring the first instance. The minimum value of $k$ for the system to be deadlock-free is ________. (answer in integer)
Answer: 6
Solution
Answer: 6 Worst case: every process holds one instance and waits for its second. With $k = 5$ , all 5 instances are held and everyone waits, which is a deadlock. One more instance breaks this: $k = 5 (2 - 1) + 1 = 6$ . Some process can then finish and release its instances.
Question 36Digital Logicmcq2 marks
Consider the real valued variables X, Y and Z represented using the IEEE 754 single-precision floating-point format. The binary representations of X and Y in hexadecimal notation are as follows: X: 35C00000 Y: 34A00000 Let $Z = X + Y$ . Which one of the following is the binary representation of $Z$ , in hexadecimal notation?
- A.
  35C80000
- B.
  35CC0000
- C.
  35E80000
  ✓
- D.
  35EC0000
Answer: C
Solution
Answer: (C) 35E80000 Both X and Y are positive (sign bit $= 0$ ) single-precision numbers; bias $= 127$ , so the true exponent is $e - 127$ .
```
     hex     | exponent field  | mantissa | value
-------------+-----------------+----------+----------------
X  35C00000  | 0110 1011 = 107 | 1000...  | 1.1b  x 2^-20
Y  34A00000  | 0110 1001 = 105 | 0100...  | 1.01b x 2^-20
```
Decoding each number:
$X = 1. 1_{2} \times 2^{107 - 127} = 1. 1_{2} \times 2^{- 20} = 1.5 \times 2^{- 20}$

$Y = 1.0 1_{2} \times 2^{105 - 127} = 1.0 1_{2} \times 2^{- 22} = 0.010 1_{2} \times 2^{- 20}$
Align both to the larger exponent $2^{- 20}$ and add the mantissas:
$1.100 0_{2} + 0.010 1_{2} = 1.110 1_{2} \Rightarrow Z = 1.110 1_{2} \times 2^{- 20}$
This is already normalised ( $1. xxx x_{2}$ ), so the exponent stays $107 = 0110101 1_{2}$ and the stored mantissa is $11010 \dots$ Assemble the 32 bits:
```
sign  exponent   mantissa (23 bits)
 0    01101011   1101000 00000000 00000000
```
Regroup into nibbles: 0011 0101 1110 1000 0000 0000 0000 0000 = 0x35E80000. Decimal check: $1.5 + 0.3125 = 1.8125$ , and $1.8125 = 1.110 1_{2}$ (scaled by $2^{- 20}$ ). Matches option (C).
Question 37Digital Logicmcq2 marks
Consider a 2-bit saturating up/down counter that performs the saturating up count when the input P is 0, and the saturating down count when P is 1. The Next State table of the counter is as shown. The counter is built as a synchronous sequential circuit using D flip-flops. Next State table (present state $Q_{1} Q_{0}$ → next state $Q_{1}^{+} Q_{0}^{+}$ ):
```
 P | Q1 Q0 | Q1+ Q0+
---+-------+--------
 0 | 0  0  |  0   1 
 0 | 0  1  |  1   0 
 0 | 1  0  |  1   1 
 0 | 1  1  |  1   1 
 1 | 0  0  |  0   0 
 1 | 0  1  |  0   0 
 1 | 1  0  |  0   1 
 1 | 1  1  |  1   0 
```
Which one of the following options corresponds to the expressions for the inputs of the D flip-flops, $D_{1}$ and $D_{0}$ ?
- A.
  $D_{1} = P Q_{1} + P Q_{0} + Q_{1} Q_{0} D_{0} = P Q_{0} + P Q_{1} + Q_{1} Q_{0}$
- B.
  $D_{1} = P Q_{1} + P Q_{0} + Q_{1} Q_{0} D_{0} = P Q_{0} + P Q_{1} + Q_{1} Q_{0}$
  ✓
- C.
  $D_{1} = P Q_{1} + P Q_{0} + Q_{1} Q_{0} D_{0} = P Q_{0} + P Q_{1} + Q_{1} Q_{0}$
- D.
  $D_{1} = P Q_{1} + P Q_{0} + Q_{1} Q_{0} D_{0} = P Q_{0} + P Q_{1} + Q_{1} Q_{0}$
Answer: B
Solution
Answer: (B) For a D flip-flop, $D = Q^{+}$ . Plot each next-state column on a 3-variable K-map, with minterm index $= P Q_{1} Q_{0}$ . $D_{1} = Q_{1}^{+} = 1$ at minterms 1, 2, 3, 7. $D_{0} = Q_{0}^{+} = 1$ at minterms 0, 2, 3, 6. $D_{1} = P Q_{1} + P Q_{0} + Q_{1} Q_{0}$ and $D_{0} = P Q_{0} + P Q_{1} + Q_{1} Q_{0}$ . This matches (B) term for term. Shortcut: at state 00 with $P = 0$ the counter must go to 01, so $D_{0} (P = 0, 00) = 1$ . Only (B) has a $P Q_{0}$ term that gives this.
Question 38Computer Organization & Architecturemcq2 marks
The size of the physical address space of a processor is $2^{32}$ bytes. The capacity of a cache memory unit is $2^{23}$ bytes. The cache block size is 128 bytes. The cache memory unit can be built as a direct mapped cache or as a $K$ -way set-associative cache, where $K = 2^{L}$ and $L \in {1, 2, 3}$ . Let the length of the TAG field be $M$ bits for the direct mapped cache, and $N$ bits for the set-associative cache. Which one of the following options is true?
- A.
  $N = M + L$
  ✓
- B.
  $N = M - L$
- C.
  $N = M + K$
- D.
  $N = M - K$
Answer: A
Solution
Answer: (A) $N = M + L$ • Offset: $128 = 2^{7}$ , so 7 bits. • Direct mapped: $2^{23} / 2^{7} = 2^{16}$ lines, so a 16-bit index and $M = 32 - 16 - 7 = 9$ . • $K$ -way: $2^{16} / 2^{L}$ sets, so the index is $16 - L$ bits and $N = 32 - (16 - L) - 7 = 9 + L$ . Every doubling of associativity moves one bit from the index to the tag.
Question 39Programming & Data Structuresmcq2 marks
Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head.
```
struct node{
   int elt;
   struct node *next;
};

int getListSize (struct node *head)
{
  if( E1 ) return 1;
  return E2;
}
```
Which one of the following options gives the correct replacements for the expressions E1 and E2?
- A.
  E1: head == NULL E2: 1 + getListSize(head)
- B.
  E1: head->next == NULL E2: 1 + getListSize(head->next)
  ✓
- C.
  E1: head == NULL E2: 1 + getListSize(head->next)
- D.
  E1: head->next == NULL E2: 1 + getListSize(head)
Answer: B
Solution
Answer: (B) The base case returns 1, so it must fire at the last node, where head->next == NULL. Otherwise, count this node and recurse on the rest. • (A), (D): recursing on head itself never ends. • (C): returns 1 for NULL, which counts one node too many (a 3-node list gives 4).
Question 40Programming & Data Structuresmcq2 marks
Let $P$ be the set of all integers from 1 to 15. Consider any order of insertion of the elements of $P$ into a binary search tree that creates a complete binary tree. Which one of the following elements can NEVER be the third element that is inserted?
- A.
  4
- B.
  2
- C.
  10
- D.
  5
  ✓
Answer: D
Solution
Answer: (D) 5 Fifteen keys in a complete BST have a fixed shape: the root is 8, level 1 is {4, 12}, and level 2 is {2, 6, 10, 14}. A node can be inserted only after its parent. So 8 goes first, then 4 or 12 second, and the third is the other of 4/12 or a child of the second (2, 6, 10 or 14). 5 is on level 3 and needs 8, 4 and 6 before it. It can never be third.
Question 41Algorithmsmcq2 marks
Let $G (V, E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path. Let $s \in V$ be a vertex in $G$ . For every $u \in V$ and for every $k \geq 0$ , let $d_{k} (u)$ denote the weight of a shortest path (in terms of weight) from $s$ to $u$ of length at most $k$ . If there is no path from $s$ to $u$ of length at most $k$ , then $d_{k} (u) = \infty$ . Consider the statements: S1: For every $k \geq 0$ and $u \in V$ , $d_{k + 1} (u) \leq d_{k} (u)$ . S2: For every $(u, v) \in E$ , if $(u, v)$ is part of a shortest path (in terms of weight) from $s$ to $v$ , then for every $k \geq 0$ , $d_{k} (u) \leq d_{k} (v)$ . Which one of the following options is correct?
- A.
  Only S1 is true
  ✓
- B.
  Only S2 is true
- C.
  Both S1 and S2 are true
- D.
  Neither S1 nor S2 is true
Answer: A
Solution
Answer: (A) Only S1 is true S1 is true: every path of length $\leq k$ also has length $\leq k + 1$ , so allowing more edges can only keep or lower the minimum. (This is the Bellman-Ford invariant.) S2 is false. Counterexample: edges s–a (1), a–b (1), b–u (1), u–v (1), and s–v (10). The shortest path to $v$ is s-a-b-u-v with weight 4, so edge (u, v) lies on it. But with $k = 1$ : $d_{1} (u) = \infty$ and $d_{1} (v) = 10$ , so $d_{1} (u) > d_{1} (v)$ .
Question 42Compiler Designmcq2 marks
Consider the control flow graph shown in the figure. Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B4 and B5? Note: All the variables are integers.
- A.
  B4: ${b + i}$ B5: ${c + m}$
- B.
  B4: ${g * k}$ B5: ${c + m}$
- C.
  B4: ${g * k, b + i}$ B5: ${}$
- D.
  B4: ${g * k}$ B5: ${}$
  ✓
Answer: D
Solution
Answer: (D) An expression is redundant at a point only if it is available on every path reaching that point: computed earlier, with no operand redefined since.
```
Expression  | Path via B2                        | Path via B3                    | Redundant?
------------+------------------------------------+--------------------------------+-----------
g * k at B4 | computed (a = g*k), g, k unchanged | computed (t = g*k)             | Yes
b + i at B4 | available from B1                  | B3 redefines b, which kills it | No
c + m at B5 | never computed on this path        | computed in B3                 | No
```
So B4 has {g*k} and B5 has none. The traps are $b + i$ , killed by $b = c + m$ in B3, and $c + m$ , which is computed on only one path.
Question 43Databasesmcq2 marks
Consider a relational database schema with two relations $R (P, Q)$ and $S (X, Y)$ . Let $E = {⟨ u ⟩ ∣ \exists v \exists w ⟨ u, v ⟩ \in R \land ⟨ v, w ⟩ \in S}$ be a tuple relational calculus expression. Which one of the following relational algebraic expressions is equivalent to $E$ ?
- A.
  $Π_{P} (R ⋈_{R . P = S . X} S)$
- B.
  $Π_{P} (S ⋈_{S . X = R . Q} R)$
  ✓
- C.
  $Π_{P} (R ⋈_{R . P = S . Y} S)$
- D.
  $Π_{P} (S ⋈_{S . Y = R . Q} R)$
Answer: B
Solution
Answer: (B) Map the variables: in $⟨ u, v ⟩ \in R$ , $u$ is $R . P$ and $v$ is $R . Q$ . In $⟨ v, w ⟩ \in S$ , the same $v$ is $S . X$ . So the join condition is $R . Q = S . X$ , and the output is $u = R . P$ : $Π_{P} (S ⋈_{S . X = R . Q} R)$ . Join order does not matter.
Question 44Computer Networksmcq2 marks
A TCP sender successfully establishes a connection with a TCP receiver and starts the transmission of segments. The TCP congestion control mechanism’s slow-start threshold is set to 10000 segments. Assume that the round-trip time is fixed at 1 millisecond. Assume that the sender always has data to send, the segments are numbered from 1, and no segment is lost. Let $t$ denote the time (in milliseconds) at which the transmission of segment number 2000 starts. Which one of the following options is correct?
- A.
  $9 \leq t < 10$
- B.
  $10 \leq t < 11$
  ✓
- C.
  $11 \leq t < 12$
- D.
  $12 \leq t < 13$
Answer: B
Solution
Answer: (B) $10 \leq t < 11$ In slow start (the threshold of 10000 is never reached), cwnd doubles every RTT. The round starting at $t = k$ ms sends $2^{k}$ segments.
```
Round starts at t (ms) | cwnd | Segments sent
-----------------------+------+--------------
0                      | 1    | 1
1                      | 2    | 2–3
2                      | 4    | 4–7
…                      | …    | …
9                      | 512  | 512–1023
10                     | 1024 | 1024–2047
```
Segment 2000 lies in the round that starts at 10 ms, so $10 \leq t < 11$ .
Question 45Computer Networksmcq2 marks
Consider the implementation of sliding window protocol over a lossless link, with a window size of $W$ frames, where each frame is of size 1000 bits (including header). The bandwidth of the link is 100 kbps (1k = $1 0^{3}$ ) and the one-way propagation delay is 100 milliseconds. Assume that processing times at the sender and receiver are zero and the transmission time of acknowledgements is also zero. Which one of the following options gives the minimum size of $W$ (in number of frames) required to achieve 100% link utilization?
- A.
  10
- B.
  21
  ✓
- C.
  20
- D.
  11
Answer: B
Solution
Answer: (B) 21 $T_{t} = \frac{1000}{1 0 ^{5}} = 10$ ms and $T_{p} = 100$ ms. The first ACK comes back after $T_{t} + 2 T_{p} = 210$ ms. To keep the link busy all that time, the sender needs $W \geq \frac{T _{t} + 2 T _{p}}{T _{t}} = \frac{210}{10} = 21$ frames. The trap is answer 20 ( $2 T_{p} / T_{t}$ ), which forgets the first frame's own transmission time.
Question 46Engineering Mathematicsmsq2 marks
Let $f : R \to R$ be defined as follows:
$f (x) = (\frac{∣ x ∣}{2} - x) (x - \frac{∣ x ∣}{2})$
Which of the following statements is/are true?
- A.
  $f$ has a local maximum
  ✓
- B.
  $f$ has a local minimum
- C.
  $f^{'}$ is continuous over $R$
  ✓
- D.
  $f^{'}$ is not differentiable over $R$
  ✓
Answer: A, C, D
Solution
Answer: A, C, D Split at 0: • $x \geq 0$ : $(- \frac{x}{2}) (\frac{x}{2}) = - \frac{x ^{2}}{4}$ , so $f^{'} (x) = - \frac{x}{2}$ . • $x < 0$ : $(- \frac{3 x}{2}) (\frac{3 x}{2}) = - \frac{9 x ^{2}}{4}$ , so $f^{'} (x) = - \frac{9 x}{2}$ . • (A) True: $f (0) = 0 \geq f (x)$ for all $x$ . • (B) False: $f$ decreases on both sides of 0 forever, so there is no local minimum. • (C) True: $f^{'} (0^{-}) = f^{'} (0^{+}) = 0$ , so $f^{'}$ is continuous. • (D) True: $f^{''} (0^{-}) = - \frac{9}{2} \neq = f^{''} (0^{+}) = - \frac{1}{2}$ , so $f^{'}$ is not differentiable at 0.
Question 47Discrete Mathematicsmsq2 marks
Let $G (V, E)$ be a simple, undirected graph. A vertex cover of $G$ is a subset $V^{'} \subseteq V$ such that for every $(u, v) \in E$ , $u \in V^{'}$ or $v \in V^{'}$ . Let the size of the smallest vertex cover in $G$ be $k$ . Let $S$ be any vertex cover of size $k$ . For a vertex $v \in V$ , which of the following constraints will always ensure that $v \in S$ ?
- A.
  The degree of $v$ is at least $k + 1$
  ✓
- B.
  The vertex $v$ is on a path of length $k + 1$
- C.
  The vertex $v$ is on a cycle of length $k + 1$
- D.
  The vertex $v$ is a part of a clique of size $k$
Answer: A
Solution
Answer: A (A) True. If $v \in / S$ , every edge at $v$ must be covered by its other end, so all $\geq k + 1$ neighbours are in $S$ . Then $∣ S ∣ \geq k + 1$ , a contradiction. (B) False. Path 1–2–3–4–5: $k = 2$ with $S = {2, 4}$ . Vertex 1 lies on the path 1-2-3-4 of length $3 = k + 1$ , yet $1 \in / S$ . (C) False. Triangle {1, 2, 3}: $k = 2$ with $S = {1, 2}$ . Vertex 3 lies on a cycle of length $3 = k + 1$ , yet $3 \in / S$ . (D) False. In the same triangle, {1, 3} is a clique of size $k = 2$ containing 3, and $3 \in / S$ . A clique needs only all but one of its vertices in a cover.
Question 48Digital Logicmsq2 marks
Consider a Boolean function F with the following minterm expression:
$F (P, Q, R, S) = \sum m (1, 2, 3, 4, 5, 7, 10, 12, 13, 14)$
Which of the following options is/are the minimal sum-of-products expression(s) of F ?
- A.
  $P S + Q R + P Q R + Q R S$
- B.
  $P S + Q R + P Q R + P R S$
  ✓
- C.
  $P S + Q R + P Q S + P R S$
- D.
  $P S + Q R + P Q S + Q R S$
  ✓
Answer: B, D
Solution
Answer: B, D Essential prime implicants: $P S$ (covers 1, 3, 5, 7) and $Q R$ (covers 4, 5, 12, 13). That leaves 2, 10, 14 to cover. The prime implicants for the remaining cells are $P Q R$ (2, 3), $Q R S$ (2, 10), $P R S$ (10, 14) and $P Q S$ (12, 14). Two of them must cover 2, 10 and 14: • (A) $P Q R + Q R S$ : 14 is not covered. ✗ • (B) $P Q R + P R S$ : covers 2, 10, 14. ✓ • (C) $P Q S + P R S$ : 2 is not covered. ✗ • (D) $P Q S + Q R S$ : covers 2, 10, 14. ✓
Question 49Algorithmsmsq2 marks
Let $G (V, E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G$ is/are true?
- A.
  In every cycle $C$ of $G$ , the edge with the largest weight in $C$ is not in any MST
  ✓
- B.
  In every cycle $C$ of $G$ , the edge with the smallest weight in $C$ is in every MST
- C.
  For every vertex $v \in V$ , the edge with the largest weight incident on $v$ is not in any MST
- D.
  For every vertex $v \in V$ , the edge with the smallest weight incident on $v$ is in every MST
  ✓
Answer: A, D
Solution
Answer: A, D (with unique weights the MST is unique) • (A) True: this is the cycle property. The heaviest edge of any cycle can be swapped out for a lighter one. • (B) False: in triangle u-v-w with weights 5, 6, 7, add a path u-x-v with weights 1, 1. Edge u-v (5) is the lightest in its triangle but is not in the MST. • (C) False: for a leaf vertex, its only edge is both its heaviest and its lightest, and it must be in the MST. • (D) True: this is the cut property applied to the cut ${v}$ vs $V - {v}$ .
Question 50Algorithmsmsq2 marks
Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G (V, E)$ as input, where $d [v]$ and $f [v]$ are the discovery time and finishing time, respectively, of the vertex $v \in V$ .
```
DFS(G):                          Explore(G, v, t):
  unmark all v ∈ V                 mark v
  t ← 0                            t ← t + 1
  for each v ∈ V                   d[v] ← t
    if v is unmarked               for each (v, w) ∈ E
      t ← Explore(G, v, t)           if w is unmarked
    end if                             t ← Explore(G, w, t)
  end for                            end if
                                   end for
                                   t ← t + 1
                                   f[v] ← t
                                   return t
```
Suppose that the input directed graph $G (V, E)$ is a directed acyclic graph (DAG). For an edge $(u, v) \in E$ , which of the following options will NEVER be correct?
- A.
  $d [u] < d [v] < f [v] < f [u]$
- B.
  $d [v] < d [u] < f [u] < f [v]$
  ✓
- C.
  $d [v] < f [v] < d [u] < f [u]$
- D.
  $d [u] < d [v] < f [u] < f [v]$
  ✓
Answer: B, D
Solution
Answer: B, D Key fact: in a DAG, every edge $(u, v)$ satisfies $f [v] < f [u]$ . This is why reverse finishing order is a topological sort. • (A) Tree or forward edge: possible. • (B) $u$ is nested inside $v$ , so $(u, v)$ is a back edge, which means a cycle. Never. • (C) Cross edge to an already finished $v$ : possible. • (D) The intervals partly overlap, which the parenthesis theorem rules out for any DFS. Never.
Question 51Theory of Computationmsq2 marks
Let $L_{1}$ and $L_{2}$ be two languages over a finite alphabet, such that $L_{1} \cap L_{2}$ and $L_{2}$ are regular languages. Which of the following statements is/are always true?
- A.
  $L_{1}$ is regular
- B.
  $L_{1} \cup L_{2}$ is regular
- C.
  $L_{2}$ is context-free
  ✓
- D.
  $L_{1}$ is context-free
Answer: C
Solution
Answer: C Take $L_{2} = \emptyset$ . Then $L_{1} \cap L_{2} = \emptyset$ is regular for any $L_{1}$ , even an undecidable one. • (A) and (D) fail for such an $L_{1}$ . • (B) $L_{1} \cup \emptyset = L_{1}$ , which also fails. • (C) is always true: every regular language is context-free.
Question 52Theory of Computationmsq2 marks
Consider the following context-free grammar $G$ .
$S A B \to aba A B A bba \to aa B B A b ∣ b B abaa \to a B b ∣ ab$
In the above grammar, $S$ is the start symbol, $a$ and $b$ are terminal symbols, and $A$ and $B$ are non-terminal symbols. Let $L (G)$ be the language generated by the grammar $G$ . For a string $s \in L (G)$ , let $n_{1} (s)$ be the number of $a$ ’s in $s$ and $n_{2} (s)$ be the number of $b$ ’s in $s$ . Which of the following statements is/are true?
- A.
  There is a string $s \in L (G)$ such that $n_{1} (s) < n_{2} (s)$
- B.
  For every string $s \in L (G)$ , $n_{1} (s) \geq n_{2} (s)$
  ✓
- C.
  There is a string $s \in L (G)$ such that $n_{1} (s) > 2 n_{2} (s)$
- D.
  For every string $s \in L (G)$ , $n_{1} (s) \leq 2 n_{2} (s)$
  ✓
Answer: B, D
Solution
Answer: B, D Track (#a, #b) for each non-terminal. • $B = a^{n} b^{n}$ with $n \geq 1$ : equal a's and b's. • $A \to b B abaa$ : adds a:3, b:2 plus a balanced $B$ , so $# a - # b = + 1$ . • $A \to aa B B A b$ : adds a:2, b:1 plus balanced $B$ s, so +1 more per step. Every $A$ has $# a - # b = r \geq 1$ . • $S$ : the terminals "aba" and "bba" give a:3, b:3, so $# a - # b = r_{1} + r_{2} \geq 2$ . So $n_{1} > n_{2}$ always: (B) true, (A) false. Ratio check: each block keeps $# a \leq 2# b$ : the $B$ block, a:3 ≤ 2·2, a:2 ≤ 2·1, and a:3 ≤ 2·3. Sums of such blocks keep the bound, so (D) is true and (C) false.
Question 53Compiler Designmsq2 marks
Consider the following two syntax-directed definitions SDD1 and SDD2 for type declarations.
```
SDD1 grammar (G1) | Semantic rules
------------------+----------------------------------------
D → T V           | D.type = T.type; V.type = T.type
T → int           | T.type = int
T → float         | T.type = float
V → V₁ id         | V₁.type = V.type; put(id.entry, V.type)
V → id            | put(id.entry, V.type)
```
```
SDD2 grammar (G2) | Semantic rules
------------------+-----------------------------------------
D → D₁ id         | D.type = D₁.type; put(id.entry, D₁.type)
D → T id          | D.type = T.type; put(id.entry, T.type)
T → int           | T.type = int
T → float         | T.type = float
```
$D$ is the start symbol, and int, float and id are the three terminals. The non-terminal $V_{1}$ is the same as $V$ and the non-terminal $D_{1}$ is the same as $D$ . Here, the subscript is used to differentiate the grammar symbols on the two sides of a production. The function put updates the symbol table with the type information for an identifier. Let P and Q be the languages specified by grammars G1 and G2, respectively. Which of the following statements is/are true?
- A.
  The languages P and Q are the same
  ✓
- B.
  SDD2 is S-attributed and contains only synthesized attributes
  ✓
- C.
  SDD1 is L-attributed and contains only inherited attributes
- D.
  The specifications of SDD1 and SDD2 are such that the same entries get added to the symbol table
  ✓
Answer: A, B, D
Solution
Answer: A, B, D • (A) True: both generate $(int ∣ float) id^{+}$ . • (B) True: in SDD2 every attribute (D.type, T.type) is computed from children, so it is S-attributed. • (C) False: SDD1 is L-attributed, but T.type is synthesized (and so is D.type), so it does not contain "only inherited" attributes. • (D) True: both call put once per id with the declared type.
Question 54Operating Systemsmsq2 marks
Consider a system that has a cache memory unit and a memory management unit (MMU). The address input to the cache memory is a physical address. The MMU has a translation lookaside buffer (TLB). Assume that when a page is evicted from the main memory, the corresponding blocks in the cache are marked as invalid. For a given memory reference, which of the following sequences of events can NEVER happen?
- A.
  TLB miss, Page table hit, Cache hit
- B.
  TLB hit, Page table miss, Cache hit
  ✓
- C.
  TLB miss, Page table miss, Cache hit
  ✓
- D.
  TLB miss, Page table miss, Cache miss
Answer: B, C
Solution
Answer: B, C • (A) Possible: the translation is found in the page table and the block is in the cache. • (B) Never: a TLB hit means the page table is not consulted, so there can be no page-table miss. • (C) Never: a page-table miss is a page fault, so the page is not in RAM, and its cache blocks were invalidated when it was evicted. It cannot be a cache hit. • (D) Possible: an ordinary page fault.
Question 55Algorithmsmsq2 marks
An undirected, unweighted, simple graph $G (V, E)$ is said to be 2-colorable if there exists a function $c : V \to {0, 1}$ such that for every $(u, v) \in E$ , $c (u) \neq = c (v)$ . Which of the following statements about 2-colorable graphs is/are true?
- A.
  If $G$ is 2-colorable, then $G$ may contain cycles of odd length
- B.
  If $G$ is 2-colorable, then $G$ may contain cycles of even length
  ✓
- C.
  An optimal algorithm for testing whether $G$ is 2-colorable runs in time $Θ (∣ V ∣ + ∣ E ∣)$ , if $G$ is represented as an adjacency list
  ✓
- D.
  An optimal algorithm for testing whether $G$ is 2-colorable runs in time $Θ (∣ E ∣ lo g ∣ V ∣)$ , if $G$ is represented as an adjacency list
Answer: B, C
Solution
Answer: B, C 2-colourable is the same as bipartite, which is the same as having no odd cycle. So (A) is false and (B) is true (for example $C_{4}$ ). BFS or DFS colouring checks every edge once, in $Θ (∣ V ∣ + ∣ E ∣)$ time. That is optimal, because every edge must be read. So (C) is true and (D) false.
Question 56Computer Networksmsq2 marks
An ISP having an address block 202.16.0.0/15 assigns a block of 6000 IP addresses to a client, using the classless internet domain routing (CIDR) super-netting approach. Which of the following address blocks can be assigned by the ISP?
- A.
  202.16.0.0/19
  ✓
- B.
  202.17.64.0/19
  ✓
- C.
  202.16.32.0/19
  ✓
- D.
  202.17.24.0/19
Answer: A, B, C
Solution
Answer: A, B, C 6000 addresses need the next power of two, $2^{13} = 8192$ , so the prefix is $/32 - 13 = /19$ . The ISP's /15 spans 202.16.0.0 – 202.17.255.255. A /19 must start on a boundary of 8192 addresses, which means the third octet must be a multiple of 32. • (A) 202.16.0.0 ✓ • (B) 202.17.64.0 ✓ • (C) 202.16.32.0 ✓ • (D) 202.17.24.0: 24 is not a multiple of 32, so it is not a valid /19 ✗
Question 57Discrete Mathematicsnat2 marks
Let $G$ be an undirected graph, which is a path on 8 vertices. The number of matchings in $G$ is ______. (answer in integer)
Answer: 34
Solution
Answer: 34 (the empty matching counts) Let $m (n)$ be the number of matchings in a path on $n$ vertices. Look at the last vertex: either it is unmatched, giving $m (n - 1)$ , or it is matched with its neighbour, giving $m (n - 2)$ . So $m (n) = m (n - 1) + m (n - 2)$ , with $m (1) = 1$ and $m (2) = 2$ .
```
n    | 1 | 2 | 3 | 4 | 5 | 6  | 7  | 8
-----+---+---+---+---+---+----+----+---
m(n) | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34
```
These are Fibonacci numbers.
Question 58Engineering Mathematicsnat2 marks
Let $X$ be a random variable which takes values in the set ${1, 2, 3, 4, 5, 6, 7, 8}$ . Further, $Pr (X = 1) = Pr (X = 2) = Pr (X = 5) = Pr (X = 7) = \frac{1}{6}$ and $Pr (X = 3) = Pr (X = 4) = Pr (X = 6) = Pr (X = 8) = \frac{1}{12}$ . The expected value of $X$ , denoted by $E [X]$ , is equal to ___________. (rounded off to two decimal places)
Answer: 4.24 to 4.26
Solution
Answer: 4.25 Check that the probabilities sum to 1: $4 \cdot \frac{1}{6} + 4 \cdot \frac{1}{12} = 1$ ✓.
$E [X] = \frac{1 + 2 + 5 + 7}{6} + \frac{3 + 4 + 6 + 8}{12} = \frac{15}{6} + \frac{21}{12} = 2.5 + 1.75 = 4.25$
Question 59Computer Organization & Architecturenat2 marks
Consider a hard disk with a rotational speed of 15000 rpm. The time to move the read/write head from a track to its adjacent track is 1 millisecond. Initially, the head is on track 0. The number of sectors per track is 400. The sector size is 1024 bytes. It is necessary to transfer data from 10 randomly located sectors in each of the following tracks in the order: 5, 12 and 7. The total time for the data transfer (in milliseconds) from the hard disk is _________. (rounded off to one decimal place)
Answer: 77.3
Solution
Answer: 77.3 ms • One rotation: $60000/15000 = 4$ ms, so the average rotational latency is 2 ms. • One sector transfer: $4/400 = 0.01$ ms. • Seek: $0 \to 5 \to 12 \to 7$ is $5 + 7 + 5 = 17$ tracks, so 17 ms. • 30 randomly placed sectors: each costs $2 + 0.01 = 2.01$ ms, so $30 \times 2.01 = 60.3$ ms. Total $= 17 + 60.3 = 77.3$ ms.

Question 60Computer Organization & Architecturenat2 marks

The EX stage of a pipelined processor performs the memory read operations for LOAD instructions, and the operations for the arithmetic and logic instructions. Let

t_{E X}

denote the time taken by the EX stage to perform the operation for an instruction. For each instruction type, the values of

t_{E X}

and M (the number of instructions of that type in a sequence of 100 instructions for a program P), are given in the table below. The duration of the pipeline clock cycle is 1 nanosecond. Assume that the latch time for the interstage buffers in the pipeline is negligible.

Instruction            | t_(EX) in nanoseconds | M
-----------------------+-----------------------+---
LOAD                   | 1.8                   | 15
IMUL                   | 1.5                   | 10
IDIV                   | 2.5                   | 5
FADD                   | 1.7                   | 10
FSUB                   | 1.7                   | 5
FMUL                   | 2.8                   | 15
FDIV                   | 3.2                   | 5
All other instructions | Less than 1.0         | 35

When program P is executed, the number of clock cycles for which the pipeline is stalled due to structural hazards in the EX stage is ______. (answer in integer)

Answer: 95

Solution

Answer: 95 An instruction occupies EX for

⌈ t_{E X} /1 ns ⌉

cycles, so it stalls the instructions behind it for

⌈ t_{E X} ⌉ - 1

cycles.

Type   | t_(EX) | EX cycles | Stalls each | M   | Total
-------+--------+-----------+-------------+-----+------
LOAD   | 1.8    | 2         | 1           | 15  | 15
IMUL   | 1.5    | 2         | 1           | 10  | 10
IDIV   | 2.5    | 3         | 2           | 5   | 10
FADD   | 1.7    | 2         | 1           | 10  | 10
FSUB   | 1.7    | 2         | 1           | 5   | 5
FMUL   | 2.8    | 3         | 2           | 15  | 30
FDIV   | 3.2    | 4         | 3           | 5   | 15
Others | < 1    | 1         | 0           | 35  | 0
       |        |           |             | Sum | 95

Question 61Programming & Data Structuresnat2 marks

Consider the recursive functions represented by the following code segment:

int bar(int n){
     if (n == 1) return 0;
     else return 1 + bar(n/2);
}

int foo(int n){
     if (n == 1) return 1;
     else return 1 + foo(bar(n));
}

The smallest positive integer n for which foo(n) returns 5 is ______. (answer in integer) Note: Ignore syntax errors (if any) in the function.

Answer: 65536

Solution

Answer: 65536 bar(n)

= ⌊ lo g_{2} n ⌋

, and foo counts how many times you can apply

⌊ lo g_{2} ⌋

before reaching 1. That is an iterated logarithm, plus 1. Build the smallest

n

for each value, working backwards:

foo(n) | Need bar(n) to be             | Smallest n
-------+-------------------------------+---------------
1      | –                             | 1
2      | 1                             | 2
3      | ≥ 2 (smallest giving foo = 2) | 4
4      | ≥ 4                           | 16
5      | ≥ 16                          | 2^(16) = 65536

Check:

65536 \to 16 \to 4 \to 2 \to 1

. That is 4 calls to bar, so foo returns

1 + 4 = 5

. Note that bar(1) = 0 would make foo(0) recurse forever, but the chain above never calls foo(0).

Question 62Programming & Data Structuresnat2 marks
The following sequence corresponds to the preorder traversal of a binary search tree $T$ : 50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77 The position of the element 60 in the postorder traversal of $T$ is ______. (answer in integer) Note: The position begins with 1.
Answer: 7
Solution
Answer: 7 Inserting the preorder sequence into an empty BST rebuilds $T$ : Postorder (left, right, root): 13, 30, 47, 40, 25, 70, 60, 77, 80, 75, 50. 60 is at position 7.
Question 63Operating Systemsnat2 marks
Consider the following program snippet. Assume that the program compiles and runs successfully. Further, assume that the fork() system call is always successful in creating a process.
```
int main () {
   int i;
   for (i = 0; i < 3; i++){
      if (fork() == 0){
        continue;
      }
      break;
   }
   printf("Hello!");
   return 0;
}
```
The total number of times that the printf statement gets executed is ________. (answer in integer)
Answer: 4
Solution
Answer: 4 After each fork(), the parent breaks out of the loop and prints. The child continues and forks again, so the processes form a chain, not a tree. Each of the 4 processes prints once, so the total is 4. (A plain fork() loop without the break would make $2^{3} = 8$ .)
Question 64Operating Systemsnat2 marks
Consider a CPU that has to execute two types of processes. The first type, Actuators (A), requires a CPU burst of 6 seconds. The second type, Controllers (C), requires a CPU burst of 8 seconds. A new process of type A arrives at time $t$ = 10, 20, 30, 40, and 50 (in seconds). Similarly, a new process of type C arrives at time $t$ = 11, 22, 33, 44, and 55 (in seconds). The CPU scheduling policy is First Come First Serve (FCFS). The first process of type A starts running at $t$ = 10 seconds. The average waiting time (in seconds) for the 10 processes is ___________. (rounded off to one decimal place)
Answer: 9.5
Solution
Answer: 9.5 s
```
Process | Arrival | Start | Waiting = Start − Arrival
--------+---------+-------+--------------------------
A1      | 10      | 10    | 0
C1      | 11      | 16    | 5
A2      | 20      | 24    | 4
C2      | 22      | 30    | 8
A3      | 30      | 38    | 8
C3      | 33      | 44    | 11
A4      | 40      | 52    | 12
C4      | 44      | 58    | 14
A5      | 50      | 66    | 16
C5      | 55      | 72    | 17
        |         | Total | 95
```
Average $= 95/10 = 9.5$ s.
Question 65Databasesnat2 marks
Consider a relational database schema with a relation $R (A, B, C, D)$ . If ${A, B}$ and ${A, C}$ are the only two candidate keys of the relation $R$ , then the number of superkeys of relation $R$ is ______. (answer in integer)
Answer: 6
Solution
Answer: 6 A superkey is any superset of a candidate key. Use inclusion–exclusion: • Supersets of AB: C and D are free, so $2^{2} = 4$ . • Supersets of AC: B and D are free, so $2^{2} = 4$ . • Supersets of both (contain ABC): D is free, so $2^{1} = 2$ . Total $= 4 + 4 - 2 = 6$ : AB, AC, ABC, ABD, ACD, ABCD.

Practice the full paper with a timer

Attempt GATE CS 2026 Set 1 in the exact GATE interface and get a detailed score and topic-wise analysis — free.

Create free account →