# CS GATE 2017 PAPER 01 (Test 4)

Tag: cs gate 2017 paper 01
Q.1
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:
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 ?
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
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.

Workspace
Report
Q.2
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:
(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?
A. (I) only
B. (II) only
C. Both (I) and (II)
D. Neither (I) nor (II)
Explaination / Solution:

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

Workspace
Report
Q.3
When two 8-bit numbers A7....A0 and B7.....B0 in 2’s complement representation (with A0 and B0 as the least significant bits ) are added using a ripple-carry adder, the sum bits obtained are S7….S0 and the carry bits are C7….C0. An overflow is said to have occurred if
A. the carry bit C7 is 1
B. all the carry bits (C7….C0) are 1
C.
D.
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
Q.4
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.
Initially, both Qand Q1 are set to 1 ( before the 1st clock cycle). The outputs

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
Explaination / Solution:

Workspace
Report
Q.5
Let c1 ........cn be scalars, not all zero, such that  where ai are column vectors in Rn . Consider the set of linear equations Ax = b where A = [a1 ........an] 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
Explaination / Solution:

Since the scalars are not all zero
∴ The column vectors ai for i = 1,2...,n are linearly dependent

Workspace
Report
Q.6
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 2i
B. 2-t to (2i - 2-t)
C. 0 to 2i
D. 0 to (2i-2-t)
Explaination / Solution:

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

Workspace
Report
Q.7
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?
I. ∃y (∃xR(x,y))                II. ∃y (∀xR(x,y))
III. ∀y (∃xR(x,y))              IV. ¬∃x (∀y¬R(x,y))
A. IV only
B. I and IV only
C. II only
D. II and III only
Explaination / Solution:

Workspace
Report
Q.8
Consider the following functions from positive integers to real numbers:
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
A.
B.
C.
D.
Explaination / Solution:
No Explaination.

Workspace
Report
Q.9
The value of
A. is 0
B. is -1
C. is 1
D. does not exist
Explaination / Solution:

Workspace
Report
Q.10
Let u and v be two vectors in R2 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