Solve any one question fromQ.1(a,b) and Q.2(a,b)

1(a)
Prove the statement is true using mathematical induction:

n

n

^{3}+2n is divisible by 3 for all n > = 1
6 M

1(b)
A bag contains 3 red and 5 black balls and second bag contains 6 red and 4 black balls. A ball is drawn from each bag. Find the probability that:

i) both are red

ii) both are black

iii) 1 is red and 1 is black.

i) both are red

ii) both are black

iii) 1 is red and 1 is black.

6 M

2(a)
Among 130 students, 60 study mathematics, 51 study physics and 30 study both mathematics and physics. Out of 54 students studying chemistry, 26 study mathematics, 21 study physics and 12 study both mathematics and physics. All the students studying neither mathematics nor physics are studying biology:

i) Find how many are studying Biology?

ii) How many not studying chemistry are studying mathematics but not physics?

iii) How many students are studying are neither mathematics nor physics nor chemistry?

i) Find how many are studying Biology?

ii) How many not studying chemistry are studying mathematics but not physics?

iii) How many students are studying are neither mathematics nor physics nor chemistry?

6 M

2(b)
The probability that a contractor will get a plumbing contract is 2/3 and the probability that he will not get electric contract is 5/9. If the probability of getting at least one contract is 4/5. What is the probability that he will get both the contracts?

6 M

Solve any one question fromQ3(a,b) and Q.4(a,b)

3(a)
Find the transitive closure of R by Warshall's algortihm where A = {1, 2, 3, 4, 5, 6} and R={(x, y) | |x -y|=2} and draw it digraph.

6 M

3(b)
Use Dijkstra's algorithm to find the shortest path from a to z:

!mage

!mage

6 M

4(a)
What is recurrence relation? Solve the following recurrence relation \[a_r-4a_{r-1}+4a_{r-2}=0\] given that a

_{0}=1 and a_{1}=6
6 M

4(b)(i)
What is complement of k

_{n}and k_{mn}?
4 M

4(b)(ii)
Is the of the following graphs strongly connected?

!mage

!mage

2 M

Solve any one question fromQ5(a,b) and Q.6(a,b)

5(a)
A secondary storage media contains information of files with different formats. The frequency of different types of files is as follows:

Exe(20), bin(75), bat(20), jpeg(85), dat(51), doc(32), sys(26), c(19), cpp(25), bmp(30), avi(24), prj(29), 1st(35), zip(37). Using Huffman algorithm, find optimal tree and its prefix codes.

Exe(20), bin(75), bat(20), jpeg(85), dat(51), doc(32), sys(26), c(19), cpp(25), bmp(30), avi(24), prj(29), 1st(35), zip(37). Using Huffman algorithm, find optimal tree and its prefix codes.

7 M

5(b)
Find minimum spanning tree for the graph given below using Prim's algorithm.

!mage

!mage

6 M

6(a)
Determine the preorder, postorder and inorder traversal of the following binary tree shown in Fig. 3:

!mage

!mage

7 M

6(b)
Find minimum spanning tree for the graph given in Fig. 2 using Kruskal's algorithm.

6 M

Solve any one question fromQ.7(a,b) and Q.8(a,b)

7(a)
What is hamming distance? Find hamming distance between code words of:

c = {(0000), ( 0 1 0 1), (1 0 1 1), (0, 1 1 1)}

Rewrite the message by adding even parity check bit.

c = {(0000), ( 0 1 0 1), (1 0 1 1), (0, 1 1 1)}

Rewrite the message by adding even parity check bit.

6 M

7(b)
Define the following terms with suitable example:

i) Group

ii) Subgroup

iii) Ring

iv) Monoid.

i) Group

ii) Subgroup

iii) Ring

iv) Monoid.

7 M

8(a)
Let Z be the set of integers:

i) Show that the operation * on Z defined by a * b = a+b+1 for all a, b ∈ Z satisfies the closure property, associative law and the commutative law.

i) Find the identity element

ii) Define inverse. What is the inverse of an integer a?

i) Show that the operation * on Z defined by a * b = a+b+1 for all a, b ∈ Z satisfies the closure property, associative law and the commutative law.

i) Find the identity element

ii) Define inverse. What is the inverse of an integer a?

6 M

8(b)
Define each of the following:

i)Homomorphism of group

ii) Isomorphism of group

iii) Semigroup

iv) Abelian group

Also show that is abelian group.

i)Homomorphism of group

ii) Isomorphism of group

iii) Semigroup

iv) Abelian group

Also show that

7 M

More question papers from Discrete Structures