T F For all positive integers n an Ontime algorithm always r

T F For all positive integers n, an O(n)-time algorithm always runs faster than an O(2^n)-time algorithm. T F A greedy algorithm does not always find an optimal solution. T F Kruskal\'s minimum spanning tree algorithm works correctly even when the input graph contains edges of negative weights. T F Although we cannot solve SUBSET SUM in polynomial time by a greedy algorithm, we can solve it in polynomial time by dynamic programming. T F No NP-complete problem can be solved in polynomial time unless the Vertex Cover problem admits a polynomial-time algorithm. T F There is a linear-time algorithm to find a vertex cover whose size is at most twice the size of an optimal one. T F It is NP-complete to determine whether a graph contains a vertex cover of size 1000.

Solution

a)True.O(n) is always better than o(2ⁿ) which is huge in computation

b)True.Greedy always not find optimal solution,Alternate to greedy can be backtrack and dynamic programming which is more efficient

c)True.Kruskal works for negative weights.Spanning tree size always remains same which is vertex-1 .it doesnt depend on weight of edge

d)True:DP is used to solve SUBSET problem in polynomial time

g)True.It is standard vertex cover problem can be easily solved by reduction technique.Reduce 3 SAT to vertex cover