## NPTEL Design and Analysis of Algorithms Week 8 Assignment Answers 2024

1. Which of the following is a linear constraint?

- 18x + 3yz + 42z ≥ 217
- 18x + 3y + 42xz ≤ 217
- 18x + 3y + 42z ≥ 217
- 18xy + 3yz + 42z = 217

Answer :-For Answers Click Here

2. The President is arriving to inaugurate a stadium. He will go directly from the airport to the stadium. Security considerations require two routes to be available for the President that do not overlap on any section of road, though the routes can cross each other at intersections.

This can be modelled as a network ﬂow problem where the source and target are the airport and the stadium, road intersections are nodes and each road segment is an edge. The actual ﬂow problem to be solved is to:

- Assign a total of capacity 2 to all outgoing edges from the source and ﬁnd a feasible ﬂow.
- Assign a total of capacity 2 to all incoming edges to the target and ﬁnd a feasible ﬂow.
- Assign each edge capacity 1 and check that the maximum ﬂow is less than 2.
- Assign each edge capacity 1 and check that the maximum ﬂow is at least 2.

Answer :-For Answers Click Here

3. City authorities are concerned about traﬃc accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of any accident along these roads. To minimize response time, ambulances are to be located at intersections with traﬃc lights so that any segment of road can be reached by at least one ambulance that does not have to pass through a traﬃc light to reach the scene of the accident. If we model the road network as a graph, where intersections with traﬃc lights are vertices and edges represent road segments between traﬃc lights, the graph theoretic question to be answered is:

- Find a spanning tree with minimum cost.
- Find a minimal colouring.
- Find a minimum size vertex cover.
- Find a minimum size independent set.

Answer :-For Answers Click Here

4. We have an exponential time algorithm for problem A, and problem A reduces in polynomial time to problem B. From this we can conclude that:

- B has an exponential time algorithm.
- B cannot have a polynomial time algorithm.
- A cannot have a polynomial time algorithm.
- None of the other choices are correct.

Answer :-

5. Suppose SAT reduces to a problem C. To claim that C is NP-complete, we additionally need to show that:

- There is a checking algorithm for C.
- Every instance of C maps to an instance of SAT.
- Every instance of SAT maps to an instance of C.
- C does not have an eﬃcient algorithm.

Answer :-For Answers Click Here