Dr Bhim Rao Ambedkar University 2007 B.Tech Information Technology Discrete Mathmatical structure - Question Paper

Y-308
SECOND YEAR OF COMPUTER SCIENCE AND ENGINEERING (PART-1) EXAMINATION, 2007
DiscRETE MATHEMATICAL STRUCTURE
Total Marks: 100
Time: 3.00p.m. To 6.00p.m.

Instructions: 1) Attempt any 3 ques. from every part.

2) Figures to right indicate full marks.


SECTION-1


Q.1 a) what is well-formed formula? provide any 4 examples which are not well-formed formula.[Marks 6]

b) describe tautology. State whether subsequent are tautology or not.[Marks 6]

1. Sun rises at east.

2. provide me a book

3. Today is Sunday

4. Earth moves around the sun

c) provide the scheme to convert infix notation to prefix notation.[Marks 6]



Q.2 a) provide various kinds of operations on sets with example. [Marks 8]

b) provide the pointers and linked allocation of discrete structures. [Marks 8]



Q.3 a) indicates the subsequent implications:[Marks 8=4*2]


1) (P IMPLIES Q) IMPLIES Q = P OR Q

2) ((P OR ~P) IMPLIES Q) IMPLIES ((P OR ~P) IMPLIES R)=(Q IMPLIES R)


b) Draw the Hasse diagram of the subsequent sets under the partial ordering relation ’divides’.[Marks 8]

1) {1, 2, 3, 6, 12}

2) {3, 9, 27, 54}





Q.4 Write a short notes on:[Marks 18=6*3]

1) Partitions and covering of set

2) POSET and Hasse diagram

3) Normal and principal normal forms



SECTION-2

Q.5 a) describe the lattices as a POSET. describe greatest lower bound and lowest upper bound with examples.[Marks 8]

b) describe group. describe and provide examples of various kinds of groups.[Marks 10]


Q.6 a) discuss about the recovery of single fault in group codes.[Marks 8]
b) discuss the linked representation of binary tree.[Marks 8]


Q.7 a) derives the reverse polish expression for the subsequent expressions: :[ Marks 8=4*2]

1) a + (b/c) *d

2) (a + b) (c + d/e) * f


b) What is diagraph? describe the following:[Marks 8]

1. asymmetric diagraph

2. converse of a diagraph

3. reflexive diagraph


Q.8 a) describe the subsequent w.r.t groups:[Marks 8=2*4]

1. Order

2. Identity

3. Abelian

4. Degree

b) Let I be the set of integers. Prove that the algebraic system (I, +)is abelian group.[Marks 8]

Earning:   Approval pending.