STUPIDSID
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(n2-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: 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?
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 ar+r+2ar+1-3ar=0 that satisfies a0=1, a1=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