please provide a detailed full solution to each mcq, thank you so much! 1. (7) C

Question

please provide a detailed full solution to each mcq, thank you so much!

1. (7) Circle T (true) or F (false) for each of the following statements to indicate whether T F (ay. For all positive integers n, an o(n-time algorithm always runs faster than O(2") time algorithm T F b). A greedy algorithm does not always find an optimal solution. T (c) Kl minimum spanning tree algorithm works correctly even when the rusikal's input graph contains edges of negati ve weights. we cannot solve SUBSET SUM in polymoonial time by a greedy algorithm, we can solve it in polynomial time by dynamic programmi T F (e). No NP-Domplete problem can be solved in polynomial time unless the VER- Tex Covlau problem admits a polynomiaktime algorithm. (f). There is a inear-time algorithm to find a vertex cover whose size is at moest twice the size of an optimal one. T F g). It is NP-complete to determine whether a graph contains a vertex cover of Rize 1000.

Explanation / Answer

a) TRUE

Explaination:

if n=5

then running time of O(n) time algorithm is 5

and running time of O(2n) time algorithm is 32 i.e. 25

hence, it is clear that O(n) time algorithm is faster than O(2n) time algorithm.

b) TRUE

Explanation:

In some system, rupees come in 1 rs , 7 rs , and 10 rs coins.

Using a greedy algorithm to count out 15 rupees , we would get a 10 rs coin and Five 1 rs coins for a total of 15 rs. This requires six coins

A better(optimal) solution would be to use two 7 rs coin and one 1 rs coin

This only requires three coin

So, we can say that Greedy algorithm do not always produce optimal solutions.

c) TRUE

Kruskal's minimum spanning tree algorithm works correctly with negative weights also because it adds up all weights along the paths and tries to find the minimum one.

d) FALSE

The Subset Sum problem is an NP complete problem, but it does not have a polynomial time algorithm. The algorithm takes O(np) time, where n is the input size, and p is the precision. If you look at it, it shall seem to be polynomial time, but in reality its not.

The reason is because its not polynomial with respect to the input size n. Its because P can take any large value, say 2^n. So np = n*(2^n), which is not polynomial.

e) TRUE

the VERTEX COVER problem admits a polynomial-time algorithm. Hence, NP-complete problem can be solved in polynomial time.

f) FALSE

there is no lenear time algorithm.

g) TRUE

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.