STUPIDSID
1 (a)
Prove by mathematical induction xn-yn is divisible by x-y.
5 M
1 (b)
How many vertices are necessary to construct a graph with exactly 6 edges in which each vertex is of degree 2.
5 M
1 (c)
Show that a relation is reflexive and circular if and only if it is an equivalence relation.
5 M
1 (d)
Prove that the set G={1,2,3,4,5,6} is an abelian group under multiplication modulo 7.
5 M
2 (a)
Is it possible to draw a tree with five vertices having degrees 1,1,2,2,4?
4 M
2 (b)
Find how many integers between 1 and 60 are
i) not divisible by 2 nor by 3 and nor by 5.
ii) Divisible by 2 but not by 3 and nor by 5.
i) not divisible by 2 nor by 3 and nor by 5.
ii) Divisible by 2 but not by 3 and nor by 5.
8 M
2 (c)
Solve the recurrence relation ar+2-ar+1-6a=4.
8 M
3 (a)
Show that A?(B?C)=(A?B)?(A?C)
4 M
3 (b)
State and explain Pigeonhole principle, extended Pigeonhole principle. How many numbers must be selected from the set {1,2,3,4,5,6} to guarantee that at least one pair of these numbers add up to 7?
8 M
3 (c)
Let R be a relation on set A={1,2,3,4}, given as
R={(1,1), (1,4), (2,2), (2,3), (3,2), (3,3), (4,1), (4,4)}.
Find transitive closure using Warshall's Algorithm.
R={(1,1), (1,4), (2,2), (2,3), (3,2), (3,3), (4,1), (4,4)}.
Find transitive closure using Warshall's Algorithm.
8 M
4 (a)
Find the generating function for the following sequence
i) 1,2,3,4,5,6......
ii) 3,3,3,3,3......
i) 1,2,3,4,5,6......
ii) 3,3,3,3,3......
4 M
4 (b)
Show that the (2,5) encoding function e:B2?B5 defined by
e(00)=00000 e(01)=01110
e(10)=10101 e(11)=11011 is a group code.
How many errors will it detect and correct.
e(00)=00000 e(01)=01110
e(10)=10101 e(11)=11011 is a group code.
How many errors will it detect and correct.
8 M
4 (c)
Draw Hasse Diagram of D42. Find the complement of each element in D42.
8 M
5 (a)
Define Distributive Lattice along with one appropriate example.
4 M
5 (b)
Let the functions f,g and h defined as follows:
f:R→R, f(x)=2x+3
g:R→R, g(x)=3x+4
h:R→R, h(x)=4x
Find gof, fog, hof, gofoh
f:R→R, f(x)=2x+3
g:R→R, g(x)=3x+4
h:R→R, h(x)=4x
Find gof, fog, hof, gofoh
8 M
5 (c)
\[ Let \ H= \begin{vmatrix}
1 &0 &0 \\0 &1 &1 \\1 &1 &1 \\1 &0 &0 \\0
&1 &0 \\0 &0 &1 \end{vmatrix} \] Be a parity check matrix. Determine the group code eH: B3 ? B6.
8 M
6 (a)
Determine \[ [(p\Rightarrow q)\wedge q]\Rightarrow \neg p \] is a tautology.
4 M
6 (b)
Define isomorphic graphs. Show that following graphs are isomorphic
8 M
6 (c)
R be a relation on set of integers Z defined by
R={(x,y)|x-y is divisible by 3}
Show that R is an equivalence relation and describe the equivalence classes.
R={(x,y)|x-y is divisible by 3}
Show that R is an equivalence relation and describe the equivalence classes.
8 M
More question papers from Discrete Structures