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: II^nd.

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 ⁿ⁺¹C_r+1 : ⁿC_r : ^n-1C_r-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)ⁿ = aⁿ bⁿ 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)

a_r 7a_r-1 + 10a_r-2 = 3^r, r2

With initial condition a₀ = 0, a₁ =1

 

(b) Solve the recurrence relation

an = a_n-1 + 6a_n-2 with boundary conditions a₀ =3, a₁ = 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: II^nd.

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 ⁿ⁺¹C_r+1 : ⁿC_r : ^n-1C_r-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)ⁿ = aⁿ bⁿ 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)

a_r 7a_r-1 + 10a_r-2 = 3^r, r2

With initial condition a₀ = 0, a₁ =1

 

(b) Solve the recurrence relation

an = a_n-1 + 6a_n-2 with boundary conditions a₀ =3, a₁ = 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)