 ### Computer Science (GATE Exam) 2006 - Previous Question Paper Solution

 Description: GATE Exam Previous Year Question Paper Solution Computer Science(CS) - 2006 Number of Questions: 85 Created by: Aliensbrain Bot Tags: Computer Science GATE CS Previous Year Paper
Attempted 0/85 Correct 0 Score 0

Consider the polynomial p(x) = a0 + a1x + a2x^2 +a3x^3, where ai != 0, for all i. The minimum number of multiplications needed to evaluate p on an input x is :

1. 3

2. 4

3. 6

4. 9

Correct Option: A
Explanation: The set (1, 2, 3, 5, 7, 8, 9) under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false?

1. It is not closed

2. 2 does not have an inverse

3. 3 does not have an inverse

4. 8 does not have an inverse

Correct Option: C
Explanation:

The definition of binary operation multiplication modulo 10 is a follows
aob = (a x b)% 10
And the identity element for the given set = 1
For closure property, 2 or 7 = 4 $\notin$ set
So, the set is not closed
Here, 2 and 8 do not have an inverse, so 307 = 1
Hence, 7 is the inverse of 3.

For which one of the following reasons does Internet Protocol (IP) use the time to-live (TTL) field in the IP datagram header?

1. Ensure packets reach destination within that time

2. Discard packets that reach later than that time

3. Prevent packets from looping indefinitely

4. Limit the time for which a packet gets queued in intermediate routers.

Correct Option: B
Explanation: A relation R is defined on ordered pairs of integers as follows:
(x,y) R (u,v) if x < u and y > v. Then R is:

1. Neither a Partial Order nor an Equivalence Relation

2. A Partial Order but not a Total Order

3. A Total Order

4. An Equivalence Relation

Correct Option: A
Explanation:

An essential condition for Partial order, Total order and Equivalence Relation is Reflexive property. The given set is not reflexive as $\forall x, y \in I, \therefore$(x,y) is not related to (x,y)

In a binary max heap containing n numbers, the smallest element can be found in time

1. O (n)

2. O (log n)

3. O (log log n)

4. O (1)

Correct Option: A
Explanation: To implement Dijkstra's shortest path algorithm on un weighted graphs so that it runs in linear time, the data structure to be used is:

1. Queue

2. Stack

3. Heap

4. B-Tree

Correct Option: C
Explanation: You are given a free running clock with a duty cycle of 50% and a digital waveform f which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of f by 180°?

1. 2. 3. 4. Correct Option: B
Explanation:  A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)?

1. 400

2. 500

3. 600

4. 700

Correct Option: C
Explanation:

Each address is equivalent to one byte in memory. Each instruction has 24 bits i.e., 3 bytes. So, from 300 onwards only a multiple of 3 will designate a valid program counter. Thus, (400 - 300) (500 - 300) and (700 - 300) are not multiple of 3.
But 600 -300 = 300 is a multiple of 3

Which one of the following in place sorting algorithms needs the minimum number of swaps?

1. Quick sort

2. Insertion sort

3. Selection sort

4. Heap sort

Correct Option: D
Explanation: Let $X,Y,Z$ be sets of sizes x, y and z respectively. Let $W = X \times Y$ and $E$ be the set of all subsets of $W$. The number of functions from $Z$ to $E$ is

1. $z^{2^{xy}}$

2. $z \times 2^{xy}$

3. $z^{2^{x+y}}$

4. $2^{xyz}$

Correct Option: D
Explanation:

The number of functions from a set A to a set B
Where, |A | = m and, |B| = n is nm
Also W = X x Y
$\Rightarrow$| W | = xy
$\because$| E | = 2xy
|Z| = z
So, the number of functions from Z to E is (2xy)z = 2xyz

Consider a weighted complete graph G on the vertex set {v1, v2,............., vn} such that the weight of the edge (vi, vj) is 2 |i - j| . The weight of a minimum spanning tree of G is:

1. n − 1

2. 2n − 2

3. $\begin{pmatrix} n \\ 2 \end{pmatrix}$

4. n2

