1(a)
Consider the set A={1, 2, 3, 4, 5, 6} under the multiplication modulo 7.

i) Find the multiplication tabel for the above

ii) Find the inverse of 2,3 and 5,6

iii) Prove that it is a cyclic group

iv) Find the orders and the subgroups generated by {3, 4} and {2, 3}

i) Find the multiplication tabel for the above

ii) Find the inverse of 2,3 and 5,6

iii) Prove that it is a cyclic group

iv) Find the orders and the subgroups generated by {3, 4} and {2, 3}

8 M

1(b)
Determine the number of integers between 1 and 250 that are divisible by any of the intergers 2, 3, 5 and 7.

6 M

1(c)
Suppose that A is non empty set, and f is a function that has A as it's domain . Let R be the relation on A consisting of all ordered pairs (x, y) where f (x) = f (y). Show that R is an equivalence relation on A.

6 M

2(a)
Given S={1, 2, 3, 4} and a Relation R on S given by R={(4,3), (2, 2), (2, 1), (3, 1), (1, 2)}

i) Show that R is not transitive

ii) Find transitive closure of Rby Warshall's algorithm

i) Show that R is not transitive

ii) Find transitive closure of Rby Warshall's algorithm

8 M

2(b)
Show that n(n

^{2}-1) is divisible by by 24, where n is any odd positive integer.
6 M

2(c)
Prove that a connected graph with n vertices must have at least n-1 edges. Can a single undirected graph of 8 vertices have 40 edges excluding self loop.

6 M

3(a)
Find the ordinary generating functions for the given sequences:

i) {0, 1, 2, 3, 4,......}

ii) {1, 2, 3, 4, ......}

iii) {0, 3, 32,33,.....}

iv) {2, 2, 2, 2......}

i) {0, 1, 2, 3, 4,......}

ii) {1, 2, 3, 4, ......}

iii) {0, 3, 32,33,.....}

iv) {2, 2, 2, 2......}

8 M

3(b)
Functions f, g, h are defined on a set, X={1, 2, 3} as [6] f={(1,2), (2, 3), (3, 1)}. g= {(1, 2), (2, 1), (3, 3)}. h= {(1, 1), (2, 2), (3, 1)}.

i) Find f o g , go f, are they equal?

ii) Find f o go h and f o h o g

i) Find f o g , go f, are they equal?

ii) Find f o go h and f o h o g

6 M

3(c)
For each of the following sets of weights construct an optimal binary prefix code. For each weight in the set give the corresponding code word:

i) 1,2,4,6,9,10,12 ii) 10,11,14,16,18,21 iii) 5,7,8,15,35,40.

i) 1,2,4,6,9,10,12 ii) 10,11,14,16,18,21 iii) 5,7,8,15,35,40.

6 M

4(a)
Show that the (2,5) encoding function e: B

^{2}→B^{5}defined by e(00)=00000 e(01)=01110 e(10)=10101 e(11)=11011 is a group code . How many errors will it detect?
8 M

4(b)
Prove the following (A-B) (B-A) = (AU B)- (An B)

6 M

4(c)
Let T be the set of all even integers. Show that (Z, +) and (T, +) are isomorphic.

6 M

5(a)
Determine the matrix of the partial order of divisibility on the set A= {1, 3, 5, 15, 30}. Draw the Hasse diagram of the poset. Indicate whether it is a chain or not?

8 M

5(b)
Define Hamiltonian path and circuit with example. What is the necessary and sufficient condition to exist Hamiltonian circuit?

6 M

5(c)
Find the solution of a

_{r+r}+2a_{r+1}-3a_{r}=0 that satisfies a_{0}=1, a_{1}=2
6 M

6(a)
Determine whether the following posets are Boolean algebra. Justify your answers.

i) A={1, 2, 3, 6} with divisibility

ii)D20: divisor of 20 with divisibility

i) A={1, 2, 3, 6} with divisibility

ii)D20: divisor of 20 with divisibility

8 M

6(b)
Define Universal and Existential quantifiers?Explain with examples.

6 M

6(c)
Prove that the set G={0, 1, 2, 3, 4, 5} is an Abelian group of order 6 with respect to addition modulo 6.

6 M

More question papers from Discrete Structures