Question

algorithm

TRUE OR FALSE

TRUE OR FALSE    Optimal substructure applies to alloptimization problems.     TRUE OR FALSE    For the same problem, there might be different greedy algorithms each optimizes a different measure on its way to a solutions.      TRUE OR FALSE Computing the nth Fibonacci number using dynamic programming with bottom-upiterations takes O(n) while it takes O(n2) to compute it using the top-down approach. TRUE OR FALSE Every computational problem on input size n can be solved by an algorithm with running time polynomial in n.    TRUE OR FALSE If any NP-complete problem can be solved in polynomial time, then NP =P.    TRUE OR FALSE    Both DP and greedy apply to optimization problems and will always lead to an optimal solution.      TRUE OR FALSE NP-Completeness applies directly not to optimization problems but to decision problems in which the answer is simply yes or no.       TRUE OR FALSE    No polynomial-time algorithm is known for any NPhard problem.       TRUE OR FALSE    Dijkstra’s algorithm solves multiple source shortest path problem.      TRUE OR FALSE    Floyed-Warshal is NPhard .       TRUE OR FALSE The greedy choice of activity selector is based on picking the activity earliest start time.       TRUE OR FALSE Many optimization problems can be stated as decision problems with the property that the decision problem can be solved in polynomial time iff the optimization problem can be solved in polynomial time.

Answer 1

1)

This statement is false.

Greedy omptimized problems might not have optimal substructure.

2)

This statement is false.

3)

This statement is false.

4)

This statement is true.

NOTE: As per Chegg policy I am allowed to answer specific number of questions (including sub-parts) on a single post. Kindly post the remaining questions separately and I will try to answer them. Sorry for the inconvenience caused.