Algorithm
Algorithm代写 – 这是利用Algorithm进行训练的代写, 对Algorithm的流程进行训练解析, 涉及了NP等代写方面
(a) False (b) False The following string 01000 can be generated by this grammar while is not the form of
(c) True The form recurrence is applicable of the Master Theorem
Therefore Since therefore Algorithm B is asymptotically faster (d) False (If P != NP) Counter example: The problem A is a trivial problem that answers yes for every input. Which is not NP-Complete and in P. And Problem B is a Vertex-Cover. We can polynomially reduce an instance of A to B as a graph with only one vertex and no edges. And no matter what a solver of B answers, we answer "yes". (e) False The problem is in P, so not NP-complete with the assumption P != NP. The problem can be solved as to get the total weight of MST of G (for example, Prim’s) and see if the weight. Hence it’s a polynomial time algorithm. (f) False Decidable languages are closed under complement. Decidable languages can not have undecidable complement, and vise versa. (g) False (h) True. Since L is finite, we can enumerate the members of L and see if it equals the input in finite time.( will halt). Therefore L is decidable.
2
(a) 001011011011010 (b) Main Idea Assign 0 edges weight 1, and 1 edges -1, edges 0 and run BF. Algorithm
- Build a graph such that:
where
- Then we run Bellman-Ford from and see if any is negative (including )
- if so, that means we have a walk from s to any accepting state a, and the number of 0’s on it is less than the number of 1’s. Time Build graph: ,run Bellman-Ford = Correctness The states order during the NFA recognition forms a walk from start to any accepting state. If we assign edge weight like said above, then the total weight of a walk will be
=
If this number is less than zero, then it means we have found such a walk. If there is a walk with strictly less number 0’s than 1’s, then it will eventually be found by the Bellman Ford algorithm.
(c) We first derive a DFA out of the NFA M. Then invert the accepting attribute of each state(that is: an accepting state is now not accepting, and vise versa). Then the DFA recognizes the complement of , then we run the same algorithm as in part (b). The time is subset construction.
state inversion. Bellman Ford.