Correct Option: B
Explanation: A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X. For a node stored at X [i], the left child, if any, is stored in X [2i] and the right child, if any, in X [2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be

1. log2 n

2. n

3. 2n + 1

4. 2n - 1

Correct Option: B
Explanation: An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

1. Solves it in linear time using a left to right pass of the array

2. Solves it in linear time using a right to left pass of the array

3. Solves it using divide and conquer in time O(n log n)

4. Solves it in time O(n2)

Correct Option: C
Explanation: Consider the following grammar

S→ S * E
S→ E
E→ F + E
E→ F
F→ id
Consider the following LR(0) items corresponding to the grammar above

S → S *.E
E → F. + E
E → F + .E
Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

1. (i) and (ii)

2. (ii) and (iii)

3. (i) and (iii)

4. None of the above

Correct Option: C
Explanation: We are given a set X = {x1 ..............xn } where xi = 2i A sample S $\subseteq$ X is drawn by selecting each xi independently with probability pi = 1/2. The expected value of the smallest number in sample S is:

1. $\dfrac{1}{2}$

2. 2

3. $\sqrt{n}$

4. n

Correct Option: B
Explanation:

As the sample S $\subseteq$ X, each element of S is an integral power of 2. The expected value of the smallest number is sample S is 2.

For each element in a set of size 2n, an unbiased coin is tossed. The 2n coin tosses are independent. An element is chosen if the corresponding coin toss were head. The probability that exactly n elements are chosen is:

1. $\frac{^{2n}\mathrm{C}_n}{4^n}$

2. $\frac{^{2n}\mathrm{C}_n}{2^n}$

3. $\frac{1}{^{2n}\mathrm{C}_n}$

4. $\frac{1}{2}$

Correct Option: A
Explanation:

Required favourable cases = Number of ways of selecting n element out of the set of size 2n = $^{2n}\mathrm{C}n$ As each toss may result in either head or tail, so for 2n tosses, total no. of combinations = 22n = 4n
$\therefore$Required probability = $\dfrac{\text{Favourable cases}}{\text{Total cases}}$
$= \frac{^{2n}\mathrm{C} n}{4^n}$

Let $E, F$ and $G$ be finite sets. Let

$X = (E ∩ F) - (F ∩ G)$ and
$Y = (E - (E ∩ G)) - (E - F)$.

Which one of the following is true?

1. $X ⊂ Y$

2. $X ⊃ Y$

3. $X = Y$

4. $X - Y ≠ \phi$ and $Y - X ≠ \phi$

Correct Option: C

Let S = {1, 2, 3,........, m}, m >3. Let X1.........Xn be subsets of S each of size 3. Define a function f from S to the set of natural numbers as, f(i) is the number of sets Xj that contain the element i. That is $f(i)=\left | \left\{j \mid i\in X_j \right\} \right|$ then $\sum_{i=1}^{m} f(i)$ is:

1. 3m

2. 3n

3. 2m + 1

4. 2n + 1

Correct Option: B
Explanation:

Suppose,
S = {1, 2, 3, 4} m = 4
X1 = { 1, 2, 3, } X2 = { 1, 3, 4} n = 2
$\therefore f(i)= f(1) + f(2) + f(3) + f(4)$
= 2 + 1 + 2 + 1
= 6 = 3 x 2 = 3n

Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at time 0, 2 and 6 respectively. How many context switches are needed if the operating system implements shortest remaining time first scheduling (SRTFS) algorithm? Do not count the context switches at time zero and at the end.

1. 1

2. 2

3. 3

4. 4

Correct Option: B
Explanation: Given a set of elements N = {1, 2, ..., n} and two arbitrary subsets A⊆N and B⊆N, how many of the n! permutations $\pi$ from N to N satisfy min($\pi$(A)) = min($\pi$(B)), where min(S) is the smallest integer in the set of integers S, and $\pi$(S) is the set of integers obtained by applying permutation $\pi$ to each element of S?

1. (n - |A ∪ B|) |A| |B|

2. $(|A|^2 + |B|^2)n^2$

3. $n! \frac{|A ∩ B|}{|A ∪ B|}$

4. $\frac{|A ∩ B|^2}{^n \mathrm{C}_{|A ∪ B|}}$

Correct Option: D

$F$ is an $n\times n$ real matrix. $b$ is an $n\times 1$ real vector. Suppose there are two $n\times 1$ vectors, $u$ and $v$ such that, $u ≠ v$ and $Fu = b, Fv = b$. Which one of the following statements is false?

1. Determinant of F is zero

2. There are an infinite number of solutions to Fx = b

3. There is an $x≠0$ such that $Fx = 0$

4. F must have two identical rows

Correct Option: D
Explanation:

(A) : Correct. We are given

$$Fu = b$$

$$Fv = b$$

So $F(u-v) = 0$

Since $u \neq v$, so we have a non-zero solution $w = (u-v)$ to homogeneous equation $Fx=0$. Now any vector $\lambda w$ is also a solution of $Fx=0$, and so we have infinitely many solutions of $Fx=0$, and so determinant of F is zero.

(B) : Correct. Consider a vector $u+\lambda w$.

$$F(u+\lambda w) = Fu+F(\lambda w) = b + 0 = b$$

So there are infinitely many vectors of the form $u+\lambda w$, which are solutions to equation $Fx=b$.

(C) : Correct. In option (a), we proved that vector $(u-v) \neq 0$ satisfies equation $Fx=0$.

(D) : False. This is not necessary.

So option (D) is the answer.

Consider the following C-program fragment in which i, j and n are integer variables.

for( i = n, j = 0; i &gt; 0; i /= 2, j +=i );
Let val ( j ) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?

1. $val(j)=\Theta(\log n)$

2. $val(j)=\Theta (\sqrt{n})$

3. $val(j)=\Theta( n)$

4. $val(j)=\Theta (n\log n)$

Correct Option: C
Explanation:

$j = n/2+n/4+n/2+\ldots +1$

number of iteration will be $2^k = n$ or $k = \log n$

this is in GP find sum till $\log n$,= $\Theta(n)$

Consider the following propositional statements:
P1 : ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))
P2 : ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))

Which one of the following is true?

1. P1 is a tautology, but not P2

2. P2 is a tautology, but not P1

3. P1 and P2 are both tautologies

4. Both P1 and P2 are not tautologies

Correct Option: D
Explanation:

null Consider the circuit above. Which one of the following options correctly represents f (x, y, z)?

