tt'

(i
tr
i*
c)

#
F,.

USN 15CS43

Fourth Semester B.E. Degree Examinationo June/July 2017

Design and Analysis of Algorithms
Time: 3 hrs. Max. Marks: 80
Note: Answer FIVE full questions, choosing one full question from each module.
(,
.*O
{-)
()
Fa
\v Module-1
g t<

1a. Define algorithm. Explain asymptotic notations, Big O, big Omega, big theta notations.
d
F<
x
(/) (08 Marks)
N
'o() b. Explain general plan of mathematical analygis of nonrecursive algorithms with example.
t)
d
0)
(08 Marks)
' {-)t<
ER
oo*
6d -a OR
().;-i
-vB (< a. Define time and space complexity. Explain important problem types. (08 Marks)
b.
F
(9 r-''r
5\n Illustrate mathematical analysis of recursive algorithm for towers of hanoii. (08 Marks)
oo ll
coo
.- I

.= c\
d\f, Module-2
hbo a. Explain concept of divide and conquer. Write merge sort algorithm.
!

X() (08 Marks)

(.) C
-C)
=ftr l<h
b. Write a recursive algorithm for binary search and also bring out its effrciency. (08 Marks)
-'A
A

Ee-
lr-

(1
H
li
OR
-.*
.ts

(t)
(t)
lJ
LJ
;r{
X 4a. Illustrate the tracing of quick sort algorithm for the following set of numbers:
64, 59, 32, g
A-l
t-.,/
t-
O()
\.,
25, 10, 72, lg, 40, ll, (08 Marks)
cdO-'\
-f<
lr
o<,
b. List out the advantages and disadvantages of divide and conquer method and illustrate the
ooc topological sorting for the following graph.
.!
,71 L
c'3

vo
c\t
'
C! -t
Ecd --
-e" f
ts-
(A-
-) ,\
o.
-S\|

tro.6-
5d
Oj H

(t) (J
a^

tr'-l
9E
5()
(/)tE
(Ft .* Fig.Q4(b) (08 Marks)
FE
t< c)
3p
>,! Module-3
oo"
.H
{-)
C
()=
orJ
t<
F
5a. Explain Greedy criterion. Write a Prim's algorithm to find minimum cost spanning tree.
-if9 - tv
(08 Marks)
F?
Xa.l b. Sort the given list of numbers using heap sort: 2, 9,7, 6, 5, 8. (08 Marks)
5r<
A

o< L< ?<

J c.i OR
0) a. Write an algorithm to find single source shortest path" (08 Marks)
z b. u[man tree anq
Construct a Huffinan rnd resutlmg
res Iti :ode wor
cooe wol d for the following:
(g
1J
Character A B C D
O. Probability 0.3 s 0.tr 0.2 0"2 0.15
F
Encode the words DAD and ADD. (08 Marks)

I of 2
 15CS43

Module-4
a. Explain the concept of dynamic programming, with example" (08 Marks)
b. Trace the following graph using Warshall's algorithm"

Fis.Q7(b) (08 Marks)

OR
8a. Explain Multistage graphs with example. Write multistage graph algorithm to forward
approach. (08 Marks)
b. Solve the following instance of Knapsack problem using dynamic programming. Knapsack
capacity is 5.
Item Weight Value
1 2 $12
2 I $10
3 3 $20
+
A
L Ot <
.lt r -.1

(08 Marks)

Module-5
9a, Explain backtracking concept. Illustrate N queens problem using backtracking to solve
4-Queens problem. (08 Marks)
b. Solve subset sum problem for the following example, s - {3, 5,6,7} and d - 15. Construct a
state space tree. (08 Marks)

OR
10 a. Explain the concept of branch and bound and solve assignment problem for the following
and obtain optimal solution.
Job I Job2 Job3 Job4
a I g 2 7 8-l
Person
lob 4 3 7l
c ls 8 I 8l
d l-7 6 s 4_l
(08 Marks)
b. E*plain LC Branch and Bound and FIFO branch and bound. (08 Marks)

,F,F:F*,F

2 of 2