Ad3351 Set2

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/Principle/Apparatus Tabulation/Circuit/ Calculation Viva-Voce Record Total

required/Procedure Program/Drawing & Results
20 30 30 10 10 100
1. Create a program for recursive and non-recursive algorithms and examine the order of
growth from log2n to n!
2. Write a program using Divide and Conquer Strassen's Matrix Multiplication to multiply the
two square matrices A and B, each of size n x n.
⎡1 2 3⎤ ⎡2 2 3⎤
A= ⎢3 4 5⎥ B= ⎢1 4 5⎥
⎢ ⎥ ⎢ ⎥
⎢⎣5 4 3⎥⎦ ⎢⎣6 4 3⎥⎦
3. To solve the following topological sorting problem, develop a code based on the DFS
method. a e
b d f
c g
Page 1 of 5
4. Create a program to sort the following elements 4,8,2,7,19,22,3,5,9 in an ascending order
using Transform and Conquer Heap Sort method.
5. Write a program to sort the following elements 8,18,10,9,20,4,3,6,5 in an ascending order

using Transform and Conquer Heap Sort method.
6. Given coins of denominations 1, 2, 4 and 5 with amount to be bay is 8. Create a program

to find optimal number of coins and sequence of coins used to pay the given amount using
dynamic programming method.
7. Create a program to find the transitive closure of the digraph specified in the following
graph using Warshall's algorithm.
a b
c d
8. Write a program to discover the transitive closure of the digraph specified in the following
adjacency matrix using Warshall's algorithm.
⎡0 1 1 0⎤
⎢0 0 1 0⎥⎥
⎢
⎢0 0 0 1⎥
⎢ ⎥
⎣1 0 0 0⎦
9. Write a program to find the shortest path between every pair of vertices of a graph using
Floyd’s Algorithm. 10
a e
5 3 9
12
b d 20
6
8
7 15
c g
Page 2 of 5
10. Create a program for the given instance of problem to obtain the optimal solution for the
knapsack problem using Dynamic Programming.
Item Weight Value
1 2 3
2 3 4
3 4 5
4 5 6
Capacity W=5
11. Write a program to solve the following knapsack instance using Dynamic Programming.
N=3, [w1,w2,w3]=[1.2.2] and [p1,p2,p3]=[18,16,6] and Capacity W=4
12. Create a program using Greedy Technique for finding a shortest path from one node to
another node in the following graph using Dijkstra’s algorithm.
G= [[0, 6, 0, 0, 0, 0, 0, 9, 0],
[6, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[9, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]]
Page 3 of 5
13. Create a program using Greedy Techniques to Construct the Huffman’s Tree & code for
the following data
Character A B C D E -
Probability 0.1 0.5 0.35 0.5 0.4 0.2
14. Write a program using Greedy Techniques to Construct the Huffman’s Tree & code for the
following data
Character m n o p q r
Probability 0.5 0.1 0.4 0.3 0.2 0.5
15. Create a program to solve the following Farmers problem using simplex method.
A farmer has a 420 acre farm on which she plants two crops: corn and soybeans. For
each acre of corn planted, her expenses are $60 and for each acre of soybeans planted,
her expenses are $110. Each acre of corn requires 110 quintals of storage and yields a
profit of $63; each acre of soybeans requires 40 quintals of storage and yields a profit of
$90. If the total amount of storage space available is 20,200 quintals and the farmer has
only $30,000 on hand, how many acres of each crop should she plant in order to
maximize her profit? What will her profit be if she follows this strategy?
16. Create a program for N-Queen (5 Queen) problem using Backtracking.
17. There are 5 distinct numbers {1,2,5,6,8}. Find the combinations of these numbers such
that sum is 9. Write a code using backtracking method to arrive at the solution.
18. Create a program to find the optimal solution using Branch and Bound method for the
following assignment problem.
Job1 Job2 Job3 Job4

Employee1 10 11 5 7
Employee2 6 8 9 5
Employee3 5 7 10 8
Employee4 7 6 8 12
19. Write a program to find the optimal solution using Branch and Bound method for the
following assignment problem.
Job1 Job2 Job3 Job4

Person1 7 6 10 7
Person2 12 7 9 5
Person3 8 6 7 10
Person4 5 11 5 12
Page 4 of 5
20. Create a program to solve the following Travelling Salesman problem using Branch and
Bound method.
1
a b
3 8 5
7
c d
2
Page 5 of 5

Ad3351 Set2

Uploaded by

Copyright:

Available Formats

Ad3351 Set2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ad3351 Set2

Uploaded by

Copyright:

Available Formats

B.E / B.Tech.

PRACTICAL END SEMESTER EXAMINATIONS, NOVEMBER/DECEMBER 2022

AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS

Time: 3 Hours Answer any one Question Max. Marks 100

Aim/Principle/Apparatus Tabulation/Circuit/ Calculation Viva-Voce Record Total

5. Write a program to sort the following elements 8,18,10,9,20,4,3,6,5 in an ascending order

6. Given coins of denominations 1, 2, 4 and 5 with amount to be bay is 8. Create a program

Item Weight Value

N=3, [w1,w2,w3]=[1.2.2] and [p1,p2,p3]=[18,16,6] and Capacity W=4

[6, 0, 8, 0, 0, 0, 0, 11, 0],

[0, 0, 7, 0, 9, 14, 0, 0, 0],

[0, 0, 0, 9, 0, 10, 0, 0, 0],

[0, 0, 4, 14, 10, 0, 2, 0, 0],

[9, 11, 0, 0, 0, 0, 1, 0, 7],

16. Create a program for N-Queen (5 Queen) problem using Backtracking.

Job1 Job2 Job3 Job4

Job1 Job2 Job3 Job4

You might also like