Total No. of Questions: 8] SEAT No.
8
23
PA-1242 [5925]-265
[Total No. of Pages : 4
i c-
S.E. (IT)
t at
3s
DISCRETE MATHEMATICS
3:2
(2019 Pattern) (Semester-III) (214441)
02 91
3:5
Time : 2½ Hours] [Max. Marks : 70
0
31
2/0 13
Instructions to the candidates:
1) Answer Q.1, or Q2, Q3 or Q4, Q5 or Q6, Q7 or Q8.
0
2/2
2) Figures to the right indicate full marks.
.23 GP
E
80
8
Q1) a) Find the Shortest Path algorithm using Dijikstra’s Shortest path algorithm.
C
23
[6]
ic-
16
tat
8.2
3s
.24
3:2
91
49
3:5
30
31
01
02
2/2
GP
2/0
b) Construct an optimal tree for the weights 3, 4, 5, 6, 12 Find the weight
CE
80
8
of the optimal tree. [6]
-23
.23
c) Find the maximum flow for the following transport network. [6]
tic
16
sta
8.2
:23
.24
1
:53
49
9
13
0
2/0 13
023
0
2/2
.23 GP
OR
CE
80
Q2) a) Define Following with examples: [6]
16
i) rooted tree
8.2
ii) Spanning tree
iii) Binary Tree
.24
49
P.T.O.
b) Use nearest Neighbourhood method to solve Travelling Salesman
8
problem. [6]
23
i c-
t at
3s
3:2
02 91
3:5
0
31
2/0 13
0
2/2
.23 GP
E
80
8
C
23
c) Explain Hamiltonian and Euler path and circuits with example. [6]
ic-
16
tat
8.2
Q3) a) X = {2, 3, 6, 12, 24, 36} and x<=y iff x divides y. Find [6]
3s
i) Maximal Element
.24
3:2
91
ii) Minimal Element
49
3:5
iii) Draw the graph and its equivalent hasse diagram for divisibility on
30
31
the set: {2, 3, 6, 12, 24, 36}.
01
02
b) What are the ordered pairs in the relation R represented by the directed
2/2
GP
graph shown in below Figures? [6]
2/0
CE
80
8
-23
.23
tic
16
sta
8.2
:23
.24
1
:53
49
c) Let functions f and g be defined by [5]
13
0
2/0 13
f (X) 2X 1,g(X) X 2 2
023
0
Find
2/2
.23 GP
i) gof (4) and fog (4)
ii) gof (a+2) and fog (a+2)
CE
80
iii) fog (5)
iv) gof (a+3)
16
v) gof (a+4)
8.2
OR
.24
[5925]-265 2
49
Q4) a) What is the reflexive closure of the relation R = {(a, b) | a<b} on the set
8
of integers and symmetric closure of the relation R = {(a,b) | a>b} on the
23
set of positive integers? [6]
i c-
t at
b) Determine whether the relations for the directed graphs shown in Figure
3s
are reflexive, symmetric, antisymmetric, and/or transitive. [6]
3:2
02 91
3:5
0
31
2/0 13
0
2/2
.23 GP
c) Let X = {a, b, c). Define f: X->X such that f ={(a,b), (b, a), (c, c)} [5]
E
80
8
Find
C
23
i) f-1
ic-
16
ii) f-1 of
tat
8.2
3s
iii) fof-1
.24
3:2
91
49
Q5) a) Solve the congruence 8x = 13mod 29 [6]
3:5
b) For each pair of integer a and b, find integers q and r such that
30
31
a = bq + r such that 0 <= r <|b|, where a is dividend, b is divisor, q is
01
02
quotient and r is remainder. [8]
2/2
GP
i) a = -381 and b=14
2/0
ii) a = -433 and b = -17
CE
c) Find all positive divisors of [4]
80
8
-23
i) 256 = 28
.23
ii) 392 = 23. 72
tic
16
sta
OR
8.2
Q6) a) Which of the following congruence is true? Justify the answer. [6]
:23
.24
i) 446 278 (mod 7)
1
:53
49
ii) 793 682 (mod9)
9
13
iii) 445 536 (mod 18)
0
2/0 13
b) Compute GCD of the following using Euclidian algorithm. [6]
023
i) GCD (2071, 206)
0
2/2
.23 GP
ii) GCD (1276, 244)
c) Using Chinese Remainder Theorem, find the value of P using following
CE
80
data. [6]
p=2 mod 3
p=2 mod 5
16
p=3 mod 7
8.2
.24
[5925]-265 3
49
Q7) a) Let R = {0o, 45o, 90o, 135o, 180o, 225o, 270o, 315o} and *= binary
8
operation, so that a*b is overall angular rotation corresponding to
23
successive rotations by a and then by b. Show that (R,*) is a Group.
i c-
[9]
t at
b) Let l be the set of all integers. For each of the following determine whether
3s
*is an commutative operation or not: [8]
3:2
02 91
i) a*b=max(a,b)
3:5
ii) a*b=min(a+2,b)
0
31
2/0 13
iii) a*b=2a-2b
iv) a*b= min (2a-b, 2b-a)
0
2/2
v) a*b= LCM (a,b)
.23 GP
vi) a*b=a/b
vii) a*b=power (a,b)
E
80
8
C
23
viii) a*b=a 2 + 2b+ab
ic-
OR
16
Show that set G of all numbers of the form a+b 2, a, b l forms a
tat
Q8) a)
8.2
group under the operation addition i.e.(a+b 2) + (c+d 2) = (a+c) +
3s
(b+d) 2.
.24
3:2 [9]
91
b) Determine whether the set together with the binary operation is a
49
3:5
semigroup, group a monoid, or neither.
30
31
S= {1, 2, 5, 10, 20}, where a*b is defined as GCD (a,b) [8]
01
02
2/2
GP
2/0
CE
80
8
-23
.23
tic
16
sta
8.2
:23
.24
1
:53
49
9
13
0
2/0 13
0 23
0
2/2
.23 GP
CE
80
16
8.2
.24
[5925]-265 4
49
