## GATE 2017 [Set-1]

Question 1 |

I. p ⇒ q

II. q ⇒ p

III. (¬q) ∨ p

IV. (¬p) ∨ q

I only | |

I and IV only | |

II only | |

II and III only |

Construct Truth tables:

~p ⇒ ~q

II, III are equivalent to (~p) ⇒ (~q)

Method 2:

(I) p⇒q ≡ ~p∨q

(II) q⇒p ≡ ~q∨p

(III) (~q) ∨ p ≡ ~q∨p

(IV) (~p) ∨ p ≡ ~p∨q

Also, from question:

(~p) ⇒ (~q)

≡ p∨~q

So, (II) & (III) are equivalent to the statement given in question.

Question 2 |

*implied*by F?

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

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

III. ∀y(∃xR(x,y))

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

IV only | |

I and IV only | |

II only | |

II and III only |

F: ∀x(∃yR(x,y)) (given)

: For all girls there exist a boyfriend

(x for girls and y for boys)

I: ∃y(∃xR(x,y))

: There exist some boys who have girlfriends.

(Subset of statement F, so True)

II: ∃y(∀xR(x,y))

: There exists some boys for which all the girls are girlfriend. (False)

III: ∀y(∃xR(x,y))

: For all boys exists a girlfriend. (False)

IV: ~∃x(∀y~R(x,y))

= ∀x(~∀y~R(x,y))

= ∀x(∃yR(x,y)) (∵ ~∀y=∃y, ~∃x=∀x)

(True)

Question 3 |

Let c^{1}, c^{n} be scalars not all zero. Such that the following expression holds:

where a_{i} is column vectors in R^{n}. Consider the set of linear equations.

where A = [a_{1}.......a_{n}] and

Then, Set of equations has

a unique solution at x = J _{n} where J_{n} denotes a n-dimensional vector of all 1 | |

no solution | |

infinitely many solutions | |

finitely many solutions |

_{i}is a column vector

AX = B

As given that

and c

_{1}&c

_{n}≠ 0

means c

_{0}a

_{0}+ c

_{1}a

_{1}+ ...c

_{n}a

_{n}= 0, represents that a

_{0}, a

_{1}... a

_{n}are linearly dependent.

So rank of 'A' = 0, (so if ‘B’ rank is = 0 infinite solution, ‘B’ rank>0 no solution) ⇾(1)

Another condition given here is, 'Σa

_{i}= b',

so for c

_{1}c

_{2}...c

_{n}= {1,1,...1} set, it is having value 'b',

so there exists a solution if AX = b →(2)

From (1)&(2), we can conclude that AX = B has infinitely many solutions.

Question 4 |

Consider the following functions from positives integers to real numbers

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

Step-1: Take n=2048 or 2

^{11}(Always take n is very big number)

Step-2: Divide functions into 2 ways

1. Polynomial functions

2. Exponential functions

Step-3: The above functions are belongs to polynomial. So, simply substitute the value of n,

First compare with constant values.

→ 100 / 2048 = 0.048828125

→ 10 > 100/ 2048

→ log

_{2}2048 =11

→ √n = 45.25483399593904156165403917471

→ n = 2048

So, Option B is correct

Question 5 |

Consider the following table

Match the algorithm to design paradigms they are based on:

(P)↔(ii), Q↔(iii), (R)↔(i) | |

(P)↔(iii), Q↔(i), (R)↔(ii) | |

(P)↔(ii), Q↔(i), (R)↔(iii) | |

(P)↔(i), Q↔(ii), (R)↔(iii) |

(Q) QuickSort is a Divide and Conquer algorithm.

(R) Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem using Dynamic Programming.

Some important points regarding Greedy Vs Dynamic Programming

Greedy: →

It always gives polynomial time complexity

→ It is not an optimal

→ It always selects only either minimum or maximum among all possibilities

→ Ex: Dijkstra’s algorithm for SSSP, Optimal Merge Pattern, Huffman coding, Fractional knapsack problem, etc..,

Dynamic Programming:

→ It gives either polynomial or exponential time complexity.

→ It gives always an optimal result.

→ It checks all possibilities of a problem.

→ Ex: Longest Common sequence, Matrix chain Multiplication, Travelling sales Problem, etc.

Question 6 |

Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:

*Note: The height of a tree with a single node is 0.*

4 and 15 respectively | |

3 and 14 respectively | |

4 and 14 respectively | |

3 and 15 respectively |

The height of a tree with single node is 0.

Minimum possible height is when it is a complete binary tree.

Maximum possible height is when it is a skewed tree left/right.

So the minimum and maximum possible heights of T are: 3 and 14 respectively.

Question 7 |

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

2 ^{-f} to 2^{i} | |

