Deemed University 2010 B.Tech Computer Science and Engineering University: Lingayas University Term: III Title of the : Discrete Structures - Question Paper
Roll No. ..
Lingayas University, Faridabad
Examination May, 2010
Course: B.Tech. Year: IInd.
Semester: III Paper Code:CSE-203E
Subject: Discrete Structures
[Time: 3 Hours] [Max. Marks: 100]
Before answering the question, candidate should ensure that they have been supplied the correct and complete question paper. No complaint in this regard, will be entertained after examination.
Note: Attempt any Five Questions. All questions carry equal marks.
Q-1. (a) Consider the set Z of integers and an integer m>1. In this, x is congruent to y modulo m, written x y(modm), if x-y is divisible by m. Show that this defines an equivalence relation on z. (12)
(b) Explain the terms: (8)
Duality, Cartesian product, Multisets, Composition of relation.
Q-2. (a) If A and B are finite sets, then AB and AB are finite and
n(AB) = n (A) + n (B) n (AB) (8)
(b) What is propositional calculus? Explain with truth table all the basic operations. (7)
(c) Let f be the function from {a, b, c} to {1, 2, 3} such that f (a) =2, f(b) =3 and f (c) =1. Is f invertible and if it is what is its inverse. (5)
Q-3. (a) If n+1Cr+1 : nCr : n-1Cr-1 = 11:6:3, then find the value of n and r? (10)
(b) A question paper has two parts. Part A and Part B each containing 10 questions. If the students has to choose 8 (eight) from part A and 5 (five) from Part B in how many ways can he choose the questions? (10)
Q-4. (a) Prove the theorem:- (G stands for graph) (12)
(i) G is 2 colorable
(ii) G is bipartite
(iii) Every cycle of G has even length
(b) Find the weight of minimum spanning tree using prims Algorithm. (8)
Q-5. (a) Prove that the set E of even integers with zero, is a ring w.r.t addition (+) and multiplication? (8)
(b) Explain the terms monoid, semigroup with examples. (5)
(c) Show that G is abelian if G is a group such that (ab)n = an bn for three consecutive integers n‑ for all a, b G. (7)
Q-6. (a) Show that the following argument is fallacy pq, ~p ~q. (8)
(b) Suppose the following list of alphabets is inserted into binary search tree i.e. (12)
J, R, D, G, W, E, M, H, P, A, F, Q
(i) Find the final Tree T.
(ii) Find the inorder traversal of T.
Q. 7. (a) Solve the recurrence relation by the method of generating function (12)
ar 7ar-1 + 10ar-2 = 3r, r2
With initial condition a0 = 0, a1 =1
(b) Solve the recurrence relation
an = an-1 + 6an-2 with boundary conditions a0 =3, a1 = 6 (8)
Q-8. (a) Explain Isomorphism, Homomorphism and automorphism with the help of suitable example? (8)
(b) Define Welch-Powell algorithm for graph coloring with an example.
(12)
Roll No. ..
Lingayas University, Faridabad
Examination December, 2009
Course: B.Tech. Year: IInd.
Semester: III Paper Code:CSE-203E
Subject: Discrete Structures
[Time: 3 Hours] [Max. Marks: 100]
Before answering the question, candidate should ensure that they have been supplied the correct and complete question paper. No complaint in this regard, will be entertained after examination.
Note: Attempt any Five Questions. All questions carry equal marks.
Q-1. (a) Consider the set Z of integers and an integer m>1. In this, x is congruent to y modulo m, written x y(modm), if x-y is divisible by m. Show that this defines an equivalence relation on z. (12)
(b) Explain the terms: (8)
Duality, Cartesian product, Multisets, Composition of relation.
Q-2. (a) If A and B are finite sets, then AB and AB are finite and
n(AB) = n (A) + n (B) n (AB) (8)
(b) What is propositional calculus? Explain with truth table all the basic operations. (7)
(c) Let f be the function from {a, b, c} to {1, 2, 3} such that f (a) =2, f(b) =3 and f (c) =1. Is f invertible and if it is what is its inverse. (5)
Q-3. (a) If n+1Cr+1 : nCr : n-1Cr-1 = 11:6:3, then find the value of n and r? (10)
(b) A question paper has two parts. Part A and Part B each containing 10 questions. If the students has to choose 8 (eight) from part A and 5 (five) from Part B in how many ways can he choose the questions? (10)
Q-4. (a) Prove the theorem:- (G stands for graph) (12)
(i) G is 2 colorable
(ii) G is bipartite
(iii) Every cycle of G has even length
(b) Find the weight of minimum spanning tree using prims Algorithm. (8)
Q-5. (a) Prove that the set E of even integers with zero, is a ring w.r.t addition (+) and multiplication? (8)
(b) Explain the terms monoid, semigroup with examples. (5)
(c) Show that G is abelian if G is a group such that (ab)n = an bn for three consecutive integers n‑ for all a, b G. (7)
Q-6. (a) Show that the following argument is fallacy pq, ~p ~q. (8)
(b) Suppose the following list of alphabets is inserted into binary search tree i.e. (12)
J, R, D, G, W, E, M, H, P, A, F, Q
(i) Find the final Tree T.
(ii) Find the inorder traversal of T.
Q. 7. (a) Solve the recurrence relation by the method of generating function (12)
ar 7ar-1 + 10ar-2 = 3r, r2
With initial condition a0 = 0, a1 =1
(b) Solve the recurrence relation
an = an-1 + 6an-2 with boundary conditions a0 =3, a1 = 6 (8)
Q-8. (a) Explain Isomorphism, Homomorphism and automorphism with the help of suitable example? (8)
(b) Define Welch-Powell algorithm for graph coloring with an example.
(12)
Earning: Approval pending. |