@ffi$ffiffiffi

t]SN
2rcs42
)'
'::"\' r'

Fourth Semester B.E. Degree Examination, June/July 2024

Time: 3 hrs. Mnx. Marks: 100

Note: Ansttey anJt Ftl/E futt quesliotts, choosing ONE futt question from etch moclule.
o
O
O
L Ylodule- |
1 a. Dcfine algorithm. Itxplain the fbllorving asymptotic notations:
d i) Ilig On ii) llig Omega iii) Big Thcta (08 N{arks)
o b. Dcsign a uon-recllrsive algorithm to find maxitnum elemeut in an anay oln elements. Give
d
o
the Mathe matical Analysis. (08 Marks)
?u c. Definc time and space complexity. (04 Marks)

OR
ol) 2 a. De sign an algorithrn 1br pcribnning scquential search ancl compute Be st. Worst and Average

d<f
case efficiency. (08 N{arks)

h ul) b. Write an alglrithrn to t-rnrJthe uniquencss of element an array and give mathematical
rrr of this non rccursivc algoritiun ivith steps.
(08 Marks)
oi
-O
analysis
(rrrurJ
Lisf and cxplain
List cxnlain basic asyu-iptotic classcs.
asvu-iototic efficiency classcs. (04 Marks)
c. -
o>
u'2

6o
3a.
(10 Marks)
aO 5,3, 1,9,8,2,4,7
botr b. Apply the topological s

2N
,=
2',a

6-X
o'"
o:
ii -) Fig.Q3(b) (10 Marks)
:e

LO OR
."c 4 a. Writc a C++/JAVA program fbr Mcrgc Sorr. Analyzc its efficiency and apply the same to
sort the tbllowing nuntbers :4. 9,0, *1, 6, 8.9,2,3,12. (10 Marks)
o"
F>a; b. Writc a recursil,cl algorithm tbr Binary Search and also bring out its efficiency. (10 Marks)
=D
o
(r< Module-3
:
Apply greedy merhod to obtain an optimal solution to the knapsack problem given M 60'
-i ci 5 a.
o w - i5. 10.20.30.401
z P = l-10. 20. 100. 90. l60i
(10 Marks)
E Fincl total pr-otit earnecl.
E

1 of3
 2lcs42
following graph Fig.Qs(b). Assume
b" Appiy single source shoftest path algorithm to the
vertex'a' as source.

(10 N{arks)
Fig.Qs(b)
Fig.Qs(b)

OR
iting of the character g;; * dre table bclow has to be transmitted netr,vork

in a sccured fiIanner
Character i.$.r M R
ProbabilitY 0.4 0.2 U.J ,0:l
i) Construci l-luffinarr tree
ii) nevice tlutfinan codes lor the given characters
iii)gn.oA" thc tcxt : RAMA*RAMAR (10 Marks)
iv) Decodc the text : 1000101 problem with
the job sequencing with dcad line
b. Find thc optirnal sotution usrng greedy fur
followrngvalucs: , : ,
Ji
r

Job Jr ,I,yt J: J+

10 3',i JJ 11 10
Profit
J /. 7
Dead line 1 1
(10 Marks)

Module-4
1a,DcfirrcaMu1tistageGraplr.Giu"unmxplainthetcc1rniqueoffirrdingtlreminimum (10 Marks)
cost path in u *,l"tistugc graph' graph'
the gii'en
write Floy,t,;';g";frrr,"o und find all pair Shortest path for
fRef'er
b.
Fie.Q7(b)l

(10 Marks)
Fie.Q7(b)

OR
salcs person problem fbr the following
8a. Apply the Dynamic Prcgrarnn:ring to solve: travelling
graph shown in Fig.Q8(a).
ctz 3 4
I 0 10 15 2A
2 5 0 9 10
J 6 13 0 t2
L) 0
4 8 8
(10 Marks)
Fig.Q8(a)
the algorithtrr to find the pattern
b. Write Llorspool Afioiitirm lor string t,atching. Tracc
"E,LECTION" in the text. (10 Marhs)
..EDUCATION ONLY I-IELI'S IN SELE,CTION."

2 of 3
 2lcs42

Module-5
9a. Construct the state-space tree for sum of subsct problem given the following data:
W:{3,5,6,7} andrn:l5. (loMarks)
b. Write C++ / JAVA program to finc1 all I{arniltonian cyclcs in a connectecl unclirectecl Graph
G of n verticcs rising backtracking principle . (10 Marks)

OR
10 a. concept. Apply Ilranch and Bouncl to the lbllowing instance of
collccpt.
Explain Branch and Bound corlccpt. of
assignrncnt problem.
lem.
.Iob i Job2 Job3 .lob4
Person A 9 7 8
Person B U ::::,
4 J 7
Pemon C l.5,,,,,"'" 8 1 8
Person f) 1 4
6 9
(10 Marks)
b. Explain tlrc lollowing c()llcepts :

i) Graph coloring problcm rvith an cxanrple

,<
,< ****
rk * {. rl. "?i',.,'

t..

3 of 3