U.G.C. NET Exam. 4 December, 2019 Paper II (COMPUTER SCIENCE & APPLICATIONS)

41. When using Dijkstra's algorithm to find shortest path in a graph, which of the following statement is not true?

(a) It can find shortest path within the same graph data structure
(b) Every time a new node in visited. we choose the node with smallest known distance/cost (weight) to visit first
(c) Shortest path always passes through least number of vertices
(d) The graph needs to have a non-negative weight on every edge

Correct Answer: (c) Shortest path always passes through least number of vertices

Solution:

42. The time complexity to multiply two polynomials of degree n using Fast Fourier transform method is:

Correct Answer: (a)

Solution:

Fast Fourier transform is a discrete Fourier transform algorithm which reduces the number of computation needed for N points from 2N² to 2N log N.
A discrete Fourier transform can be computed using fast Fourier transform by means of Daniel-Sonlanczos lemma, if the number of point N is a Power of two. If number of points N is not a power of two, a transform can be performed n sets of points corresponding to prime factor of N.
Fast Fourier transform allows computing in 0(n log n) time. Basic idea is to apply divide and conquer. We divide the co-efficient vector of polynomial into two vectors, recursively compute the Discrete Fourier transform for each of them and combine the results Recursive relation will become;

43. Consider the following grammars:

Correct Answer: (c)

Solution:

44. Answer the following question

(a) S→aA|a, A→aAb|b
(b) S→aaA|λ, A→aAb|λ
(c) S→aaaA|a, A→aAb|λ
(d) S→aaaA, A→aAb|λ

Correct Answer: (d) S→aaaA, A→aAb|λ

Solution:

for n = 3, string generated = aaa for n = 4, string generated = aaaab for n = 5 string generated = aaaaabb only option 4 can generate the above grammar at following value of n

45. Consider the following grammar :

S → 0A|0BB
A → 00A|λ
B → 1B|11C
C → B
Which language does this grammar generate ?

(a) L((00)*0 + (11)*1)
(b) L(0(11)*0 +1 (00)*)
(c) L((00)*0)
(d) L(0(11)*1)

Correct Answer: (c) L((00)*0)

Solution:

Given grammar is generating string of type: {0,000,00000,0000000...........}
(1) L((00) * 0 + (11) * 1 )
This language generating string with combination of 0'S and 1 and But given Grammar is not generating any string composed of 1's.

46. Answer the following question

(a) (zxyy + xzy)(zxyy)
(b) (zxyy+(xzy)*)(zxyyzxyy)*
(c) (zxyy+xzy)(zxyy)*
(d) (zxyy+(xzy)*)(zxyyzxyy)

Correct Answer: (b) (zxyy+(xzy)*)(zxyyzxyy)*

Solution:

Homomorphism is a function from string to string that is based on the concatenation for any x and y ∈∑* h(x,y) = h(x) h(y)
L is the regular language with the regular expression r =
(w + x*) (ww)*
Then h(L) = (h(w) + h(x)*) (h(w)h(w))*
Given : h(x) = xzy
h(w) = zxyy
h(L) = (zxyy+(xzy)*) (zxyy zxyy)*

47. Answer the following question

Correct Answer: (d)

Solution:

48. Answer the following question

Correct Answer: (a)

Solution:

49. Let G = (V,T,S,P)be any context - free grammar without any λ-productions or unit production Let K be the maximum number of symbols on the right of any production in P. The maximum number of production rules for any equivalent grammar in Chomsky normal from is given by:

(a) (K–1)|P| – |T| –1
(b) (K–1)|P| + |T|
(c) K|P| + |T| –1
(d) K|P| + |T|

Correct Answer: (b) (K–1)|P| + |T|

Solution:

Context free Grammar :- A grammar G = (V,T,S,P) is said to be context- free if all productions in P have the from A →X Where A∈V and X∈(V U T)* If context the grammar G = (V,T,S,P) is without λproductions or unit productions. K = maximum number of symbols on right-side of production.
The maximum number of production rules for equivalent grammar in CNF: (K–1)|P|+|T| A context free grammar is in CNF (Chomsky normal form) if it satisfies these conditions: 1. Should not contains null or unit productions. 2. A non- terminal symbol generating two non-terminals for examples S →AB 3. A non-terminal generating a terminal example: S →a