Deemed University 2011 B.Tech Computer Science and Engineering University: Lingayas University Term: V Title of the : Discreate Structure - Question Paper
Roll No. ..
Lingayas University
B.Tech. 2nd Year (Term V)
Examination Feb 2011
Discrete Structure (CS - 203)
[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: All questions carry equal marks. Attempt five questions in all. Question no. 1 is compulsory. Select two questions from Section B and two questions from Section C.
Section A
Q-1. Part A
Select the correct answer of the following multiple choice questions. [10x1=10]
(i) Given that proposition p is false, proposition q is true and proposition r is false, determine whether each proposition is true or false.
(a) ~p v ~q (b) ~pvq (c) pvq (d) ~pv~(qnr)
(ii) If there are 64 terminal nodes in a complete binary tree then total no. of nodes in this tree will be:
(a) 64 (b) 128 (c) 32 (d) 27
(iii) Which of the following statements are true
(a) {{}} (b) {} (c) a{a} (d) 2{1, {2}} (iv) Let R be a relation represented by the matrix
MR=
then
MR-1= 
,
for (k,l) equal to
(a) (1,0) (b) (0,0) (c) (0,1) (d) ( 1,1 )
(v) Let A: {1,2,3}, B= {a,b,c,d}. In each case, state whether the function f = {( l, a), (2,b)} is
(a) injective (b) surjective (c) Bijective (d) none of these
(vi) The sets {3,2,2}, {x|x is a integer and 1 <3} are
(a) Equal (b) subset of each other (c) either (d) none of the above
(vii) The number of ways that five distinct Martians and five distinct Jovians wait in line is
(a) C(5,5) (b) P(5,5) (c) 5! x 2 (d) 10!
(viii) The set {l, i) under multiplication is a sub group of multiplicative group { l,-1,i,-i} is
(a) Possible (b) impossible (c) either (d) none of these
(ix) If (R,+) is an abelian group then the ring containing at least two elements is a field, is
(a) Possible (b) impossible (c) either (d) none of these
(x) The number of vertices for the graph which contains l6 edges & all vertices of degree 2 is
(a) 16 (b) 17 (c) 18 (d) 19
Q-1. Part - B (5x2=10)
(i) On the set N of all nature numbers define the operation * on N by x * y = g c d (x, y) for all x and y N then prove that
(a) * is commutative (b) * is Associative
(ii) Define & explain the following:
(a) Tree, Binary tree, Forest
(b) Path, Simple path
(c) Planer graph
(d) Isomorphic graph
(e) Cyclic group, Normal subgroup, Rings
Section - B
Q- 2. (i) In a class, l8 students offered physics; 23 offered chemistry and, 24 offered mathematics. Of these, 13 are in both chemistry and mathematics; 12 in physics and chemistry; 11 in mathematics and physics and 6 in all the three subjects. Find:
(a) How many students are there in class?
(b) How many offered mathematics but not chemistry;
(c) How many are taking exactly one of the three subjects? (10)
Q-2.(ii)
Let A
B and CD, is
it always the case that (A U C) is a sub set of (B U D)? Justify this result
using general method. (10)
Q-3. (i) Prove that each of the following is a tautology: (10)
(a) ((pq)(qr)) (pr)
(b) ~(pq) p
(ii) For any sets A,B,C and D prove that:
(AXB)(CXD) = (AC) X (BD) (10)
Q4 (i) Show that relation 'Divides' defined on the set of natural numbers is a partial order relation and write POSET for this. (10)
(ii) Suppose that the population of a city is 120 at time n=0 and 160 at time n=1. The population increase from time n-1 to time n is twice the increase from time n-2 to time n-l. Find a recurrence relation and the initial conditions for the population at time n and then find the explicit formula for it. (10)
Section C
Q-5. For the given graph in the adjacent figure; find out its Adjacency matrix & Incidence matrix. Also make all the possible spanning trees of this graph and then find minimal spanning tree by using Kruskals algorithm. (20)
Q-6.(i) Sate Konigsberg bridge problem. What is the solution of this problem? Elaborate. (10)
(ii) State Euler's formula for connected planner graphs and illustrate it for two such graphs. (10)
Q7. Different between Euler circuit and Hamilton circuit and draw the graphs such that: (10)
(a) It is Euler circuit and not Hamilton circuit
(b) It is Hamilton and not Euler circuit
(c) It is both
(ii) Consider the group G: {1,2,3,4,5,6,7,8} under multiplication module 9. Find: (10)
(a) Multiplication table of G
(b) 4-1,5-1 and 6-1
(c) Orders and subgroups generated by 3 and 4
(d) Is G cyclic? then mention its generator
Q-8. (i) Determine the numeric function corresponding to the generating function. (5)
G(x)=
(ii) Solve the following recurrence relation;
an+1 + (n+1) an = (n+1)! for n0, a0 =3 (5)
(iii) Construct a binary search tree in which elements are inserted one by one in following order: 100, 110, 90, 94, 120, 105, 96, 92, 80, 110, 110, 125, 112, 140 and then delete the following elements one by one from constructed tree: 112, 125, 90, 92, 94, 105. (10)
Roll No. ..
Lingayas University
B.Tech. 2nd Year (Term V)
Examination Feb 2011
Discrete Structure (CS - 203)
[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: All questions carry equal marks. Attempt five questions in all. Question no. 1 is compulsory. Select two questions from Section B and two questions from Section C.
Section A
Q-1. Part A
Select the correct answer of the following multiple choice questions. [10x1=10]
(i) Given that proposition p is false, proposition q is true and proposition r is false, determine whether each proposition is true or false.
(a) ~p v ~q (b) ~pvq (c) pvq (d) ~pv~(qnr)
(ii) If there are 64 terminal nodes in a complete binary tree then total no. of nodes in this tree will be:
(a) 64 (b) 128 (c) 32 (d) 27
(iii) Which of the following statements are true
(a) {{}} (b) {} (c) a{a} (d) 2{1, {2}} (iv) Let R be a relation represented by the matrix
MR=
then
MR-1= 
,
for (k,l) equal to
(a) (1,0) (b) (0,0) (c) (0,1) (d) ( 1,1 )
(v) Let A: {1,2,3}, B= {a,b,c,d}. In each case, state whether the function f = {( l, a), (2,b)} is
(a) injective (b) surjective (c) Bijective (d) none of these
(vi) The sets {3,2,2}, {x|x is a integer and 1 <3} are
(a) Equal (b) subset of each other (c) either (d) none of the above
(vii) The number of ways that five distinct Martians and five distinct Jovians wait in line is
(a) C(5,5) (b) P(5,5) (c) 5! x 2 (d) 10!
(viii) The set {l, i) under multiplication is a sub group of multiplicative group { l,-1,i,-i} is
(a) Possible (b) impossible (c) either (d) none of these
(ix) If (R,+) is an abelian group then the ring containing at least two elements is a field, is
(a) Possible (b) impossible (c) either (d) none of these
(x) The number of vertices for the graph which contains l6 edges & all vertices of degree 2 is
(a) 16 (b) 17 (c) 18 (d) 19
Q-1. Part - B (5x2=10)
(i) On the set N of all nature numbers define the operation * on N by x * y = g c d (x, y) for all x and y N then prove that
(a) * is commutative (b) * is Associative
(ii) Define & explain the following:
(a) Tree, Binary tree, Forest
(b) Path, Simple path
(c) Planer graph
(d) Isomorphic graph
(e) Cyclic group, Normal subgroup, Rings
Section - B
Q- 2. (i) In a class, l8 students offered physics; 23 offered chemistry and, 24 offered mathematics. Of these, 13 are in both chemistry and mathematics; 12 in physics and chemistry; 11 in mathematics and physics and 6 in all the three subjects. Find:
(a) How many students are there in class?
(b) How many offered mathematics but not chemistry;
(c) How many are taking exactly one of the three subjects? (10)
Q-2.(ii)
Let A
B and CD, is
it always the case that (A U C) is a sub set of (B U D)? Justify this result
using general method. (10)
Q-3. (i) Prove that each of the following is a tautology: (10)
(a) ((pq)(qr)) (pr)
(b) ~(pq) p
(ii) For any sets A,B,C and D prove that:
(AXB)(CXD) = (AC) X (BD) (10)
Q4 (i) Show that relation 'Divides' defined on the set of natural numbers is a partial order relation and write POSET for this. (10)
(ii) Suppose that the population of a city is 120 at time n=0 and 160 at time n=1. The population increase from time n-1 to time n is twice the increase from time n-2 to time n-l. Find a recurrence relation and the initial conditions for the population at time n and then find the explicit formula for it. (10)
Section C
Q-5. For the given graph in the adjacent figure; find out its Adjacency matrix & Incidence matrix. Also make all the possible spanning trees of this graph and then find minimal spanning tree by using Kruskals algorithm. (20)
Q-6.(i) Sate Konigsberg bridge problem. What is the solution of this problem? Elaborate. (10)
(ii) State Euler's formula for connected planner graphs and illustrate it for two such graphs. (10)
Q7. Different between Euler circuit and Hamilton circuit and draw the graphs such that: (10)
(a) It is Euler circuit and not Hamilton circuit
(b) It is Hamilton and not Euler circuit
(c) It is both
(ii) Consider the group G: {1,2,3,4,5,6,7,8} under multiplication module 9. Find: (10)
(a) Multiplication table of G
(b) 4-1,5-1 and 6-1
(c) Orders and subgroups generated by 3 and 4
(d) Is G cyclic? then mention its generator
Q-8. (i) Determine the numeric function corresponding to the generating function. (5)
G(x)=
(ii) Solve the following recurrence relation;
an+1 + (n+1) an = (n+1)! for n0, a0 =3 (5)
(iii) Construct a binary search tree in which elements are inserted one by one in following order: 100, 110, 90, 94, 120, 105, 96, 92, 80, 110, 110, 125, 112, 140 and then delete the following elements one by one from constructed tree: 112, 125, 90, 92, 94, 105. (10)
| Earning: Approval pending. |
