# GATE Solved Paper 2017-19 - GATE 2018

• Option : B
• Explanation :
I {ambncpdq | m + p = n + q} is clearly CFL since, we can rearrange the equation as m - n + p - q = 0 which can be done by push, pop, and pop and check if stack is empty at end.
II {ambncpdq | m = n and p = q} is clearly CFL since, one comparison at a time can be done by pda
III {ambncpdq | m = n = p and p ≠ q} is not CFL since m = n = p is a double comparison which cannot be done by PDA.
IV {ambncpdq | mn = p + q} is not a CFL, since mn involves multiplying number of a’s and number b’s which cannot be done by a PDA.
So, only I and II are CFL’s.

• Option : B
• Explanation :
// n takes 2^40
unsigned long int fun(unsigned long int n) {
// initialized sum = 0
unsigned long int i, j, sum = 0;
//First it takes i = n = 2^40,
//then it divides i by 2 and incremented once j
//each time, that's will make makes j = 40,
for( i=n; i>1; i=i/2) j++;
//Now the value of j = 40,
//it divides j by 2 and incremented once sum
//each time, that's will make makes sum = 5,
for( ; j>1; j=j/2) sum++;
//returns sum = 5
return sum;
}

• Option : C
• Explanation :

Given query: r ⋈ ( σB<5(s))  A B C a1 2 c1 a2 4 c1 a3 4 c1

A: σB<5(r ⋈ s) A B C a1 2 c1 a2 4 c1 a3 4 c1

B:  σB<5(r ⋈ s) A B C a1 2 c1 a2 4 c1 a3 4 c1

C: r ⋈ (σB<5(s)) A B C a1 2 c1 a2 4 c1 a3 4 c1 a4 6 Null a5 6 Null

D: σ;B<5 (r) ⋈  s A B C a1 2 c1 a2 4 c1 a3 4 c1

Option “C” query result not equal to given query.

 Allocation Max E F G E F G P0 1 0 1 P0 4 3 1 P1 1 1 2 P1 2 1 4 P2 1 0 3 P2 1 3 3 P3 2 0 0 P3 5 4 1
From the perspective of deadlock avoidance, which one of the following is true?

• Option : A
• Explanation :  Max need Current allocation Current available Remaining need E F G E F G E(3) F(3) G(0) E F G P0 4 3 1 1 0 1 4 3 1 3 3 0 P1 2 1 4 1 1 2 5 3 4 1 0 2 P2 1 3 3 1 0 3 6 4 6 0 3 0 P3 5 4 1 2 0 0 8 4 6 3 4 1

Safe sequence : P0, P2, P1, P3
Safe state

• Option : C
• Explanation :
Total number of scalar multiplications are 48 + 75 + 50 + 2000 = 2173 and optimal parenthesis is ((F1(F2(F3 F4))) F5). As concluded, F3, F4 are explicitly computed pairs.
Related Quiz.
GATE 2018