Computer Science & Information Technology (CS) 2017 [Session 1]

1

2017 · Unclassified

Computer Science & Information Technology (CS) 2017 [Session 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$

A

I only

B

I and IV only

C

II only

D

II and III only

2

2017 · Unclassified

Computer Science & Information Technology (CS) 2017 [Session 1]

Consider the first-order logic sentence $F: \forall x(\exists y R(x, y))$. Assuming non-empty logical domains, which of the sentences below are implied by $F$?
I.   $\exists y(\exists x R(x, y))$
II.   $\exists y(\forall x R(x, y))$
III.   $\forall y(\exists x R(x, y))$
IV.   $\neg \exists x(\forall y \neg R(x, y))$

A

IV only

B

I and IV only

C

II only

D

II and III only

3

2017 · Unclassified

Computer Science & Information Technology (CS) 2017 [Session 1]

Let \( c_1, \ldots, 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 \( \mathbf{R}^n \). Consider the set of linear equations \( Ax = b \) where \( A = [a_1, \ldots, a_n] \) and \( b = \sum_{i=1}^n a_i \). The set of equations has

A

a unique solution at \(x = J_n \) where \(J_n \) denotes a \(n \)-dimensional vector of all 1

B

no solution

C

infinitely many solutions

D

finitely many solutions

4

2017 · Unclassified

Computer Science & Information Technology (CS) 2017 [Session 1]

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:

A

\(\log_2 n, \frac{100}{n}, 10, \sqrt{n}, n \)

B

\(\frac{100}{n}, 10, \log_2 n, \sqrt{n}, n \)

C

\(10, \frac{100}{n}, \sqrt{n}, \log_2 n, n \)

D

\(\frac{100}{n}, \log_2 n, 10, \sqrt{n}, n \)

5

2017 · Unclassified

Computer Science & Information Technology (CS) 2017 [Session 1]

Consider the following table:

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

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

A

(P) \(\leftrightarrow \) (ii), (Q) \(\leftrightarrow \) (iii), (R) \(\leftrightarrow \) (i)

B

(P) \(\leftrightarrow \) (iii), (Q) \(\leftrightarrow \) (i), (R) \(\leftrightarrow \) (ii)

C

(P) \(\leftrightarrow \) (ii), (Q) \(\leftrightarrow \) (i), (R) \(\leftrightarrow \) (iii)

D

(P) \(\leftrightarrow \) (i), (Q) \(\leftrightarrow \) (ii), (R) \(\leftrightarrow \) (iii)

6

2017 · Unclassified

Computer Science & Information Technology (CS) 2017 [Session 1]

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.

A

4 and 15 respectively

B

3 and 14 respectively

C

4 and 14 respectively

D

3 and 15 respectively