Total No.
of Questions : 8]
34)
SEAT No.:ß190 447
P-6551
[TotalNo. of Pages :3
[6181)-101
B.E. (Computer Engineering)
DESIGN AND ANALYSIS OF ALGORITHM
Time : 2 Hours]
(2019Catten)(Semester-I) (410241)
[Max. Marks : 70
Instructions to the canidate_
1) AnswerQl,or 003 or Q4, 5 or 06, 07 or 98.
2) NeatdiagYamssiust be drawn wherever necessary.
3) Fighrèyto thg right indicate full marks.
4) A__une suttable data, if necessary.
Q1) a) Writg 1igh-leveldescription ofjob sequencing algorithm. Letnumber of
jobsfh)=5;Profit vector P={20, 15, 10, 5, 1); Dadline vector D={2, 2,
1,3, 3) Find the feasible solutions, What i_ the optimal solution and
maximum profit? 191
b) Consider the following instance
Y 33
afde
.905
knpsáck problem. Find the optima'
/1
solution by using dynamic progranming approach.
Item Weight Profit
1 2 $12
2 1
3 3 $20
:31:41
4 2 $15
Capacity of the knapsask'= 5.
OR
Q2) a) What is Job scheduling algorithm? How job schedulingalgoritfai can be
solved using Greedy algorithmic approach? Explainyour, pswer with
respect to Principle, control abstraction, timágnalys"
C 33.113.95
EÜ 3 0 / 1 of control
N
abstraction, of greedy approach for the following instanç of Knapsack
problem. [12]
Each job is associated with adeadline and profit.
Job
Deadline 2 1 3 2 1
Profit 60 100 20 40 20
b) Write steps for Greedy approach for Jok séquencing. [6j
PI0.
03) a) What is branch and bound algorithmic strategy?
Apply branch n bount
algorithmic strategy to solve traveling salesman problem for [9]
10
15
3.95go/1
30
35
b) Eplain with suitable example Backtracking:
time anatysis of control abstraction. Principle, control abstraction,
[8]
OR
04) a) Explain the 'branch and bound' appo¡ch
branch and bound algorithm for sejvang theforsolving
0/1
problems. Write a
the sane algorithm to solve Knapsack problem. Use
capacity of the knapsack is 15thetloytog
kg.
o/1 Knapsack problem. The
Item A B CD [9]
|Profit(Rs.) 18 I0 T2 10.
Weight (Kg.)| 9 43
b) What is sum of subsetppoblem? Solve sum
instance using backtrac7iûg approach ofsubset problem for following
[8]
Input: set[ ]= {2, 3, 5,6,8, 10}, sum = 10
05) a) What is amortized analysis? Explain the
aggregate method with exanple.[9j
b) What is Potential function method of
amortized
30/1 illustrate
Potential method, find amortized cost of PUSH POP and MULTIPOP
stack operations.
OR
26) a) What are special needs of embedded algoithmR Whichsorting algorithm
is best for embeddedsystems? Why? [6]
b) Explain Randomized and Approximate algoithms. [4]
[6181]-101 2
c) What is randomized algorithm? Give any example of randomized algorithm?
Also explain Random variable,l:41
Binomial random variable and-Mathematics
for Randomized algorithm. [8]
ey a) ) Explain an algorithm{or Distributed Minimum Spanning Tree.
Write andplainRabin-Karp algorithm for string matching. [10|
b) With respo@to'Multnthreaded Algorithms explain Analyzing multithreaded
[7]
algorithms Paraèl loops, Race conditions.
OR
08) a) Write anhexplain pseudo code for Multi-threaded merge sort algorithm.
How paallel merging gives asignificant parallelismadvantage over Merge
[9!
Sorg EGNO188e
ig.93,30/1l/2029
many spurious hits
b) For string matching, working module q = E how
T=31415926535....[8]
does the Rabin- Karp matcher enconers in Text
T=31415926535
i)
P=26
i) Here [Link] =14s0
iv) And Pmod Q3 mod?i
=4 1:41
Now findthe exactatch of Pmod Q..
v) 13:3
CEGNO18801
30/11/2023
157.33.I13.95
|6181]-101