Scribd
Upload
7 views2 pages

DAA Assignment 3

Uploaded by

Mansi
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
7 views2 pages

DAA Assignment 3

Uploaded by

Mansi
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/ 2

ABES ENGINEERING COLLEGE, GHAZIABAD

DEPARTMENT OF COMPUTER SCIENCE


Session: 2024-25 Semester: 5th Section: A+B+C
Course Code: BCS-503 Course Name: Design and Analysis of Algorithms
Assignment 3
Date of Assignment: 29/11/24 Date of submission: 04/12/24

S.No. KL, CO Question

1 K2, C03 Write a Short Note on Convex Hull.

2 K3,C03 Use single source shortest path algorithm for find the optimal solution for given graph.

3 K3,CO3 Explain any one minimum cost spanning tree algorithm with example.
4 K3,CO3 Consider 5 items along their respective weights and values
I=<I1,I2,I3,I4,I5>
W=<5,10,20,30,40,>
V=<30,20,100,90,160>
The capacity of Knapsack w=60. Find the solution to the fractional knapsack problem.
5 K3,C03 Generate MST for the following graph using Prim’s Algorithm

.6 K3,CO3
Write down Bellman Ford Algorithm to solve Single source shortest path problem. Also Write
its time complexity.
7. K2,CO3 Explain “greedy algorithm” Write its pseudo code to prove that fractional Knapsack
problem has a greedy-choice property.
8. K3, Multiply The given Matrices using Strassen’s Multiplication.
CO3 A= 1 3 B= 6 7
7 5 3 8

9. K3, A networking company uses a compression technique to encode the message before transmitting
CO3 over the network. Suppose the message contains the following characters with their frequency:

Note that each character in input message takes 1 byte. If the compression technique used is
Huffman Coding, how many bits will be saved in the message?

10. K3, Consider the following tasks with their deadlines and profits. Schedule the tasks in such a way
CO3 that they produce maximum profit after being executed −
S. No. 1 2 3 4 5

Jobs J1 J2 J3 J4 J5

Deadlines 2 2 1 3 4

Profits 20 60 40 100 80

You might also like