Computer Science and Information Technology - GATE 2017 Paper Solution


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}$

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 x\left(\forall y\neg R\left(x,y\right)\right)} $

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 

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:

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.

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

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

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 

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

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?

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

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?

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:

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?

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?

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 ?

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)?

Threads of a process share 

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 ___________.

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