Question

please directly show me the answers

8) (20 pts) Running times. Each question has 2pts. A. Can be solved in linear time in the worst case. B. Can be solved in polynomial time in the worst case. C. Can be solved in exponential time in the worst case. D. Cannot be solved/computed with any algorithm Match each task below with the best-matching description above. For the purposes of this question, assume PNP. Find the shortest paths from source to other nodes on a graph where all edges have weight 1. Find a topolectal ordering of nodes on a directed graph. Find if a graph is disconnected or not (i.e, there are islands or isolated nodes). Find if an input string matches a regular expression. Find if a set X of integers can be partitioned into a subset S X such that the sum of integers in S is equal to target t. Find if there are three integers in a set X of integers such that the sum of the three integers is equal to t

Answer 1

To find the shortest path from source to destination where weight of all edges is 1. A - Can be solved in linear time in worst case.

To find topological sorting of nodes. A - Can be solved in linear time in worst case.

To find if graph is disconnected or not. A - Can be solved in linear time in worst case.

Find if an input string matches a regular expression. C - Can be solved in exponential time in worst case.

Find if a set X of integers can be partitioned into a subset S where sum of integers in S equals target t. B - Can be solved in polynomial time in worst case.

Find if there are three integers in a set X such that their sum is 1. B - Can be solved in polynomial time in worst case.