GATE 2017 Solved Paper CS: Set – 2 | xlv

Question Number: 42 Question Type: MCQ if (array[i] < array[i+1]) {

swap(&array[i], &array[i + 1]) ;
The next state table of a 2-bit saturating up-counter is given
done = 0;
below.
}
Q1 Q0 Q1+ Q0+ }
for (i=5; i >=l; i--) {
0 0 0 1 if (array[i] > array[i−l]) {
0 1 1 0 swap(&array[i], & array[i−1]);
1 0 1 1 done = 0;
1 1 1 1 }
}
The counter is built as a synchronous sequential circuit }
using T flip-flops. The expressions for T1 and T0are printf{“%d”, array[3]);
}
(A) T1 = Q1Q0, T0 = Q1 Q 0
The output of the program is ________.
(B) T1 = Q1Q0, T0 = Q1 + Q 0 Solution: The above code sorts the elements in the de-
creasing order. The output array after the code execution is
(C) T1 = Q1 + Q0, T0 = Q1 + Q 0
0 1 2 3 4 5
(D) T1 = Q1Q0, T0 = Q1 + Q0 6 5 4 3 2 1
Solution:
So, array [3] contains an element ‘3’, so, it outputs 3.
Q1 Q0 Q1+ Q0+ T1 T0
Hence, the correct answer is (3).
0 0 0 1 0 1
Question Number: 44 Question Type: NAT
0 1 1 0 1 1
Two transactions T1 and T2 are given as
1 0 1 1 0 1
T1 : r1(X)w1 (X)r1 (Y)w1 (Y)
1 1 1 1 0 0
T2 : r2 (Y)w2 (Y)r2 (Z)w2 (Z)
By observation, T1 = Q1 Q0 where ri (V) denotes a read operation by transaction Ti on a
K’ map for T0 variable V and wi (V) denotes a write operation by transac-
tion Ti on a variable V. The total number of conflict serializ-
Q0
0 1 able schedules that can be formed by T1 and T2 is _______.
Q1
Solution: Number of conflict serializable schedules pos-
0 sible such that T1 is depend on T2 is 1. Number of conflict
1 1
serislizable schedules possible such that T2 is depend on T1
is 53.
1 1 0 ∴ Total possible conflict serializable schedules is 54
Hence, the correct answer is (54).
Question Number: 45 Question Type: NAT
T0 = Q1 + Q0
The read access times and the hit ratios for different caches
T1 = Q1 Q0 , T0 = Q1 + Q0 in a memory hierarchy are as given below.
Hence, the correct option is (B).
Cache Read access time Hit ratio
Question Number: 43 Question Type: NAT (in nanoseconds)
Consider the following snippet of a C program. Assume that I-cache 2 0.8
swap (&x, &y) exchanges the contents of x and y. D-cache 2 0.9
L2-cache 8 0.9
int main () {
int array[] = {3, 5, 1, 4, 6, 2};
The read access time of main memory is 90 nanoseconds.
int done = 0;
Assume that the caches use the referred- word-first read pol-
int i;
icy and the write back policy. Assume that all the caches are
while (done == 0) {
direct mapped caches. Assume that the dirty bit is always 0
done = 1;
for all the blocks in the caches. In execution of a program.
for (i=0; i <=4; i++) {
xlvi | GATE 2017 Solved Paper CS: Set – 2

60% of memory reads are for instruction fetch and 40% are AND ta.goals >ANY (SELECT tc.goals
for memory operand fetch. The average read access time in FROM top_scorer AS tc
nanoseconds (up to 2 decimal places) is __________. WHERE tc. country = ‘Germany’)
The number of tuples returned by the above SQL query is
Solution: Given there are 60% instruction fetch, 40% op- _________.
erand fetch.
Solution: Select tb. goals FROM top-scorer AS tb where
For instruction fetch, average memory access time tb. ‘country’ = Spain
= 0.6 [HI * RI + (1 − HI) HL (RI + RL ) + (1 − HI) (1 − HL ) This query returns zero tuples as no country has name
2 2 2
(RI + RL + Rm)] ‘Spain’.
2
= 0.6[0.8 * 2 + (1−0.8) 0.9 (2 + 8) + (1 − 0.8) (1 − 0.9) (2 TC table has below rows:
+ 8 + 90)] tc
= 0.6[1.6 + 1.8 + 2]
tc. goals
= 3.24 ns 16
For operand fetch, 14
Average memory access time 11

= 0.4[HD * RD + (1 − HD) HL (RD + RL ) + (1 − HD) (1 − HL ) 10

2 2 2
(RD + RL + Rm)] ta consists the player name whose goals is > ANY (tc.goals)
2
= 0.4[0.9 * 2 + 0.1 * 0.9 * (2 + 8) + 0.1 * 0.1 * (2 + 8 + 90)] ta
= 0.4 [1.8 + 0.9 + 1] ta.player
= 3.7 * 0.4 = 1.48 ns Klose (∵ 16 >15)
∴ Average memory access time = 3.24 + 1.48 = 4.72
Ronaldo (∵ 15 >14)
Hence, the correct answer is (4.72).
G muller (∵ 14 >11)
Question Number: 46 Question Type: NAT Foundtaine (∵ 13 >10)
Consider the following database table named top_scorer.
Pele (∵ 12 >10)
top_scorer Klinsmann (∵ 11 >10)
player country goals
Kocsis (∵ 11 >10)
Klose Germany 16
Ronaldo Brazil 15
∴ 7 rows returned by given query.
G Miiller Germany 14
Hence, the correct answer is (7).
Fontaine France 13
Pelé Brazil 12
Question Number: 47 Question Type: NAT
Klinsmann Germany 11 If the ordinary generating function of a sequence
Kocsis Hungary 11 ∞ 1+ z
{an }n=0 is 3
then a3 −a0 is equal to __________.
Batistuta Argentina 10 (1− z )
Cubillas Peru 10
Solution: Given, the generating function of a sequence
Lato Poland 10 ∞
{an }n=0 is
Lineker England 10
T Muller Germany 10 1+ z 1
= 3
= (1 + z ) 3
Rahn Germany 10 (1− z ) (1− z )
∞ 
Consider the following SQL query: = (1 + z )∑ C (3 −1 + r , r ) z r 
 r =0 
SELECT ta.player FROM top_scorer AS ta
WHERE ta.goals >ALL (SELECT tb.goals  1 ∞ 

 (1− X ) n = ∑ C (n −1 + r , r ) X r 
FROM top_scorer AS tb r =0 
WHERE tb.country = ‘Spain’)