Shivaji University 2005 B.E Computer Science Discrete Mathematical Structure - university paper

Y-308
SECOND YEAR OF COMPUTER SCIENCE AND ENGINEERING (PART-1) EXAMINATION, 2005
SHIVAJI UNIVERSITY, KOLHAPUR
DiscRETE MATHEMATICAL STRUCTURE

Day and Date: Wednesday, 30-05-2005 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) provide the various properties of binary relations with definitions and examples. [Marks 8]

b) What is POSET? How they are represented? discuss with example.[Marks 8]



Q.4 a) what is function? provide various kinds of functions with examples. [Marks 8]

b) What is semi group? describe subsequent with respect to semi groups. [Marks8]

1. Isomorphism

2. Monomorphism

3. Homomorphism


Q.5 Write a short notes on:[Marks 16=8*2]

1) Algebraic systems

2) Normal and principal normal forms




SECTION-2



Q.6 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.7 a) discuss about the recovery of single fault in group codes.[Marks 8]
b) discuss the linked representation of binary tree.[Marks 8]


Q.8 a) discuss the algorithm of PERT with example.[Marks 8]

b) describe the terms with respect to Graph:[Marks 8]

1.strongly connected

2.unilaterally connected

3.path

4.simple path


Q.9 a) list and describe with examples various kinds of lattices.[Marks 8]


b) Write and discuss with example an algorithm for generating a fault matrix.[Marks 8]



Q.10.Write a short notes on:[Marks 16=8*2]


1. Matrix representation of graphs

2. Compilation of polish expression

Earning:   Approval pending.