 Sample Questions, Previous Year Solved Papers, Study Materials For Competitive Examinations Like UGC NET, SET And GATE Computer Science.

Friday, 25 May 2018

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
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.
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
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
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)
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
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,i,…,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)
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
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