1. $x\bar{z}+xy+\bar{y}z$$2. x\bar{z}+xy+\overline{yz} 3. xz+xy+\overline{yz} 4. xz+x\bar{y}+\bar{y}z Correct Option: A Explanation: Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lions attack if they are hungry or threatened. 1. ∀x[(tiger(x) ∧ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}] 2. ∀x[(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) ∧ attacks(x)}] 3. ∀x[(tiger(x) ∨ lion(x)) → {attacks(x) → (hungry(x) ∨ threatened(x))}] 4. ∀x[(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}] Correct Option: D Explanation: The given statement can be explained as follows: If x is lion or if it is hungry or it is threatened, x will attack P(x) = lion (x) v tiger (x) Q(x) = hungry (x) v threatened (x) R (x) = attacks (x) P(x) \rightarrow (Q (x) \rightarrow R (x)) Expanding all, ∀x[(lion(x) ∨ tiger(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}] We consider the addition of two 2's complement numbers b_{n-1}b_{n-2}\dots b_{0} and a_{n-1}a_{n-2}\dots a_{0}. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by c_{n-1}c_{n-2}\dots c_{0} and the carry-out by c_{out}. Which one of the following options correctly identifies the overflow condition? 1. c_{out}\left ( \overline{a_{n-1}\oplus b_{n-1}} \right ) 2. a_{n-1}b_{n-1}\overline{c_{n-1}}+\overline{a_{n-1}b_{n-1}}c_{n-1} 3. c_{out}\oplus c_{n-1} 4. a_{n-1}\oplus b_{n-1}\oplus c_{n-1} Correct Option: C Explanation: Binary adder generates C out only if Consider a Boolean function f(w,x,y,z). Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors i_{1}=\left \langle w_{1}, x_{1}, y_{1},z_{1}\right \rangle and i_{2}=\left \langle w_{2}, x_{2}, y_{2},z_{2}\right \rangle , we would like the function to remain true as the input changes from i_{1} to i_{2} ( i_{1} and i_{2} differ in exactly one bit position) without becoming false momentarily. Let f(w,x,y,z)=\sum (5,7,11,12,13,15) . Which of the following cube covers of f will ensure that the required property is satisfied? 1. \overline{w}xz,wx\overline{y},x\overline{y}z,xyz,wyz 2. wxy, \overline{w}xz,wyz 3. wx\overline{y} \overline{z}, xz, w\overline{x}yz 4. wx\overline{y}, wyz, wxz, \overline{w}xz, x\overline{y}z, xyz Correct Option: A Explanation: Station A uses 32 byte packets to transmit messages to Station B using a sliding window protocol. The round trip delay between A and B is 80 milliseconds and the bottleneck bandwidth on the path between A and B is 128 kbps. What is the optimal window size that A should use? 1. 20 2. 40 3. 160 4. 320 Correct Option: B Explanation: Station A needs to send a message consisting of 9 packets to Station B using a sliding window (window size 3) and go-back-n error control strategy. All packets are ready and immediately available for 1. 12 2. 14 3. 16 4. 18 Correct Option: A Explanation:  A logical binary relation \odot, is defined as follows: A B A\odot B True True True True False True False True False False False True Let \sim be the unary negation (NOT) operator, with higher precedence then \odot. Which one of the following is equivalent to A\wedge B ? 1. (\sim A\odot B) 2. \sim(A \odot \sim B) 3. \sim(\sim A\odot\sim B) 4. \sim(\sim A\odot B) Correct Option: D Explanation: |||||| |---|---|---|---|---| | A| B| A \odot B| ~ (~ A \odot B)| A \odot B| | T| T| T| ~F=T| T| | T| F| T| ~T=F| F| | F| T| F| ~T=F| F| | F| F| T| ~T=F| T| Let T be a depth first search tree in an undirected graph G. Vertices u and n are leaves of this tree T. The degrees of both u and n in G are at least 2. Which one of the following statements is true? 1. There must exist a vertex w adjacent to both u and n in G. 2. There must exist a vertex w whose removal disconnects u and n in G. 3. There must exist a cycle in G containing u and n. 4. There must exist a cycle in G containing u and all its neighbours in G. Correct Option: A Explanation: The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which the median is selected as pivot? 1. O(n) 2. O(n log n) 3. O(n)3 4. O(n)2 Correct Option: B Explanation: If we use median as a pivot element, then the recurrence for all cases becomes T(n) = 2T(n/2) + O(n) The above recurrence can be solved using Master Method. It falls in case 2 of master method. Two computers C1 and C2 are configured as follows. C1 has IP address 203.197.2.53 and netmask 255.255.128.0. C2 has IP address 203.197.75.201 and netmask 255.255.192.0. Which one of the following statements is true? 1. C1 and C2 both assume they are on the same network 2. C2 assumes C1 is on same network, but C1 assumes C2 is on a different network 3. C1 assumes C2 is on same network, but C2 assumes C1 is on a different network 4. C1 and C2 both assume they are on different networks. Correct Option: C Explanation: Consider numbers represented in 4-bit gray code. Let h3 h2 h1 h0 be the gray code representation of a number n and let g3 g2 g1 g0 be the gray code of (n + 1) (modulo 16) value of the number. Which one of the following functions is correct? 1. g0 (h3 h2 h1 h0) = \sum1, 2, 3, 6, 10, 13, 14, 15 2. g0 (h3 h2 h1 h0) = \sum4,9,10,11,12,13, 14,15 3. g0 (h3 h2 h1 h0) = <\sum2, 4,5, 6, 7,12,13,15 4. g0 (h3 h2 h1 h0) = \sum0,1,6, 7,10,11,12,13 Correct Option: B Explanation:   Given two three bit numbers a2 a1 a0 and b2 b1 b0 and c, the carry in, the function that represents the carry generate function when these two numbers are added is: 1. a2 b2 + a2 a1 b1 + a2 a1 a0 b0 + a2 a0 b1 b0 + a1 b2 b1 + a1 a0 b2 b0 + a0 b2 b1 b0 2. a2 b2 + a2 a1 b0 + a2 a1 b1 b0 + a1 a0 b2 b1 + a1 a0 b2 + a1 a0 b2 b0 + a2 a0 b1 b0 3. a2 + b2 + (a2\oplusb2) (a1 + b1 +(a1\oplusb1) (a0 + b0)) 4. Correct Option: C Explanation: Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal's algorithm? 1. (a − b), (d − f ) , (b − f ), (d − c) , (d − e) 2. (a − b), (d − f ) , (d − c) , (b − f ) , (d − e) 3. (d − f ), (a − b) , (d − c) , (b − f ) , (d − e) 4. (d − f ), (a − b) , (b − f ), (d − e) , (d − c) Correct Option: D Explanation: A set X can be represented by an array x [n] as follows: x\left [ i \right ]=\begin {cases} 1 & \text{if } i \in X \\ 0 & otherwise \end{cases} Consider the following algorithm in which x, y and z are boolean arrays of size n. algorithm zzz (x [ ], y[ ], z [ ] ) { int i; for (i = 0 ; i< n; ++i) z[i] = (x[i] Ù ~y[i]) Ú (~x[i] Ù y[i]) } The set Z computed by the algorithm is 1. (X U Y) 2. (X \capY) 3. (X − Y) \cap (Y − X) 4. (X − Y) U (Y − X) Correct Option: D Explanation: \text{Here}\ z = (x \land y') \lor (x' \land y) The order of the following recurrence: T(n) = 2T([\sqrt{n}]) + 1 is 1. T (n) = \odot(log log n) 2. T (n) = \odot (log n) 3. T (n) = \odot (\sqrt{n}) 4. T (n) = \odot (n) Correct Option: A Explanation: Consider the following code written in a pass-by-reference language like FORTRAN and these statements about the code. S1: The compiler will generate code to allocate a temporary nameless cell, initialize it to 13, and pass the address of the cell swap S2: On execution the code will generate a runtime error on line L1 S3: On execution the code will generate a runtime error on line L2 S4: The program will print 13 and 8 S5: The program will print 13 and - 2 Exactly the following set of statement(s) is correct: 1. S1 and S2 2. S1 and S4 3. S3 4. S1 and S5 Correct Option: B Explanation: A CPU generates 32-bit virtual addresses. The page size is 4 KB. The processor has a translation look-aside buffer (TLB) which can hold a total of 128 page table entries and is 4-way set associative. The minimum size of the TLB tag is: 1. 11 bits 2. 13 bits 3. 10 bits 4. 20 bits Correct Option: A Explanation: Consider the following C code segment. for (i - 0, i<n; i++) { for (j=0; j<n; j++) { if (i%2) { x += (4* j + 5* i); y += (7 + 4*j); } } } Which one of the following is false? 1. The code contains loop invariant computation 2. There is scope of common sub-expression elimination in this code 3. There is scope of strength reduction in this code 4. There is scope of dead code elimination in this code Correct Option: D Explanation: All the statements are true except option (4) since there is no dead code to get eliminated Given two arrays of numbers a1,..........., an and b1,............, bn where each number is 0 or 1, the fastest algorithm to find the largest span (i, j ) such that ai + ai+1 + .........+ aj = bi + bi + 1 +...........+ bj or report that there is not such span, 1. Takes O (3n) and \Omega(2n) time if hashing is permitted 2. Takes O (n3) and \Omega (n2.5) time in the key comparison model 3. Takes \odot (n3) time and space 4. Takes O (\sqrt{n}) time only if the sum of the 2n elements is an even number Correct Option: C Explanation: Consider the following translation scheme. S\rightarrowER R\rightarrowE {print (''); R}\in E \rightarrowF + E {print ('+');} F F\rightarrow (S) | id {print (id.value);} Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '2 * 3 + 4', this translation scheme prints 1. 2 * 3 + 4 2. 2 * +3 4 3. 2 3 * 4 + 4. 2 3 4+* Correct Option: B Explanation: Input String 2*3 + 4 A computer system supports 32-bit virtual addresses as well as 32-bit physical addresses. Since the virtual address space is of the same size as the physical address space, the operating system designers decide to get rid of the virtual memory entirely. Which one of the following is true? 1. Efficient implementation of multi-user support is no longer possible 2. The processor cache organization can be made more efficient now 3. Hardware support for memory management is no longer needed 4. CPU scheduling can be made more efficient now Correct Option: C Explanation: Consider the circuit in the diagram. The \oplus operator represents Ex - OR. The D flip - flops are initialized to zeroes (cleared). The following data: 100110000 is supplied to the “data” terminal in nine clock cycles. After that the values of q2 q1 q0 are: 1. 000 2. 001 3. 010 4. 101 Correct Option: C Explanation: |||||| |---|---|---|---|---| | | q2| q1| q0| I/P| | initially | 0| 0| 0| -| || 0| 0| 1| 1| || 0| 1| 0| 0| || 1| 0| 0| 0| || 0| 0| 0| 1| || 0| 0| 1| 1| || 0| 1| 0| 0| || 1| 0| 0| 0| || 0| 0| 1| 0| || 0| 1| 0| 0| Consider three processes (process ids 0, 1, 2 respectively) with compute time bursts 2, 4 and 8 time units. All processes arrive at time zero. Consider the longest remaining time first (LRTF) scheduling algorithm. In LRTF ties are broken by giving priority to the process with the lowest process id. The average turn around time is 1. 13 units 2. 14 units 3. 15 units 4. 16 units Correct Option: A Explanation: Consider three processes, all arriving at time zero, with total execution time of 10, 20 and 30 units respectively. Each process spends the first 20% of execution time doing I/O, the next 70% of time doing computation and the last 10% of time doing I/O again. The operating system uses shortest remaining compute time first scheduling algorithm and schedules a new process either when the running process gets blocked on I/O or when the running process finishes its compute burst. Assume that all I/O operations can be overlapped as much as possible. For what percentage of time does the CPU remain idle? 1. 0% 2. 10.6% 3. 30.0% 4. 89.4% Correct Option: B Explanation: Consider the following grammar: S \rightarrowFR R\rightarrow* S|\in F\rightarrowid In the predictive parser table, M, of the grammar the entries M [S, id] and M [R,] respectively. 1. {S \rightarrow FR} and {R \rightarrow \in } 2. {S \rightarrowFR} and { } 3. {S \rightarrowFR} and {R \rightarrow *S} 4. {F \rightarrow id} and {R \rightarrow \in } Correct Option: A Explanation: The atomic fetch-and-set x, y instruction unconditionally sets the memory location x to 1 and fetches the old value of x n y without allowing any intervening access to the memory location x. consider the following implementation of P and V functions on a binary semaphore S. void P (binary_semaphore *s) { unsigned y; unsigned *x = &(s->value); do { fetch-and-set x, y; } while (y); } void V (binary_semaphore *s) { S ->value = 0; } Which one of the following is true? ( Which one of the following is true? 1. The implementation may not work if context switching is disabled in P 2. Instead of using fetch-and -set, a pair of normal load/store can be used 3. The implementation of V is wrong 4. The code does not implement a binary semaphore Correct Option: A Explanation: If there are more than two processes and context & switching processes is disabled in P then this implementation doesn't work properly and can't synchronize the processes. The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n \ge 6 . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertices of degree zero in G is: 1. 1 2. n 3. n + 1 4. 2n Correct Option: C Explanation: The vertices of degree zero will be those subsets which do not have two elements common with any other subsets. This is true only for the subsets of cardinality 0 and 1. Number of sets with cardinality 1 = n \thereforeNumber of vertices of degree 0 = n + 1 The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n \ge 6 . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in G is: 1. n 2. n + 2 3. 2n/2 4. \dfrac{2^n}{n} Correct Option: B Explanation: null Consider the following snapshot of a system running n processes. Process i is holding xi instances of a resource R, 1\le i\le n. currently, all instances of R are occupied. Further, for all i, process i has placed a request for an additional yi instances while holding the xi instances it already has. There are exactly two processes p and q such that 0. yp = yq = 0. Which one of the following can serve as a necessary condition to guarantee that the system is not approaching a deadlock? 1. min (xp, xq) < max_{k \neq p, q}yk 2. xp + xq \ge$$max_{k \neq p, q}$. yk

3. max (xp, xq) > 1

4. min(xp, xq) > 1

Correct Option: B
Explanation: Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.

void barrier (void) {
1: P(S);
2: process_arrived++;

1. V(S); 4: while (process_arrived !=3); 5: P(S); 6: process_left++; 7: if (process_left==3) { 8: process_arrived = 0; 9: process_left = 0; 10: } 11: V(S); }

The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.

Which one of the following rectifies the problem in the implementation?

1. Lines 6 to 10 are simply replaced by process_arrived--

2. At the beginning of the barrier the first process to enter the barrier waits until process_arrived becomes zero before proceeding to execute P(S).

3. Context switch is disabled at the beginning of the barrier and re-enabled at the end.

Correct Option: B
Explanation: The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n $ge$ 6 . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

The maximum degree of a vertex in G is:

1. $\binom{n/2}{2}2^{n/2}$

2. 2n −2

3. 2n−3 × 3

4. 2n-1

Correct Option: B
Explanation:

A little observation of the adjacent vertices of different subsets reveals that the maximum degree will be
possessed by a subset of size $\dfrac{n}{2}$.
Suppose an example to compute the maximum degree.
Set is {1,2,3,4,5,6}
We have a subset of size $\dfrac{n}{2}${1,2,3}
Now let us compute its degree
The number of adjacent subsets of size
2 = 3C2 = 3
For each one of {1,2} {2,3} and {1,3}
There are 3 subsets of size 3 which are adjacent to {1,2, 3}
e.g       {1,2,4}, {1,2,5}, {1,2,6}
{2,3,4} {2,3,5} {2,3,6}
In this way, for each of {1,2}, {2,3} and {1,3} there are 3C2 subsets of size 5 for each of the three.
The set itself would not be adjacent to {1,2,3}
$\therefore$The maximum Degree = 3 + 3 x 3 + 3 x 3 + 3 = 24
$\therefore \binom{n/2}{2}2^{n/2}$= 3C2 23 = 3 x 8 = 24

Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.

void barrier (void) {
1: P(S);
2: process_arrived++;

1. V(S); 4: while (process_arrived !=3); 5: P(S); 6: process_left++; 7: if (process_left==3) { 8: process_arrived = 0; 9: process_left = 0; 10: } 11: V(S); }

The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.

The above implementation of barrier is incorrect. Which one of the following is true?

1. The barrier implementation is wrong due to the use of binary semaphore S

2. The barrier implementation may lead to a deadlock if two barrier in invocations are used in immediate succession.

3. Lines 6 to 10 need not be inside a critical section

4. The barrier implementation is correct if there are only two processes instead of three.

Correct Option: B
Explanation: In the correct grammar above, what is the length of the derivation (number of steps starring from S) to generate the string al bm with l $\ne$ m?

1. max (l, m) + 2

2. l + m + 2

3. l + m + 3

4. max (l, m) + 3

Correct Option: A
Explanation:

It is very clear the previous solution that the no. of steps required Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a spanning tree. First, the root bridge is identified as the bridge with the least serial number. Next, the root sends out (one or more) data units to enable the setting up of the spanning tree of shortest paths from the root bridge to each bridge. Each bridge identifies a port (the root port) through which it will forward frames to the root bridge. Port conflicts are always resolved in favour of the port with the lower index value. When there is a possibility of multiple bridges forwarding to the same LAN (but not through the root port), ties are broken as follows: bridges closest to the root get preference and between such bridges, the one with the lowest serial number is preferred. Consider the correct spanning tree for the previous question. Let host H1 send out a broadcast ping packet. Which of the following options represents the correct forwarding table on B3?

1. 2. 3. 4. Correct Option: A
Explanation: Which one of the following grammars generates the language $L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$?

1. $S\rightarrow AC\mid CB$

$C\rightarrow aCb\mid a\mid b$

$A\rightarrow aA\mid \varepsilon$

$B\rightarrow Bb\mid \varepsilon$

2. $S\rightarrow aS\mid Sb \mid a\mid b$

3. $S\rightarrow AC\mid CB$

$C\rightarrow aCb\mid \varepsilon$

$A\rightarrow aA\mid \varepsilon$

$B\rightarrow Bb\mid \varepsilon$

4. $S\rightarrow AC\mid CB$

$C\rightarrow aCb\mid \varepsilon$

$A\rightarrow aA\mid a$

$B\rightarrow Bb\mid b$

Correct Option: D
Explanation: Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a spanning tree. First, the root bridge is identified as the bridge with the least serial number. Next, the root sends out (one or more) data units to enable the setting up of the spanning tree of shortest paths from the root bridge to each bridge. Each bridge identifies a port (the root port) through which it will forward frames to the root bridge. Port conflicts are always resolved in favour of the port with the lower index value. When there is a possibility of multiple bridges forwarding to the same LAN (but not through the root port), ties are broken as follows: bridges closest to the root get preference and between such bridges, the one with the lowest serial number is preferred. For the given connection of LANs by bridges, which one of the following choices represents the depth first traversal of the spanning tree of bridges?

1. B1, B5, B3, B4, B2

2. B1, B3, B5, B2, B4

3. B1, B5, B2, B3, B4

4. B1, B3, B4, B5, B2

Correct Option: C
Explanation: A CPU has a cache with block size 64 bytes. The main memory has k banks, each bank being c bytes wide. Consecutive c − byte chunks are mapped on consecutive banks with wrap-around. All the k banks can be accessed in parallel, but two accesses to the same bank must be serialized. A cache block access may involve multiple iterations of parallel bank accesses depending on the amount of data obtained by accessing all the k banks in parallel. Each iteration requires decoding the bank numbers to be accessed in parallel and this takes$\dfrac{k}{2}$ns .latency of one bank access is 80 ns. If c = 2 and k = 24, the latency of retrieving cache block starting at address zero from main memory is:

1. 92 ns

2. 104 ns

3. 172 ns

4. 184 ns

Correct Option: D
Explanation: Consider two cache organizations: The first one is 32 KB 2-way set associative with 32- byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-1 multiplexer has a latency of 0.6 ns while a k - bit comparator has a latency of k /10 ns. The hit latency of the set associative organization is h1 while that of the direct mapped one is h2.

The value of h1 is:

1. 2.4 ns

2. 2.3 ns

3. 1.8 ns

4. 1.7 ns

Correct Option: A
Explanation: A CPU has a five-stage pipeline and runs at 1 GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new instructions following a conditional branch until the branch outcome is known. A program executes 9 10 instructions out of which 20% are conditional branches. If each instruction takes one cycle to complete on average, the total execution time of the program is:

1. 1.0 second

2. 1.2 seconds

3. 1.4 seconds

4. 1.6 seconds

Correct Option: B
Explanation:  Consider a new instruction named branch-on-bit-set (mnemonic bbs). The instruction “bbs reg, pos, label” jumps to label if bit in position pos of register operand reg is one. A register is 32 bits wide and the bits are numbered 0 to 31, bit in position 0 being the least significant. Consider the following emulation of this instruction on a processor that does not have bbs implemented.
temp$\leftarrow$reg & mask
Branch to label if temp is non-zero.
The variable temp is a temporary register. For correct emulation, the variable mask must be generated by

1. mask $\leftarrow$ 0 ×l << pos

2. musk $\leftarrow$ 0 × ffffffff >> pos

3. mask $\leftarrow$pos

4. masdk $\leftarrow$0×f

Correct Option: A
Explanation: Consider two cache organizations: The first one is 32 KB 2-way set associative with 32- byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-1 multiplexer has a latency of 0.6 ns while a k - bit comparator has a latency of k /10 ns. The hit latency of the set associative organization is h1 while that of the direct mapped one is h2.

The value of h2 is:

1. 2.4 ns

2. 2.3 ns

3. 1.8 ns

4. 1.7 ns

Correct Option: B
Explanation: A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a two dimensional
array of size 512×512 with elements that occupy 8-bytes each. Consider the
following two C code segments, P1 and P2.
P1: for (i=0; i<512; i++) {
for (j=0; j<512; j++) {
x +=A[i] [j];
}
}
P2: for (i=0; i<512; i++) {
for (j=0; j<512; j++) {
x +=A[j] [i];
}
}
P1 and P2 are executed independently with the same initial state, namely, the array A is
not in the cache and i, j, x are in registers. Let the number of cache misses experienced
by P1 be M1 and that for P2 be M2 .

The value of the ratio $\dfrac{M_1}{M_2}$

1. 0

2. $\dfrac{1}{16}$

3. $\dfrac{1}{8}$

4. 16

Correct Option: B
Explanation:  A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a two dimensional
array of size 512×512 with elements that occupy 8-bytes each. Consider the
following two C code segments, P1 and P2.
P1: for (i=0; i<512; i++) {
for (j=0; j<512; j++) {
x +=A[i] [j];
}
}
P2: for (i=0; i<512; i++) {
for (j=0; j<512; j++) {
x +=A[j] [i];
}
}
P1 and P2 are executed independently with the same initial state, namely, the array A is
not in the cache and i, j, x are in registers. Let the number of cache misses experienced
by P1 be M1 and that for P2 be M2 .

The value of 1 M is:

1. 0

2. 2048

3. 16384

4. 262144

Correct Option: C
Explanation: Consider these two functions and two statements S1 and S2 about them. S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1

1. S1 is false and S2 is false

2. S1 is false and S2 is true

3. S1 is true and S2 is false

4. S1 is true and S2 is true

Correct Option: D
Explanation:  Consider the following C-function in which a [n] and b [m] are two sorted integer
arrays and c [n + m ] be another integer array.

void xyz (int a[ ], int b [ ], int c [ ]) {
int i, j, k;
i=j=k=0;
while ((i &lt; n) &amp;&amp; (j &lt; m))
if (a[i] &lt; b[j]) c[k++] = a[i++];
else c[k++] = b[j++];
}


Which of the following condition(s) hold(s) after the termination of the while loop?

1. only (i)

2. only (ii)

3. either (i) or (ii) but not both

4. neither (i) nor (ii)

Correct Option: C
Explanation: A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a, nodes in the next level, from left to right, is stored from a to a. The nodes from the second level of the tree from left to right are stored from alocation onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?

1. 1, 3, 5, 6, 8, 9

2. 9, 6, 3, 1, 8, 5

3. 9, 3, 6, 8, 5, 1

4. 9, 5, 6, 8, 3, 1

Correct Option: D
Explanation: the all its children

Consider this C code to swap two integers and these five statements: the code. S1: will generate a compilation error
S2: may generate a segmentation fault at runtime depending on the arguments passed
S3: correctly implements the swap procedure for all input pointers referring to integers stored in
memory locations accessible to the process
S4: implements the swap procedure correctly for some but not all valid input pointers
S5: may add or subtract integers and pointers.

1. S1

2. S2 and S3

3. S2 and S4

4. S2 and S5

Correct Option: C
Explanation: A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a, nodes in the next level, from left to right, is stored from a to a. The nodes from the second level of the tree from left to right are stored from alocation onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question, Q.76. Which one of the following is the sequence of items in the array representing the resultant heap?

1. 10, 7, 9, 8, 3, 1, 5, 2, 6, 4

2. 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

3. 10, 9, 4, 5, 7, 6, 8, 2, 1, 3

4. 10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Correct Option: A
Explanation:  An implementation of a queue Q, using two stacks S1 and S2, is given below:
void insert (Q, x) {
push (S1, x);
}
void delete (Q) {
if (stack-empty(S2)) then
if (stack-empty(S1)) then {
print(“Q is empty”);
return;
}
else while (!(stack-empty(S1))){
x=pop (S1);
push (S2,x);
}
x=pop (S2);
}
Let n insert and m ($\le$ n) delete operations be performed in an arbitrary order on an empty queue Q. Let
x and y be the number of push and pop operations performed respectively in the process. Which one of
the following is true for all m and n?

1. n + m $\le$ x < 2n and 2m $\le$ y $\le$ n + m

2. n + m $\le$ x < 2n and 2m $\le$ y $\le$ 2n

3. 2m $\le$ x < 2n and 2m $\le$ y $\le$ n + m

4. 2m $\le$ x < 2n and 2m $\le$ y $\le$ 2n

Correct Option: A
Explanation:

The order in which insert and delete operations are performed matters here.
The best case: Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push operations are performed. So, total m+ n push (n push for insert() and m push for delete()) operations and 2m pop operations are performed.
The worst case: First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations and n push operation are performed. Other than first, in all delete operations, 1 pop operation is performed. So, total m + n pop operations and 2n push operations are performed (n push for insert() and n push for delete())

Consider the relation account (customer, balance) where customer is a primary key and there are no null values. We would like to rank customers according to decreasing balance. The customer with the largest balance gets rank 1. Ties are not broken but ranks are skipped: if exactly two customers have the largest balance they each get rank 1 and rank 2 is not assigned. Consider these statements about Query 1 and Query 2.

1. Query 1 will produce the same row set as Query 2 for some but not all databases.
2. Both Query 1 and Query 2 are correct implementation of the specification.
3. Query 1 is a correct implementation of the specification but Query 2 is not.
4. Neither Query 1 nor Query 2 is a correct implementation of the specification.
5. Assigning rank with a pure relational query takes less time than scanning in decreasing balance order assigning ranks using ODBC.

Which two of the above statements are correct?

1. 2 and 5

2. 1 and 3

3. 1 and 4

4. 3 and 5

Correct Option: C
Explanation:  Consider the following log sequence of two transactions on a bank account, with initial balance of Rs. 12,000, that transfers 2000 to a mortgage payment and then applies a 5% interest.

1. T1 start
2. T1 B old = 1200 new = 10000
3. T1 M old = 0 new = 2000
4. T1 commit
5. T2 start
6. T2 B old = 10000 new = 10500
7. T2 commit

Suppose the database system crashes just before log record 7 is written. When the system is restarted, which statement is true for the recovery procedure?

1. We must redo log record 6 to set B to 10500.

2. We must undo log record 6 to set B to 10000 and then redo log records 2 and 3.

3. We need not redo log records 2 and 3 because transaction T1 has committed.

4. We can apply redo and undo operations in arbitrary order because they are idempotent.

Correct Option: C
Explanation: Consider the following functional dependencies:
AB$\rightarrow$CD, AF $\rightarrow$ D,DE $\rightarrow$F,C $\rightarrow$G, F $\rightarrow$E,G $\rightarrow$A.
Which one of the following options is false?

1. {CF}* = {ACDEFG}

2. {BG}* = {ABCDG}

3. {AF}* = {ACDEFG}

4. {AB}* = {ABCDFG

Correct Option: C
Explanation: Consider the relation enrolled (student, course) in which (student, course) is the primary key, and the relation paid (student, amount) where student is the primary key.
Assume no null values and no foreign keys or integrity constraints. Given the following four queries:
Query1:select student from enrolled where student in (select student from paid)
Query2:select student from paid where student in (select student from enrolled)
Query3:select E.student from enrolled E, paid P where E.student = P.student
Query4:select student from paid where exists (select * from enrolled where enrolled. student = paid. student)
Which one of the above statements is correct?

1. All queries return identical row sets for any database.

2. Query2 and Query4 return identical row sets for all databases but there exist databases for which Query1 and Query2 return different row sets.

3. There exist databases for which Query3 returns strictly fewer rows than Query 2.

4. There exist databases for which Query4 will encounter an integrity violation at runtime.

Correct Option: B
Explanation:  Consider the relation enrolled (student, course) in which (student, course) is the primary key, and the relation paid (student, amount) where student is the primary key. Assume no null values and no foreign keys or integrity constraints. Assume that amounts 6000, 7000, 8000, 9000 and 10000 were each paid by 20% of the students. Consider these query plans (Plan 1 on left, Plan 2 on right) to “list all courses taken by students who have paid more than x” A disk seek takes 4ms, disk data transfer bandwidth is 300 MB/s and checking a tuple to see if amount is greater than x takes 10Zs. Which of the following statements is correct?

1. Plan 1 and Plan 2 will not output identical row sets for all databases

2. A course may be listed more than once in the output of Plan 1 for some databases

3. For x = 5000, Plan 1 executes faster than Plan 2 for all databases

4. For x = 9000, Plan I executes slower than Plan 2 for all databases.

Correct Option: C
Explanation: Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

1. R is NP-complete

2. R is NP-hard

3. Q is NP-complete

4. Q is NP-hard

Correct Option: A
Explanation: Let SHAM, be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with V divisible by 3 and DHAM' be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

1. Both DHAM, and SHAM, are NP-hard

2. SHAM, is NP-hard, but DHAM, is not

3. DHAM, is NP-hard, but SHAM, is not

4. Neither DHAM, nor SHAM, is NP-hard

Correct Option: A

Let L1 = {0n+m1n0m|n, m$\ge$0}. L2 = {0n+m1n+m0m|n, m$\ge$0} and L3 = {0n+m1n+m0n+m|n, m$\ge$0} Which of these languages are NOT context free?

1. L1 only

2. L2 only

3. L1 and L2

4. L2 and L3

Correct Option: D
Explanation: For S $\in$ (0 + 1) * let d (s) denote the decimal value of s (e.g. d (101) = 5).
Let L = {s $\in$ (0 + 1)* d (s)mod 5 = 2 and d (s) mod 7 $\ne$ 4}
Which one of the following statements is true?

1. L is recursively enumerable, but not recursive

2. L is recursive, but not context-free

3. L is context-free, but not regular

4. L is regular

Correct Option: D
Explanation:  Consider the regular language L = (111 + 11111) *. The minimum number of states in any DFA accepting these languages is:

1. 3

2. 5

3. 8

4. 9

Correct Option: D
Explanation:  If s is a string over (0 + 1)* then let n0 (s) denote the number of 0's in s and n1 (s) the number of 1's in s. Which one of the following languages is not regular?

1. L = {s $\in$(0 + 1)*| n0 (s) is a 3-digit prime}

2. L = {s $\in$(0 + 1)*| for every prefix s' of s1 |n0 (s') - n1 (s')| $\le$2 |

3. L = {s $\in$(0 + 1)*| n0 (s') - n1 (s')| $\le$4 |

4. L = {s $\in$(0 + 1)*| n0 (s) mod 7 = n1 (s) mod 5 = 0}

Correct Option: C
Explanation: Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?

1. L1 $\cap$ L is a deterministic CFL

2. L3 $\cap$ L1 is recursive

3. L1 U L2 is context free

4. L1 $\cap$ L2 $\cap$ L3 is recursively enumerable

Correct Option: B
Explanation: Consider the following statements about the context free grammar
G = {S $\rightarrow$ SS, S $\rightarrow$ ab, S $\rightarrow$ ba, S $\rightarrow$$\in$}
I. G is ambiguous
II. G produces all strings with equal number of a's and b's
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?

1. I only

2. I and III only

3. II and III only

4. I, II and III

Correct Option: B
Explanation:  + View questions