Total No. of Questions : 8] SEAT No.

8
23
P3147 [Total No. of Pages : 3

ic-
[6004]-480A

tat
B.E. (Computer Engineering)

6s
3:3
DESIGN ANALYSIS OF ALGORITHMS

02 91
4:4
(2019 Pattern) (Semester - VII) (410241)

0
31
Time : 2½ Hours]
1/0 13 [Max. Marks : 70
0
6/2
Instructions to the candidates:
.23 GP

1) Solve Q.1 or Q.2, Q.3 or Q.4, Q.5 or Q.6, Q.7 or Q.8.

E

2) Neat diagrams must be drawn wherever necessary.

82

8
C

23
3) Figures to the right indicate full marks.

ic-
4) Assume suitable data, if necessary.
16

tat
8.2

6s
Q1) a) Consider the following instance of the knapsack problem. Find the
.24

3:3
optimal solution by using dynamic programming approach. [10]
91
49

4:4
Item Weight Profit
30
31

1 2 $12
01
02

2 1 $10
6/2
GP

3 3 $20
1/0
CE

4 2 $15
82

8
23
Capacity of the knapsack = 5.
.23

ic-
16

b) What is job scheduling algorithm? How job scheduling algorithm can be

tat
8.2

solved using Greedy algorithmic approach? Explain your answer with

6s

respect to Principle, control abstraction, time analysis of control

.24

3:3
91

abstraction, of greedy approach for the following instance of knapsack

49

4:4

problem. [8]
30
31

Each job is associated with a deadline and profit.

01
02

Job J1 J2 J3 J4 J5
6/2
GP

Deadline 2 1 3 2 1
1/0
CE

Profit 60 100 20 40 20
82
.23

OR
16

Q2) a) What is greedy approach? Explain Job scheduling algorithm using Greedy
8.2

approach for following examples. Give the sequence of job scheduling.

.24

[8]
P.T.O.
49
 Input: Four jobs with following deadlines and profits

8
23
Job1D deadline Profit

ic-
a 4 20

tat
b 1 10

6s
c 1 40

3:3
02 91
d 1 30

4:4
Input: Five Jobs with following deadlines and profits

0
31
Job1D 1/0 13
Deadline Profit
0
a 2 100
6/2
.23 GP

b 1 19
c 2 27
E
82

8
C

23
d 1 25

ic-
e 3 15
16

tat
8.2

6s
b) What is optimal binary search tree? How dynamic programming approach
.24

3:3
is used to build OBST for following tale. [10]
91
49

4:4
1 2 3 4
30
31

Keys→ 10 20 30 40
01
02

Frequency→ 4 2 6 3
6/2
GP
1/0

Q3) a) Explain with suitable example Backtracking: Principle, control

CE
82

8
abstraction, time analysis of control abstraction. [8]

23
.23

b) Compare between greedy method and dynamic programming with

ic-
16

respect to. [9]

tat
8.2

i) Feasibility.
6s
.24

3:3

ii) Optimality.
91
49

iii) Recursion.
4:4
30

iv) Memorization.
31
01

v) Time complexity.
02
6/2

OR
GP
1/0

Q4) a) What is sum of subset problem? Solve sum of subset problem for
CE

following instance using backtracking approach. [8]

82

Input : set [] = {2, 3, 5, 6, 8, 10}, sum = 10

.23

b) What is Branch and Bound method? Write control abstraction for Least
16

cost search? [9]

8.2
.24

[6004]-480A 2
49
Q5) a) What is amortized analysis? Explain aggregate and potential function

8
23
methods used for amortized analysis with respect to stack operations?[9]

ic-
b) What is potential function method, of amortized analysis? To illustrate

tat
potential method, find amortized cost of PUSH, POP and MULTIPOP

6s
stack operations. [9]

3:3
02 91
OR

4:4
0
Q6) a) Write short notes on the following. [10]

31
1/0 13
i) Aggregate analysis.
0
6/2
.23 GP

ii) Accounting Analysis.

iii) Potential function method.
E
82

8
iv) Tractable and Non-tractable problems.
C

23
ic-
b) Write short notes on with suitable example of each. [8]
16

tat
i) Randomized algorithm.
8.2

6s
.24

ii) Approximation algorithm.

3:3
91
49

4:4
30
31

Q7) a) Write and explain pseudo code for multi-threaded merge sort algorithm.
01

How parallel merging gives a significant parallelism advantage over merge

02

Sort? [9]
6/2
GP
1/0

b) i) Explain an algorithm for Distributed Minimum Spanning Tree. [8]

CE
82

ii) Write and explain Rabin-Karp algorithm for string matching.

8
23
.23

OR
ic-
16

tat
Q8) a) Write short notes on the following. [10]
8.2

6s

i) Multithreaded matrix multiplication.

.24

3:3
91

ii) Multithreaded merge sort.

49

4:4
30

iii) Distributed breadth first search.

31

iv) The Rabin-Karp algorithm.

01
02
6/2

b) With respect to Multithreaded Algorithms explain Analyzing

GP

multithreaded algorithms, Parallel loops, Race conditions. [7]

1/0
CE
82
.23

  
16
8.2
.24

[6004]-480A 3
49