Recall that Belady’s anomaly is that the pages-fault rate may increase as the number of
allocated frames increases. Now consider the following statements:

**A. ** S1 is true, S2 is true

**B. ** S1 is true, S2 is false

**C. ** S1 is false , S2 is true

**D. ** S1 is false, S2 is false

**Answer : ****Option B**

**Explaination / Solution: **

Statement 1 is “TRUE”. Because there can be a case when page selected to be replaced is by FIFO policy. Statement 2 is “FALSE”. Because LRU page replacement algorithm does not suffers from Belady’s Anomaly. Only FIFO page replacement algorithm suffers from Belady’s Anomaly.

S1: Random page replacement algorithm (where a page chosen at random is replaced)
suffers from Belady’s anomaly

S2: LRU page replacement algorithm suffers from Belady’s anomaly

Which of the following is CORRECT ?

Statement 1 is “TRUE”. Because there can be a case when page selected to be replaced is by FIFO policy. Statement 2 is “FALSE”. Because LRU page replacement algorithm does not suffers from Belady’s Anomaly. Only FIFO page replacement algorithm suffers from Belady’s Anomaly.

Workspace

Report

Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in
E are positive and distinct. Consider the following statements: **A. ** (I) only

**B. ** (II) only

**C. ** Both (I) and (II)

**D. ** Neither (I) nor (II)

**Answer : ****Option A**

**Explaination / Solution: **

(I) Minimum spanning tree of G is always unique.

(II) Shortest path between any two vertices of G is always unique.

Which of the above statements is/are necessarily true?

Shortest path from B to C are two B-A-C and B-C both of weight '3'

Workspace

Report

When two 8-bit numbers A_{7}....A_{0} and B_{7}.....B_{0} in 2’s complement representation (with A_{0} and B_{0} as the least significant bits ) are added using a ripple-carry adder, the sum bits
obtained are S_{7}….S_{0} and the carry bits are C_{7}….C_{0}. An overflow is said to have occurred if

**A. ** the carry bit C_{7} is 1

**B. ** all the carry bits (C_{7}….C_{0}) are 1

**C. **

**D. **

**Answer : ****Option C**

**Explaination / Solution: **

Overflow flag indicates an over flow condition for a signed operation. Some points to

remember in a signed operation:

* MSB is always reserved to indicate sign of the number.

* Negative numbers are represented in 2’s – complement.

* An overflow results in invalid operation.

2's complement overflow rules:

* If the sum of two positive numbers yields a negative result, the sum has- overflowed.

* If the sum of two negative number yields a positive result, the sum has overflowed.

* Otherwise, the sum has not overflowed.

Overflow for signed numbers occurs when the carry-in into the MSB (most significant bit) is

not equal to carry-out. Conveniently, an XOR-operation on these two bits can quickly

determine if an overflow condition exists.

Workspace

Report

Consider a combination of T and D flip-flops connected as shown below. The output of the D flip-flops is connected to the input of the T flip-flop and the output of the T Flip-flop connected to the input of the D Flip-flop.

**A. ** Q1Q0 after the 3rd cycle are 11 and after the 4th cycle are 00 respectively

**B. ** Q1Q0 after the 3rd cycle are 11 and after the 4th cycle are 01 respectively

**C. ** Q1Q0 after the 3rd cycle are 00 and after the 4th cycle are 11 respectively

**D. ** Q1Q0 after the 3rd cycle are 01 and after the 4th cycle are 01 respectively

**Answer : ****Option B**

**Explaination / Solution: **

Initially, both Q_{0 }and Q_{1} are set to 1 ( before the 1^{st} clock cycle). The outputs

Workspace

Report

Let c_{1} ........c_{n} be scalars, not all zero, such that where a_{i} are column vectors in
R_{n} . Consider the set of linear equations Ax = b where A = [a_{1} ........a_{n}] and The set of equations has

**A. ** a unique solution at x = Jn where Jn denotes a n-dimensional vector of all 1

**B. ** no solution

**C. ** infinitely many solutions

**D. ** finitely many solutions

**Answer : ****Option C**

**Explaination / Solution: **

Since the scalars are not all zero

Since the scalars are not all zero

∴ The column vectors a_{i} for i = 1,2...,n are linearly dependent

Workspace

Report

The n-bit fixed-point representation of an unsigned real number real X uses f bits for the
fraction part. Let i = n –f. The range of decimal values for X in this representation is

**A. ** 2^{-t} to 2^{i}

**B. ** 2-t to (2^{i} - 2^{-t})
**C. ** 0 to 2i
**D. ** 0 to (2i-2-t)
**Answer : ****Option D**

**Explaination / Solution: **

i = n – f . f

i = n – f . f

Max value = 111.....1 (i times).111........1 (f times)

Workspace

Report

Consider the first-order logic sentence F: ∀z (∃yR(x,y)). Assuming non-empty logical
domains, which of the sentences below are implied by F?

**A. ** IV only

**B. ** I and IV only

**C. ** II only

**D. ** II and III only

**Answer : ****Option B**

**Explaination / Solution: **

I. ∃y (∃xR(x,y)) II. ∃y (∀xR(x,y))

III. ∀y (∃xR(x,y)) IV. ¬∃x (∀y¬R(x,y))

Workspace

Report

Consider the following functions from positive integers to real numbers:

**A. **

**B. **

**C. **

**D. **

**Answer : ****Option B**

**Explaination / Solution: **

No Explaination.

The CORRECT arrangement of the above functions in increasing order of asymptotic
complexity is:

No Explaination.

Workspace

Report

The value of

**A. ** is 0

**B. ** is -1

**C. ** is 1

**D. ** does not exist

**Answer : ****Option C**

**Explaination / Solution: **

Workspace

Report

Let u and v be two vectors in R_{2} whose Euclidean norms satisfy ||u|| = 2 ||v||. What is the value
of α such that w = u + αv bisects the angle between u and v ?

**A. ** 2

**B. ** 1/2

**C. ** 1

**D. ** -1/2

**Answer : ****Option A**

**Explaination / Solution: **

Workspace

Report