Scribd
Upload
6 views3 pages

DAA Assignment - 2

DAA assignment

Uploaded by

thefashion597
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views3 pages

DAA Assignment - 2

DAA assignment

Uploaded by

thefashion597
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

Subject: Design and Analysis of Algorithms with Lab


Subject Code: 21ITH-311/21CSH-311 Semester: 5th

Assignment- 2

Last date of Submission: 09 Oct., 2023 Total Marks: 10 (2.5 marks each)

*Note: 1) Assignment should be handwritten.


2) Every student needs to submit assignment as per the allotted set
mentioned in attached PDF.

Set-1
1 Solve using fractional knapsack:
M=20, n=4
P= (3, 10, 15, 5)
W= (5, 13, 12, 8).
2 A networking company uses a compression technique to encode the message before
transmitting over the network. Suppose the message contains the following characters with
their frequency:

If the compression technique used is Huffman Coding, how many bits will be saved in the
message?
3 Find minimum spanning tree using prim and kruskal’s algorithm:
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

4 Write algorithm for matrix chain multiplication and solve the given sequence matrices:
P=<30, 35, 15, 5, 10, 20, 3>

Set-2

1 Let A1, A2, A3, and A4 be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5,
respectively. The minimum number of scalar multiplications required to find the product A1
A2 A3 A4 using the basic matrix multiplication method is?
2 Find longest common subsequence for:
A=<1001010> B=<10011>
3 What is the difference between greedy and dynamic programming approach?
4 Solve the following travelling salesperson problem.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Set-3
1 What do you understand by 0-1 Knapsack problem and fractional knapsack problem?
2 What is spanning tree give an example. Write down the Prim's and Kruskal’s minimum-cost
spanning tree algorithms.
3 Write the difference between the Greedy method and Dynamic programming.
4 Solve the following instance of 0/1 Knapsack problem using Dynamic programming n = 3;
(W1, W2, W3) = (3, 5, 7);
(P1, P2, P3) = (3, 7, 12); M(capacity of knapsack) = 4.

Set-4
1 Discuss about n-queen problem.
2 State the concept of branch and bound method and also list its applications.
3 A set of cities are given as graph. Solve the given Travelling Salesman Problem using Branch
and Bound:

4 Consider two strings A = "qpqrr" and B = "pqprqrp". Let x be the length of the longest
common subsequence (not necessarily contiguous) between A and B and let y be the number
of such longest common subsequences between A and B. Then x + 10y = _.

You might also like