## Tuesday, 3 October 2017

### UGC Net Computer Science December 13 Paper 3 Page 4 Solved

31. Consider the formula in image
processing

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

Explanation : Data compression ratio is defined as the ratio between the uncompressed size and compressed size

Thus a representation that compresses a 10 MB file to 2 MB has a compression ratio of 10/2 = 5, often notated as an explicit ratio, 5:1 (read "five" to "one"), or as an implicit ratio, 5/1. Note that this formulation applies equally for compression, where the uncompressed size is that of the original; and for decompression, where the uncompressed size is that of the reproduction.

Sometimes the space savings is given instead, which is defined as the reduction in size relative to the uncompressed size:

Thus a representation that compresses a 10MB file to 2MB would yield a space savings of 1 - 2/10 = 0.8, often notated as a percentage, 80%.

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.
Explanation : Advanced encryption algorithm would be unclassified and had to be "capable of protecting sensitive government information well into the next century," according to the NIST announcement of the process for development of an advanced encryption standard algorithm.

The selection process for this new symmetric key algorithm was fully open to public scrutiny and comment; this ensured a thorough, transparent analysis of the designs submitted.

NIST specified the new advanced encryption standard algorithm must be a block cipher capable of handling 128 bit blocks, using keys sized at 128, 192, and 256 bits; other criteria for being chosen as the next advanced encryption standard algorithm included:

Security: Competing algorithms were to be judged on their ability to resist attack, as compared to other submitted ciphers, though security strength was to be considered the most important factor in the competition.

Cost: Intended to be released under a global, nonexclusive and royalty-free basis, the candidate algorithms were to be evaluated on computational and memory efficiency.

Implementation: Algorithm and implementation characteristics to be evaluated included the flexibility of the algorithm; suitability of the algorithm to be implemented in hardware or software; and overall, relative simplicity of implementation.

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

(D) 2 lg n – 2

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

36. The recurrence relation T(n)= Tan2  is satisfied by

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

38.Assuming there are n keys and each key 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)

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

40. Pumping lemma for context-free languages states : Let L be an infinite context free language. Then there exists some positive integer m such that any 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