2 ^{-f} to (2^{i} - 2^{-f}) | |

0 to 2 ^{i} | |

0 to (2 ^{i} - 2^{-f }) |

Number of bits in fraction part → f-bits

Number of bits in integer part → (n – f) bits

Minimum value:

000…0.000…0 = 0

Maximum value:

= (2

^{ n-f }- 1) + (1 - 2

^{-f}

= (2

^{n-f}- 2

^{-f})

= (2

^{i}- 2

^{ -f })

Question 8 |

Consider the C code fragment given below.

typedef struct node { int data; node* next; } node; void join(node* m, node* n) { node* p = n; while(p→next !=NULL) { p = p→next; } p→next=m; }

Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will

append list m to the end of list n for all inputs. | |

either cause a null pointer dereference or append list m to the end of list n. | |

cause a null pointer dereference for all inputs. | |

append list n to the end of list m for all inputs. |

So have to consider both the cases.

⇾ 1. Lists are not null, invocation of JOIN will append list m to the end of list n.

m = 1, 2, 3

n = 4, 5, 6

After join, it becomes 4, 5, 6, 1, 2, 3, NULL.

⇾ 2. If lists are null, if the list n is empty, and itself NULL, then joining & referencing would obviously create a null pointer issue.

Hence, it may either cause a NULL pointer dereference or appends the list m to the end of list n.

Question 9 |

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

the carry bit C _{7} is 1 | |

all the carry bits (C _{7},…,C_{0}) are 1 | |

i.e., A

_{7}= B

_{7}

⇾ Overflow can be detected by checking carry into the sign bits (C

_{in}) and carry out of the sign bits (C

_{out}).

⇾ Overflow occurs iff A

_{7}= B

_{7}and C

_{in}≠ C

_{out}

These conditions are equivalent to

Consider

Here A

_{7}= B

_{7}= 1 and S

_{7}= 0

This happens only if C

_{in}= 0

Carry out C

_{out}=1 when

Similarly, in case of

C

_{in}=1 and C

_{out}will be 0.

Question 10 |

*S*as the start symbol:

S → abScT | abcT

T → bT | b

Which one of the following represents the language generated by the above grammar?

{(ab) ^{n} (cb)^{n}│n ≥ 1} | |

{(ab) ^{n} cb^{(m1 )} cb^{(m2 )}…cb^{(mn )}│n,m_{1},m_{2},…,m_{n} ≥ 1} | |

{(ab) ^{n} (cb^{m})^{n}│m,n ≥ 1} | |

{(ab) ^{n} (cb^{n})^{m}│m,n ≥ 1} |

S→ abScT | abcT, this production will generate equal number of “ab” and “c” and for every “abc” any number of b’s ( > 1) after “abc”.

For Ex:

Hence the language generated by the grammar is

L = {(ab)

^{n}cb

^{(m1 )}cb

^{(m2 )}…cb

^{(mn )}│n,m

_{1},m

_{2},…,m

_{n}≥ 1}

Question 11 |

Consider the C struct defined below:

struct data { int marks [100]; char grade; int cnumber; }; struct data student;

The base address of *student* is available in register **R1**. The field *student.grade* can be accessed efficiently using

Post-increment addressing mode, (R1)+ | |

Pre-decrement addressing mode, -(R1) | |

Register direct addressing mode, R1 | |

Index addressing mode, X(R1), where X is an offset represented in 2’s complement 16-bit representation |

{

int marks[100];

char grade;

int cnumber;

}; struct data student

Base Address of student is available in R1.

So student.grade can be accessed efficiently by Relative Indexed Addressing Mode.

It is clearly mentioned X is the offset address to be summed with Base Address of R1.

Hence Index Addressing mode X(R1), where X is an offset represented in 2’s complement 16-bit representation.

⇾ Relative, Base Indexed & all subtypes of Indirect addressing modes are used with Arrays.

Question 12 |

Consider the following intermediate program in three address code

p = a - b q = p * c p = u * v q = p + q

Which of the following corresponds to a *static single assignment* form of the above code?

In Static Single Assignment form (SSA) each assignment to a variable should be specified with distinct names.

We use subscripts to distinguish each definition of variables.

In the given code segment, there are two assignments of the variable p

p = a-b

p = u*v

and two assignments of the variable q

q = p*c

q = p+q

So we use two variables p

_{1}, p

_{2}for specifying distinct assignments of p and q

_{1}, q

_{2}for each assignment of q.

Static Single Assignment form(SSA) of the given code segment is:

p

_{1}= a-b

q

_{1}= p

_{1}* c

p

_{2}= u * v

q

_{2}= p

_{2}+ q

_{1}

__Note__:

As per options, given in GATE 2017 answer is B.

p

_{3}= a - b

q

_{4}= p

_{3}* c

p

_{4}= u * v

q

_{5}= p

_{4}+ q

_{4}

Question 13 |

Consider the following C code:

#include <stdio.h> int *assignval(int *x, int val) { *x = val; return x; } void main ( ) { int *x = malloc(sizeof(int)); if(NULL == x) return; x = assignval(x, 0); if(x) { x = (int *)malloc(size of(int)); if(NULL == x) return; x = assignval(x, 10); } printf("%dn", *x); free(x); }

The code suffers from which one of the following problems:

compiler error as the return of malloc is not typecast approximately | |

compiler error because the comparison should be made as x==NULL and not as shown | |

compiles successfully but execution may result in dangling pointer | |

compiles successfully but execution may result in memory leak |

In C++, we need to perform type casting, but in C Implicit type casting is done automatically, so there is no compile time error, it prints10 as output.

Option B:

NULL means address 0, if (a == 0) or (0 == a) no problem, though we can neglect this, as it prints 10.

Option C:

x points to a valid memory location. Dangling Pointer means if it points to a memory location which is freed/ deleted.

int*ptr = (int*)malloc(sizeof(int));

free(ptr); //ptr becomes a dangling pointer

ptr = NULL; //Removing Dangling pointers condition

Option D:

x is assigned to some memory location

int*x = malloc(sizeof(int));

→ (int*)malloc(sizeof(int)) again assigns some other location to x, previous memory location is lost because no new reference to that location, resulting in Memory Leak.

Hence, Option D.

Question 14 |

Consider a TCP client and a TCP server running on two different machines. After completing data transfer, the TCP client calls *close* to terminate the connection and a FIN segment is sent to the TCP server. Server-side TCP responds by sending an ACK, which is received by the client-side TCP. As per the TCP connection state diagram (RFC 793), in which state does the client-side TCP connection wait for the FIN from the server-side TCP?

LAST-ACK | |

TIME-WAIT | |

FIN-WAIT-1 | |

FIN-WAIT-2 |

i.e. waiting for the ACK for own FIN segment.

There are two possibilities here:

I. If Client receives ACK for its FIN then client will move to FIN-WAIT-2 and will wait for matching FIN from server side.

After receiving the FIN from server, client will send ACK and move to TIME-WAIT state.

II. Client has sent FIN segment but didn’t get ACK till the time.

Instead of ACK, client received FIN from server side.

Client will acknowledge this FIN and move to CLOSE state.

Here Client will wait for the ACK for its own FIN.

After receiving ACK, client will move to TIME-WAIT state.

Here we encounter First Case.

So, the solution is (D).

Refer this TCP state transition diagram:

Question 15 |

*m*to receiver R, which is digitally signed by S with its private key. In this scenario, one or more of the following security violations can take place.

(I) S can launch a birthday attack to replace

*m*with a fraudulent message.

(II) A third party attacker can launch a birthday attack to replace

*m*with a fraudulent message.

(III) R can launch a birthday attack to replace

*m*with a fraudulent message.

Which of the following are possible security violations?

(I) and (II) only | |

(I) only | |

(II) only | |

(II) and (III) only |

(I) Can the sender replace the message with a fraudulent message?

Yes, definitely because the sender will encrypt the message with its private key.

It can encrypt another message also with its private key.

(II) Can the third party send a fraudulent message?

No, because the third party doesn't know about the private key of the sender.

(III) Can receiver send the fraudulent message?

No, the receiver also doesn't know about the Private key of the sender.

So receiver also cannot send the fraudulent message.

Question 16 |

V → W

VW → X

Y → VX

Y → Z

Which of the following is irreducible equivalent for this set of functional dependencies?

V→W V→X Y→V Y→Z | |

V→W W→X Y→V Y→Z | |

V→W V→X Y→V Y→X Y→Z | |

V→W W→X Y→V Y→X Y→Z |

V → W, VW → X, Y → V, Y → X, Y→ Z

Step 2:

V → W, VW → X, Y → V, Y → X, Y→ Z

(V)

^{+}= V ×

(VW)

^{+}= VW ×

(Y)

^{+}= YXZ

(Y)

^{+}= YVW ×

(Y)

^{+}= YVWX

Without Y → X, the closure of Y is deriving ‘X’ from the remaining attributes.

So, we can remove Y → X as its redundant.

Step 3:

V → W, VW → X, Y → V, Y → Z

(V)

^{+}= VW, the closure of V is deriving W from the remaining FD’s.

So, W is redundant. We can remove it.

So, the final canonical form is

V→W, V→X, Y→V, Y→Z

⇾ So, option (A) is correct.