North Maharashtra University 2011 B.E Computer Science and Engineering .s.ecomputer - exam paper
<3 p ref> t rrf O M */ -7 n
DISCRI IT STRLCTl'Rl* AND GRAPH THKOKV (New)
P P&ges . 3 Tune * 3 Hours
Max Mark* 100
/ tk* not write anything on quest urn paper except your Seat Number
Instructions
2) Attempt all five question \
J) From each question attempt any two sub questions (/ram a. b, c > such that every question is attempted for maximum of 20 marks.
4) Assume suitable data wherever necetsary.
5) Draw neat diagram wherever necessary
mathematics, 21 study physic*. 12 studboth mathematics and physic* Ml the student studying neither tmthematu npr phyncs are studying b*4of> Find 1) How many arc itudying biology 1
2) How many not studying chemistry are studying nadwmfto N* hoi pfcystcs ? J) Haw many &k1ctH arc oudymg neither mathemtfic w* ptoywei nor chawsary
10
b) Student A takes his examination in 4 subjects COM. DCOM. VC + *d VJ++. He estupates tus chance of paattftf in COM ** 4/5 DCOM as 3/4. in VC-M- as 5/6, in VJ-m- 2/3 To qualify, he must pus COM and t least two other subjects What is the probability that he qualifies *
10
c) i) Use the mathematical induction to show that
I3 23 .... n3 (I 2 . . n)J ii) Explain set operation with suitable Vann diagram and example of each
UNIT - 11 *f Define transitive closure. State and c&platn the War*haH* algorithm to find out transitive closure with suitable example 1
Vi
|
- 06 |  |
p;rf,
10
function f, g. h, s be function from X to X given by f* {(1,2), (2, 3), (3, I)} g* {(1.2), (2. 1). (3, 3)} h* {(1, 1), (2.2), (3. I)}
{(1, 1). (2, 2). (3, 3)}
-pr?H
Find fog. gof Are they equal ?
Find fogoh and fohog Find sog and foa.
c) i) State and explain binary relation and all the properties with suitable example.
ii) Let As(t,b,c)
R * {(, a), (b, b), (b, c), (c, b), (c. e)).
whether
3. a) Find the shortest path using Dijkstras algorithm between vertex a to z.
10
1)6
 |
Mi '* |
b) Const met a optimal binary search tree for weight tcquence 1.2,3,0, 15,17, 23,29.
Also find the prefix code using Huffman algorithm, t) Explain :
i) Hamiltonian path and circuit
ii) Prim's algorithm for minimum spanning tree.
UNIT - IV v
a) Define and explain the following :
t) Group
ii) Ring
iii) Integral domain and field
iv) Group homomorphism.
b) Explain time complexity of algorithm Write the shortest path algtvitii Give the time complexity for hottest path algorithm and bubble tori
'**%
10
10
10
10
11 f (1 hgr il lullp. ShoVi, thjl lufV U
homomorphism if G is an abelian ii) Prove that finite integral domain is field
irmr v-
a) Define lattice. Explain properties of algebraic system defined by lattice, p) Perform the following conversion ;
*
4
10
10
5,
(
(
(
(
(45.I5)I0
(2AB)|6
dioion)2
(347)|
(2EA)l6
yi
>io
ho
>10
( ) -
I
<c) i) E-xpUtn Boolean function and Boolean expression. ; -i) Write CNF and DNF for (unction
I f0. 1.3, 9, 13)>
ul
'ftp
|
Attachment: |
| Earning: Approval pending. |
