QUESTION$-2$

Design of a network: Suppose that you are wiring a building so that all the rooms are

connected via bidirectional communication wires. Suppose that you can connect any two rooms

at the cost of the wire connecting the rooms, which depends on the specifics of the building

and the rooms but is always a positive real number. We can represent the possible connection

between rooms as a graph, where vertices represent rooms and weighted edges represent

possible connections along with their cost $($weight$).$ To minimize the cost of the wiring, you

could find a minimum spanning tree of the graph.

Design an algorithm to minimize the cost of the wiring for the network and also analyze the

algorithm by giving the results using order notation.

QUESTION$-3$

A thief breaks into a store and wants to fill his knapsack of capacity $K$ with goods of as much

value as possible. The thief's knapsack can hold $100gms$ and has to choose from:

$30$ gms of gold dust at Rs $\frac{1000}{g}m$

$60$ gms of silver dust at Rs $\frac{500}{g}m$

$30$ gms of platinum dust at Rs $\frac{1500}{g}m$

a$)$ Find what is the maximum possible solution to get more profit

b$)$ Design greedy algorithm that finds the optimal solution for the given problem.

c$)$ Is the solution return using b algorithm is it optimal? Justify

d$)$ Analyze your algorithm and give the results using order notation.