## UGC Net Computer Science December-12 Paper 3 Page 2 Solved

11. The time complexities of some standard graph algorithms are given.Match each algorithm with its time complexity ? (n and m are no. of nodes and edges respectively)

a. Bellman Ford algorithm 1. O (m log n)

b. Kruskals algorithm 2. O (n3)

c. Floyd Warshall algorithm 3. O(mn)

d. Topological sorting 4. O(n + m)

**Codes :**

a b c d

(A) 3 1 2 4

(B) 2 4 3 1

(C) 3 4 1 2

(D) 2 1 3 4

12. Let V1 = 2I – J + K and V2 = I + J – K,then the angle between V1 & V2 and a vector perpendicular to both V1 & V2 shall be :

(A) 90 ⠁ and (–2I + J – 3K)

(B) 60⠁ and (2I + J + 3K)

(C) 90⠁ and (2I + J – 3K)

(D) 90⠂ and (–2I – J + 3K)

__Answer D__

13. Consider a fuzzy set A defined on the

interval X = [0, 10] of integers by the

membership Junction

Then the 饾挾 cut corresponding to

饾挾= 0.5 will be

(A) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

(B) {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

(C) {2, 3, 4, 5, 6, 7, 8, 9, 10}

(D) { }

__Answer D____Explanation:-__
In the fundamentals, refer to the answer given for question no. 6 regarding 伪-cut.

伪-cut of a fuzzy set A denoted as A伪, is the crisp set comprised of the elements x of a universe of discourse X for which the membership function of A is greater than or equal to 伪.

Given, x = In the range [0,10]

Membership function = x/x+2

Calculate the value of membership function for the interval from 0 to 10, substituting in the formula x/x+2.

碌A(0) = 0 / 0+ 2 = 0

碌A(1) = 1 / 1+ 2 = 0.33

碌A(2) = 2 / 2+ 2 = 0.5

碌A(3) = 3 / 3+ 2 = 0.6

碌A(4) = 4 / 4+ 2 = 0.66

碌A(5) = 5 / 5+ 2 = 0.71

碌A(6) = 6 / 6+ 2 = 0.75

碌A(7) = 7 / 7+ 2 = 0.77

碌A(8) = 8 / 8+ 2 = 0.8

碌A(9) = 9 / 9+ 2 = 0.81

碌A(10) = 10 / 10+ 2 = 0.83

伪= 0.5. We have to find the corresponding 伪-cut,

That will be a crisp set, having those values of x, for which the membership function is returning a value of 0.5 or above.

碌A(2) = 0.5 and all the values of x above 2 is getting a value greater than 0.5. So the crisp set will contain the following values.

{ 2,3,4,5,6,7,8,9,10}.

http://internetnotes.in/

14. Let T(n) be the function defined by T(n) = 1 and T(n) = 2T (n/2) + 鍘俷, which of the following is TRUE ?

(A) T(n) = O( 鍘俷)

(B) T(n) = O(log2n)

(C) T(n) = O(n)

(D) T(n) = O(n2)

15. In classful addressing, an IP address 123.23.156.4 belongs to ______ class format.

(A) A

(B) B

(C) C

(D) D

伪-cut of a fuzzy set A denoted as A伪, is the crisp set comprised of the elements x of a universe of discourse X for which the membership function of A is greater than or equal to 伪.

Given, x = In the range [0,10]

Membership function = x/x+2

Calculate the value of membership function for the interval from 0 to 10, substituting in the formula x/x+2.

碌A(0) = 0 / 0+ 2 = 0

碌A(1) = 1 / 1+ 2 = 0.33

碌A(2) = 2 / 2+ 2 = 0.5

碌A(3) = 3 / 3+ 2 = 0.6

碌A(4) = 4 / 4+ 2 = 0.66

碌A(5) = 5 / 5+ 2 = 0.71

碌A(6) = 6 / 6+ 2 = 0.75

碌A(7) = 7 / 7+ 2 = 0.77

碌A(8) = 8 / 8+ 2 = 0.8

碌A(9) = 9 / 9+ 2 = 0.81

碌A(10) = 10 / 10+ 2 = 0.83

伪= 0.5. We have to find the corresponding 伪-cut,

That will be a crisp set, having those values of x, for which the membership function is returning a value of 0.5 or above.

碌A(2) = 0.5 and all the values of x above 2 is getting a value greater than 0.5. So the crisp set will contain the following values.

{ 2,3,4,5,6,7,8,9,10}.

http://internetnotes.in/

14. Let T(n) be the function defined by T(n) = 1 and T(n) = 2T (n/2) + 鍘俷, which of the following is TRUE ?

(A) T(n) = O( 鍘俷)

(B) T(n) = O(log2n)

(C) T(n) = O(n)

(D) T(n) = O(n2)

__Answer C__15. In classful addressing, an IP address 123.23.156.4 belongs to ______ class format.

(A) A

(B) B

(C) C

(D) D

__Answer A____Explanation:-__Class | 1^{st} Octet Decimal Range | 1^{st} Octet High Order Bits | Network/Host ID (N=Network, H=Host) | Default Subnet Mask | Number of Networks | Hosts per Network (Usable Addresses) |
---|---|---|---|---|---|---|

A | 1 – 126* | 0 | N.H.H.H | 255.0.0.0 | 126 (2^{7} – 2) | 16,777,214 (2^{24} – 2) |

B | 128 – 191 | 10 | N.N.H.H | 255.255.0.0 | 16,382 (2^{14} – 2) | 65,534 (2^{16} – 2) |

C | 192 – 223 | 110 | N.N.N.H | 255.255.255.0 | 2,097,150 (2^{21} – 2) | 254 (2^{8} – 2) |

D | 224 – 239 | 1110 | Reserved for Multicasting | |||

E | 240 – 254 | 1111 | Experimental; used for research |

16. The Mandelbrot set used for the construction of beautiful images is based on the following transformation :

(A) Both x & z are real numbers.

(B) Both x & z are complex numbers.

(C) x is real & z is complex.

(D) x is complex & z is real.

__Answer c__

__Explanation:-__

17. Which of the following permutations can be obtained in the output using a stack of size 3 elements assuming that input, sequence is 1, 2, 3, 4, 5 ?

(A) 3, 2, 1, 5, 4

(B) 5, 4, 3, 2, 1

(C) 3, 4, 5, 2, 1

(D) 3, 4, 5, 1, 2

__Answer D__

__Explanation:-__
Push(1),Push(2),Push(3),Pop(

**3**),Push(4),Pop(**4**),Push(5),Pop(**5**),Push(?=1),Pop(**1**),Pop(**2**)
Output is indicate by blue color :

3,4,5,1,2

18. In a Linear Programming Problem,suppose there are 3 basic variables and 2 non-basic variables, then the possible number of basic solutions are

(A) 6

(B) 8

(C) 10

(D) 12

__Answer C__

__Explanation:-__
Total number of feasible solutions are n!/(factorial(m)*factorial(n-m)).

M is the basic variable having non zero values.

N=3+2

M=3

(5*4*3*2*1)/((3*2)(2))=10.

19. Identify the following activation function :

Z, X, Y are parameters

(A) Step function

(B) Ramp function

(C) Sigmoid function

(D) Gaussian function

__Answer C__

__Explanation:-__
. identity
function:

f(x)=
x
for all x

2. binary
step function

f(x)=
1 if x>=胃

f(x)=0 if
x<胃

3. bipolar
step function

f(x)=
1 if x>=胃

f(x)= -1 if x<胃

4. sigmoidal
function

· binary sigmoid function

f(x)=1/1+e-位x where 位 represent steepness parameter

· bipolar simoid function:

f(x)=2/(1+e-位x ) -1

= 1-( e-位x)/1+( e-位x)

· binary sigmoid function

f(x)=1/1+e-位x where 位 represent steepness parameter

· bipolar simoid function:

f(x)=2/(1+e-位x ) -1

= 1-( e-位x)/1+( e-位x)

5. ramp
function:

f(x)=
1 if x>1

f(x)= x if
0<=x<=1

f(x)= 0 if
x<

http://csnetpapers.blogspot.in/

**20.**The no. of ways to distribute n distinguishable objects into k distinguishable boxes, so that ni objects are placed into box i, i = 1, 2, …. K equals which of the following ?

(A)

n!

________________

________________

n1! + n2! + ..... +
nk!

(B)

n1! + n2! + ..... +
nk!

_________________

_________________

n1! n2! n3! ..... nk!

(C)

n!

_________________

_________________

n1! n2! n3! ..... nk!

(D)

n1! n2! ..... nk!

_____________________

_____________________

n1! – n2! – n3! ..... – nk!

__Answer C__

__Explanation:-__

**Placing particular numbers of distinguishable objects (labeled balls) in distinguishable boxes (labeled urns).**

That is, placing n1 objects into the first box, n2 objects into the second box, etc., and nk into the kth box.

Surprisingly, the problem of counting the ways to put particular numbers of n labeled balls in k labeled urns is the same as that of counting the ways to permute sets of n objects with k types of indistinguishable objects, with a particular number of each type of object.

I say surprisingly, because at first these appear to be different problems. But if you think back to the MISSISSIPPI problem, and consider not permuting not the M's, I's, S's, and P's, but rather assigning the eleven letter positions to labeled urns, then the problem becomes "How many ways can the numbers 1 through 11 be placed in four urns such that one number be placed in urn 'M', 4 numbers be placed in urn 'I', 2 numbers be placed in urn 'P', and 4 numbers be placed in urn 'S'"? For each way of permuting the letters in MISSISSIPPI, there is a corresponding way of assigning the given quantities of the 11 letter positions to the four urns.

So the formula for the number of ways to place n distinguishable objects into k distinguishable boxes, such that n1 objects go in the first box, n2 in the second, ... and nk go in the kth box is:

n! / (n1! n2! ... nk!)

*http://2000clicks.com/mathhelp/CountingObjectsInBoxes.aspx*