$1$ a$.$ You work as an engineer for the Roads and Highways department in a district. The district has $7$

CO$2$

thanas that are represented by the $7$ vertices in the following graph. The edges between the vertices

represent the roads that connect one thana with another and the weight of an edge represents the

length of the road.

A recent flood has totally damaged these roads and immediate repair work is needed. The cost to

repair a road is proportionate to its length. However, your department does not have the budget to

repair all the roads so you need to repair a subset of the roads. Which algorithm should you use

here to find out the roads that need to be repaired to keep all the thanas connected to one another

with the minimum possible cost?

Show the step by step simulation of the algorithm. You may pick any algorithm of your preference

that you think will solve the problem.

b$.$ Problem Y is NP$-$complete. If A professor takes an instance of Y$,$ converts it into an instance of the

CO$3$

shortest path problem in $2^n$ time, and claims that Y is in P now, is the claim valid?

Explain your answer.

c$.$ Rank the following three approximation algorithms from the worst to the best:

CO$32-$approximation algorithm, $1\mathrm{.}5-$approximation algorithm, n $-$approximation algorithm

handwritten ans only