ET-4

AN
B.E/B.Tech. PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2022
Third Semester

AD3351 DESIGN AND ANALYSis OF ALGORITHMs

Regulations 2021)

Time 3 Hours
Answer any one Question Max Marks 100

Aim/PrinciplelApparatus Tabulation/Circuit Calculation Viva-Voce Record Total

requiredProcedure Program/Drawing &Results
20
30 30 10 10 100

Perform In order Tree Traversal

without Recursion

Given two square matrices A

and B of size n x n each. find their
using the concept of Strassen's Matrix multiplication matrix by
Multiplication
Sorta given set of elements using the quick sort method and
determine the
sort the
1st
elements Repeat the
experiment for different values of n, the time required to
number of elements in
the to be sorted and piota graph of the time taken versus n The
from a file or can be
generated using the random number generator elements can be read

Implement merge sort algorithm to sort a set of

required to sort the elements. Repeat the given elements and determine the time
elements the list to be sorted
in experiment for different values of
n,
the number of
and piot a graph of the time taken versus
can be read from a file or n The elements
can be
generated using the random number
generator
5 i) Obtain the
topological ordering of vertices in a digraph
i)
Compute the transitive closure of a directed graph using Warshall s
algorithm
Impiement any scheme to find the optimal
and then solve the solution for the
same problem instance Traveling Sales Person problem
using any approximation
determine the error in the
approximation algorithm and

Page I of3
 Flbyds agornnm
Shortest Paths Problem using
ement
All- Pairs

implement N Queen's problem using Back Tracking

in
Knapsack problem we are given 1)n
objects Knapsack with capacity m 3) An
2)
s associated with profit 4) An objecti s associated with object
profit Pi 5) when an object 1s
placed in knapsack we get profit P Xi Here objects can be broken into pieces (XI Values)
ind Optimal solution for
a Knap Sack
Problem using Greedy Metr
10
Implement 0/1
Knapsack problem using Dynamic Programming
11
From a
given vertex in a
weighted connected graph,
USing find shortest paths to other
Dijkstra algorithm
s vertices

12 a Obtain the
Topological ordering of vertices in a
gven digraph

b
Compute the transitive closure of a given directed graph using
Warshall's algorithm

Paye 2 of 3
 implement All-pairs shortest paths problem using Floyd s algorithm Paralelize tthis
algorithm. implement and determine the speed-up achieved
14 You are given an array of coins with varying denominations and an integer surm representing
the total amount of money you must return the fewest coins required to make up that sum. f
that sum cannot be constructed. return-1

and d. and their corresponding variable length codes be

15 Let there be four characters a, b, c
1 This leads to ambiguity because code assigned to c is the prefix of
00. 01 0 and coding
codes assigned to a and b If the compressed bit stream is 0001. the de-compressed output
Build a Huffman Tree from input characters
"ab
may be
cccd
or
"ccb or
"acd or
to characters
Traverse the Huffman Tree and assign codes

to a
16 Find subset of a given set S {sl
a sn) of n positive integers whose sum is equal
=
s2..
6. 8} and d 9 there are two solutions
= (1
given positive integer d For example. S={1. 2.5.
if
instance doesn't
and (18) A suitable message is to be displayed
if the given problem
2. 6)
have a solution

17 Implement N Queen's problem using Back Tracking

feasible solution for the complete

18 Build optimal solution by iterative refinement of
an
a

problem by using any iterative method

19 Implement any scheme to find the optimal solution for the Traveling Sales Person problem
and
and then solve the same problem instance using any approximation algorithm
determine the error in the approximation

(worker
20 Assume that you have N workers and N jobs that should be done For each pair
the job Our goal is to
job) you know salary that should I paid to worker for him to perform
complete all jobs min1mizing total while each worker to exactly one oD and
inputs. assigning
viCe versa

POCO
SHOT ON c0 F