Computer Science and Information Technology - GATE 2017 Paper Solution

Question No. 1

The statement $\style{font-family:'Times New Roman'}{\left(\neg p\right)\Rightarrow\left(\neg q\right)}$ is logically equivalent to which of the statments below?

I. $\style{font-family:'Times New Roman'}{p\Rightarrow q}$

II. $\style{font-family:'Times New Roman'}{q\Rightarrow p}$

III. $\style{font-family:'Times New Roman'}{\left(\neg q\right)\vee p}$

IV. $\style{font-family:'Times New Roman'}{\left(\neg p\right)\vee q}$

Question No. 2

Consider the first-order logic sentence $\style{font-family:'Times New Roman'}{F:\forall x\left(\exists yR\left(x,y\right)\right)}$. Assuming non-empty logical domains, which of the sentence below are implied by F?

$\style{font-family:'Times New Roman'}{\mathrm I.\;\exists y\left(\exists xR\left(x,y\right)\right)}$

$\style{font-family:'Times New Roman'}{\mathrm{II}.\;\exists y\left(\forall xR\left(x,y\right)\right)}$

$\style{font-family:'Times New Roman'}{\mathrm{III}.\;\forall y\left(\exists xR\left(x,y\right)\right)}$

$\style{font-family:'Times New Roman'}{\mathrm{IV}.\;\neg\exists y\left(\forall y\neg R\left(x,y\right)\right)}$

Question No. 3

Let c1,....,cn be scalars, not all zero, such that $\style{font-family:'Times New Roman'}{\sum_\limits{i=1}^nc_ia_i=0}$ where ai are column vectors in Rn Consider the set of linear equations
                                                      $\style{font-family:'Times New Roman'}{Ax=b}$
where $\style{font-family:'Times New Roman'}{A=\left[a_1,....,a_n\right]\;\mathrm{and}\;b=\sum_\limits{i=1}^na_i}$. The set of equations has 

Question No. 4

Consider the following function from positive integers to real numbers:

                        $\style{font-family:'Times New Roman'}{10,\;\sqrt n,\;n,\;\log_2n,\;\frac{100}n.}$

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

Question No. 5

Consider the following table:

                   Algorithms                   Design Paradigms
(P) Kruskal (i) Divided and conquer
(Q) Quicksort (ii) Greedy
(R) Floyd-Warshall (iii) Dynamic Programming

Match the algorithms to the design paradigms they are based on.

Question No. 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

Question No. 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

Question No. 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 

Question No. 9

When two 8-bit  number A7....A0  and  B7 ..... B0  in 2's  complement representation (with A0 and B0 as the least significant bits) are added using ripple-carry adder, the sum bits obtained are S7.....S0 and the  carry bits are C7....C0 . An overflow is said to have occured if

Question No. 10

Consider the following context-free grammar over the alphabet $\style{font-family:'Times New Roman'}{\sum=\{a,b,c\}}$ with S as the  start  symbol:

$\style{font-family:'Times New Roman'}{\begin{array}{l}S\rightarrow abScT\;\vert\;abcT\\T\rightarrow bT\;\vert\;b\end{array}}$

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

Question No. 11

Consider 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 filed  student. grade  can be accessed efficiently using

Question No. 12

Consider the following intermediate program in three address code

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

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

Question No. 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 (sizeof  (int));
        if  (NULL ==  x)  return;
        x  =  assignval  (x,10) ;
        printf ("%d\n" ,  *x) ;
        free  (x) ;

The code suffers from which one of the following problems:

Question No. 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?

Question No. 15

A sender S sends a message 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?

Question No. 16

The following functional dependencies hold true for the relational schema R {V, W, X, Y, Z}:

                                                                                $\style{font-family:'Times New Roman'}{\begin{array}{l}V\rightarrow W\\VW\rightarrow X\\Y\rightarrow VX\\Y\rightarrow Z\end{array}}$

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

Question No. 17

Consider the following grammar:

$\style{font-family:'Times New Roman'}{\begin{array}{l}P\rightarrow xQRS\\Q\rightarrow yz\;\vert\;z\\R\rightarrow w\;\vert\;\varepsilon\\S\rightarrow y\\\end{array}}$

What is FOLLOW(Q)?

Question No. 18

Threads of a process share 

Question No. 19

Let X be a Gaussian random variable with mean 0 and variance $\style{font-family:'Times New Roman'}{\sigma^2}$. Let Y= max(X,0) where max(a,b) is the maximum of a and b. The median of Y is ___________.

Question No. 20

Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is ____________ .