31. Consider
the formula in image processing

R

_{D}= 1 - (1/C_{R}) Where C_{R}= n_{1}/n_{2}
C

_{R}is called as compression ratio n_{1}and n_{2}denotes the number of information carrying units in two datasets that represent the same information. In this situation R_{D}is called as relative ................ of the first data set.
(A) Data Compression

(B) Data Redundancy

(C) Data Relation

(D) Data Representation

Answer: B

32. Find
the false statement:

(A) In Modern Cryptography, symmetric key
algorithms use same key both for Encryption and Decryption.

(B) The Symmetric cipher DES (Data Encryption
Standard) was widely used in the industry for security product.

(C) The AES (Advanced Encryption Standard)
cryptosystem allows variable key lengths of size 56 bits and 124 bits.

(D) Public key algorithms use two different
keys for Encryption and Decryption.

Answer: C

33. The
message 11001001 is to be transmitted using the CRC polynomial x

^{3}+1 to protect it from errors. The message that should be transmitted is
(A) 110010011001

(B) 11001001

(C) 110010011001001

(D) 11001001011

Answer: D

__Explanation:__

CRC Polynomial x

^{3}+1 implies that the divisor is of 4 bit length, which is 1001.
(1*x

^{3}+ 0*x^{2}+ 0*x + 1*1) read off the coefficients to get 1001.
11001001 000
<--- input right padded by 3 bits

1001
<--- divisor

01011001 000
<---- XOR of the above 2

1001
<--- divisor

00010001 000

1001

00000011 000

10 01

00000001 010

1 001

00000000 011 <------- remainder (3 bits)

After dividing the given message 11001001 by
1001, we get the remainder as 011, which is the CRC. The transmitted data is,
message + CRC which is 11001001 011.

34. ...................
comparisons are necessary in the worst case to find both the maximum and
minimum of n numbers.

(A) 2n-2

(B) n + floor(lg n) - 2

(C) floor(3n/2) - 2

(D) 2 lg n – 2

Answer: C

35. Let
A and B be two n x n matrices. The efficient algorithm to multiply the two
matrices has the time complexity

(A) O(n

^{3})
(B) O(n

^{2.81})
(C) O(n

^{2.67})
(D) O(n

^{2})
Answer: B

__Explanation:__

The recurrence relation for the strassen
matrix multiplication is :

T(n) = 7T(n/2) + n

^{2}
by using the master method T(n)= O(n

^{log}_{2}^{7}) = O(n^{2.81})
36. The
recurrence relation T(n)=mT(n/2)an

^{2}is satisfied by
(A) O(n

^{2})
(B) O(n

^{lg m})
(C) O(n

^{2}lg n)
(D) O(n lg n)

Answer: Marks given to all

__Explanation:__

The recurrence relation T(n)=mT(n/2) + an

^{2}
by using the master method T(n) = O(n

^{log m})
37. The
longest common subsequence of the sequences X=<A, B, C, B, D, A, B> and Y=<B, D, C, A, B, A> has length

(A) 2

(B) 3

(C) 4

(D) 5

Answer: C

__Explanation:__**Definition:**

Given sequence X = <x

_{1}, x_{2}, …, x_{m}>, another sequence Z = <z_{1}, z_{2}, … , z_{k}> is a subsequence of X if …
– there exists a strictly increasing sequence
<i[1],i[2],…,i[k]> of indices of X s.t. for all j in [1,2,..k], x

_{i[j]}= z_{j}**Example**

– If X = <A,B,A,C,A,B> and Y =
<A,B,B,A> …

– then <A,A>, <A,B>, <B,A>,
<B,B>, <A,B,A>, <A,B,B> are all subsequences of both X and
Y—i.e., they are common subsequences.

**Longest Common Subsequence**

• If X = <A,B,C,B,D,A,B> and Y =
<B,D,C,A,B,A>, then <B,C,A> is a common subsequence, but not a
longest common subsequence (LCS)

– <B,C,B,A> and <B,C,A,B> are
both longest common subsequences of X, Y

• (there is no common subsequence of length
5)

38. Assuming
there are n keys and each keys is in the range [0, m-1]. The run time of bucket
sort is

(A) O(n)

(B) O(n lgn)

(C) O(n lgm)

(D) O(n+m)

Answer: D

39. A
................. complete subgraph and a ................. subset of vertices
of a graph G=(V,E) are a clique and a vertex cover respectively.

(A) minimal, maximal

(B) minimal, minimal

(C) maximal, maximal

(D) maximal, minimal

Answer: D

__Explanation:__

A clique is a complete graph, where every
pair of vertices are connected by an edge.

A vertex cover of a graph G is a subset of
vertices such that every edge e Ïµ E is incident to a vertex in the subset.

40. Pumping
lemma of the context-free languages states:

Let L be an infinite context free language.
Then there exists some positive integer m such that wÏµL with |w|≥m can be
decomposed as w=uv xy Z with |vxy| ................. and |vy| ................
such that uv

^{z’}xy^{z’}, ZÏµL for all z’ = 0,1, 2,...
(A) ≤m, ≤1

(B) ≤m, ≥1

(C) ≥m, ≤1

(D) ≥m, ≥1

Answer: B

## 0 Comments