Ad3351 Set4

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. Perform In order Tree Traversal without Recursion.
2. Given two square matrices A and B of size n x n each, find their multiplication matrix by
using the concept of Strassen’s Matrix Multiplication.
3. Sort a given set of elements using the quick sort method and determine the time required to
sort the elements. Repeat the experiment for different values of n, the number of elements in
the 1st to be sorted and plot a graph of the time taken versus n. The elements can be read
from a file or can be generated using the random number generator.
4. Implement merge sort algorithm to sort a given set of elements and determine the time
required to sort the elements. Repeat the experiment for different values of n, the number of
elements in the list to be sorted and plot a graph of the time taken versus n. The elements
can be read from a file or can be generated using the random number generator.
5. i) Obtain the topological ordering of vertices in a digraph.
ii) Compute the transitive closure of a directed graph using Warshall`s algorithm
6. Implement any scheme to find the optimal solution for the Traveling Sales Person problem
and then solve the same problem instance using any approximation algorithm and
determine the error in the approximation.
Page 1 of 3
7. Implement All-Pairs Shortest Paths Problem using Floyd's algorithm.
8. Implement N Queen's problem using Back Tracking
9. In Knapsack problem we are given:1) n objects 2) Knapsack with capacity m, 3) An object i

is associated with profit Wi , 4) An object i is associated with profit Pi , 5) when an object i is
placed in knapsack we get profit Pi Xi .Here objects can be broken into pieces (Xi Values).
Find Optimal solution for a Knap Sack Problem using Greedy Method
10. Implement 0/1 Knapsack problem using Dynamic Programming
11. From a given vertex in a weighted connected graph, find shortest paths to other vertices
using Dijkstra’s algorithm.
12. a. Obtain the Topological ordering of vertices in a given digraph
b. Compute the transitive closure of a given directed graph using
Warshall's algorithm.
Page 2 of 3
13. Implement All-pairs shortest paths problem using Floyd`s algorithm. Parallelize this
algorithm, implement and determine the speed-up achieved.
14. You are given an array of coins with varying denominations and an integer sum representing
the total amount of money; you must return the fewest coins required to make up that sum; if
that sum cannot be constructed, return -1.
15. Let there be four characters a, b, c and d, and their corresponding variable length codes be
00, 01, 0 and 1. This coding leads to ambiguity because code assigned to c is the prefix of
codes assigned to a and b. If the compressed bit stream is 0001, the de-compressed output
may be “cccd” or “ccb” or “acd” or “ab”. Build a Huffman Tree from input characters.
Traverse the Huffman Tree and assign codes to characters.
16. Find a subset of a given set S = {sl, s2... sn} of n positive integers whose sum is equal to a
given positive integer d. For example, if S={1, 2, 5, 6, 8} and d = 9 there are two solutions {1,
2, 6} and {1,8}.A suitable message is to be displayed if the given problem instance doesn't
have a solution.
17. Implement N Queen's problem using Back Tracking
18. Build an optimal solution by iterative refinement of a feasible solution for the complete
problem by using any iterative method.
19. Implement any scheme to find the optimal solution for the Traveling Sales Person problem
and then solve the same problem instance using any approximation algorithm and
determine the error in the approximation.
20. Assume that you have N workers and N jobs that should be done. For each pair (worker,
job) you know salary that should be paid to worker for him to perform the job. Our goal is to
complete all jobs minimizing total inputs, while assigning each worker to exactly one job and
vice versa.
Page 3 of 3

Ad3351 Set4

Uploaded by

Copyright:

Available Formats

Ad3351 Set4

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 Set4

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

1. Perform In order Tree Traversal without Recursion.

5. i) Obtain the topological ordering of vertices in a digraph.

8. Implement N Queen's problem using Back Tracking

9. In Knapsack problem we are given:1) n objects 2) Knapsack with capacity m, 3) An object i

10. Implement 0/1 Knapsack problem using Dynamic Programming

12. a. Obtain the Topological ordering of vertices in a given digraph

b. Compute the transitive closure of a given directed graph using

17. Implement N Queen's problem using Back Tracking

You might also like