STUPIDSID
Solve any one question fromQ.1(a,b) and Q.2(a,b)
1(a)
Prove the statement is true using mathematical induction:
n3+2n is divisible by 3 for all n > = 1
n3+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 a0=1 and a1 =6
6 M
4(b)(i)
What is complement of kn and kmn?
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