Circle T (true) or F (false) for each of the following statements to indicate wh

Question

Circle T (true) or F (false) for each of the following statements to indicate whether the statement is true or false (1 mark for each correct answer and -1 mark for each incorrect answer). T F For all positive integers n, an O(n)-time algorithm always runs 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 Sunset 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 solving in polynomial time unless the Vertex Cover problem admits a polynomial-time algorithm. T F There is a liner-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.

Explanation / Answer

The answer to the first 4 parts is below:

1: For all positive integers n, an O(n)-time algorithm always runs faster than an O(2^n)-time algorithm.

Answer: F

Explanation: It doesn't always run faster, O(n) means linear, which means that as you increase the size of input so does the runtime. if you plot a graph for O(n) it will be a straight line. With O(2n), as you increase the size of input the runtime also increases (more as compared to O(n)) due to which the graph will have a slope but it still reduces to linear in terms of algorithm complexity and thus it reduces to O(n).

2: A greedy algorithm does not always find an optimal solution.

Answer: T

Explanation: Greedy algorithm is certainly fast but it doesn't always find an optimal solution and thats because usually greedy algorithms do not operate exhaustively on all the data.

3. Kruskal's mimimum spanning tree algorithm works correctly even when the input graph contains edges of negative weights.

Answer: T

Explanation: Mimimum Spanning tree algorithms allow weights of arbitrary sign which means you can add a big positive constant to the edges of your graph which will make all the edges positive. Mimimum Spanning tree algorithms works on undirected graphs.

4. Although we cannot solve Subset Sum in polynomial time by a greedy algorithm, we can solve it in polynomial time by dynamic programming.

Answer: T

Explanation: Subset Sum problem can be solved via a few techniques like dynamic programming, backtracking, quantum algorithms, priority algorithms etc, However solving Subset Sum problem via dynamic programming is best for Small problems

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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