31. Consider
the formula in image processing
RD = 1 - (1/CR) Where CR
= n1/n2
CR is called as compression ratio n1
and n2 denotes the number of information carrying units in two datasets
that represent the same information. In this situation RD 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 x3+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 x3+1 implies that
the divisor is of 4 bit length, which is 1001.
(1*x3 + 0*x2 + 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(n3)
(B) O(n2.81)
(C) O(n2.67)
(D) O(n2)
Answer: B
Explanation:
The recurrence relation for the strassen
matrix multiplication is :
T(n) = 7T(n/2) + n2
by using the master method T(n)= O(nlog27)
= O(n2.81)
36. The
recurrence relation T(n)=mT(n/2)an2 is satisfied by
(A) O(n2)
(B) O(nlg m)
(C) O(n2 lg n)
(D) O(n lg n)
Answer: Marks given to all
Explanation:
The recurrence relation T(n)=mT(n/2) + an2
by using the master method T(n) = O(nlog
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 = <x1, x2,
…, xm>, another sequence Z = <z1, z2, …
, zk> 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], xi[j]
= zj
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 uvz’xyz’ , ZϵL for all z’ = 0,1, 2,...
(A) ≤m, ≤1
(B) ≤m, ≥1
(C) ≥m, ≤1
(D) ≥m, ≥1
Answer: B
0 Comments