Question 1 |

The statement (\neg p)\Rightarrow (\neg q) is logically equivalent to which of the statements below?

I. p\Rightarrow q

II. q \Rightarrow p

III. (\neg q)\vee p

IV. (\neg p)\vee q

I. p\Rightarrow q

II. q \Rightarrow p

III. (\neg q)\vee p

IV. (\neg p)\vee q

I only | |

I and IV only | |

II only | |

II and III only |

Question 1 Explanation:

Question 2 |

Consider the first-order logic sentence F:\forall x(\exists yR(x,y)). Assuming non-empty logical
domains, which of the sentences below are implied by F?

I. \exists y(\exists xR(x,y))

II. \exists y(\forall xR(x,y))

III. \forall y(\exists xR(x,y))

IV. \neg \exists x(\forall y\neg R(x,y))

I. \exists y(\exists xR(x,y))

II. \exists y(\forall xR(x,y))

III. \forall y(\exists xR(x,y))

IV. \neg \exists x(\forall y\neg R(x,y))

IV only | |

I and IV only | |

II only | |

II and III only |

Question 2 Explanation:

Question 3 |

Let c_{1}....c_{n} be scalars, not all zero, such that \sum_{i=1}^{n}c_{i}a_{i}=0

where a_{i} are column vectors in R^{n}. Consider the set of linear equations Ax = b

where A=a_{1}....a_{n} and b=\sum_{i=1}^{n}a_{i}. The set of equations has

where a_{i} are column vectors in R^{n}. Consider the set of linear equations Ax = b

where A=a_{1}....a_{n} and b=\sum_{i=1}^{n}a_{i}. The 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 |

Question 3 Explanation:

Question 4 |

Consider the following functions from positive integers to real numbers:

10,\sqrt{n},n, log_{2}n,\frac{100}{n}.

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

10,\sqrt{n},n, log_{2}n,\frac{100}{n}.

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

log_{2}n,\frac{100}{n}, 10,\sqrt{n},n | |

\frac{100}{n}, 10,log_{2}n, \sqrt{n}, n | |

10, \frac{100}{n}, \sqrt{n}, log_{2}n, n | |

\frac{100}{n}, log_{2}n, 10, \sqrt{n}, n |

Question 4 Explanation:

Question 5 |

Consider the following table:

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

Match the algorithms to the 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) |

Question 5 Explanation:

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.

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 |

Question 6 Explanation:

Question 7 |

The n-bit fixed-point representation of an unsigned real number real 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}) |

Question 7 Explanation:

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

Question 8 Explanation:

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 Combinational Circuit, 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 | |

(A_{7}B_{7}\bar{S_{7}}+\bar{A_{7}}\bar{B_{7}}S_{7}) is 1 | |

(A_{0}B_{0}\bar{S_{0}}+\bar{A_{0}}\bar{B_{0}}S_{0})
is 1 |

Question 9 Explanation:

Question 10 |

Consider the following context-free grammar over the alphabet \sum = {a,b,c} with S as the start
symbol.

S\rightarrowabScT|abcT

T\rightarrowbT|b

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

S\rightarrowabScT|abcT

T\rightarrowbT|b

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

{(ab)^{n}(cb)^{n}|n\geq 1} | |

{(ab)^{n}cb^{m_{1}}cb^{m_{2}}...cb^{m_{n}}|n,m_{1},m_{2},...,m_{n}\geq 1} | |

(ab)^{n}(cb^{m})^{n}|n,m\geq 1 | |

(ab)^{n}(cb^{n})^{m}|n,m\geq 1 |

Question 10 Explanation:

There are 10 questions to complete.