算法和复杂性代写 算法考试代写 Exam代写 Algorithms代写

Exam for Algorithms and Complexity

算法和复杂性代写 Question 1 We prove this fact by diagonalization. We encode all TMs in to binary string. Since the finite string are enumerable. We could list

Question 1

We prove this fact by diagonalization. We encode all TMs in to binary string. Since the finite string are enumerable. We could list all TMs. Consider the following TM D. D(x) simulates the TM M_x on input x where M_x is the x-th TM in the list. D(x) runs for at most 2⁴ⁿ steps, and output the opposite result of M_x (x). If M_x (x) doesn’t terminate in 2⁴ⁿ steps, D(x) output anything. The simulation costs at most 2⁴ⁿ steps. Hence, D is in DTIME(2⁴ⁿ). 算法和复杂性代写

We prove by contradiction. Assume that DTIME(2ⁿ ) = DTIME(2⁴ⁿ). Then there exists M such that L(M) = L(D) and M runs in time O(2ⁿ). Let x be the string corresponding to the M, i.e., M_x = M. We consider D(x). By definition, if M_x(x) terminates in 2⁴ⁿ steps, then D(x) must output the opposite result of M_x(x). Then can’t be equal. We know that M_x(x) terminates in O(2ⁿ) steps.

However, O(2ⁿ) steps may be more than 2⁴ⁿ steps when n is small. We solve this issue by padding the input. We can encode a TM by adding some useless 0s to increase the input size to arbitrarily large. Hence, we see that M_x and D can’t be equal.

Thus, DTIME(2ⁿ) ≠ DTIME(2⁴ⁿ).

Question 2

Yes, it’s possible. Consider the following graph.

Vertices a, b, c and d forms a 4-clique. The only edges to connect with e, f and g are the threes with the heaviest edges. Hence, even in the minimum spanning tree, these 3 edges must be included.

Question 3 算法和复杂性代写

We can solve this problem by dynamic programming. First select arbitrary vertex r as the root of the tree. Then, by this orientation, each edge connect to a parent and a child. Denote C(v ) as the set of children of v . Moreover, for each vertex v in the tree, the subtree rooted at v is well-defined.

Denote f (v ) as the MWVC (min weighted vertex cover) for the subtree rooted at v . We also denote g(v ) as the MWVC for the subtree rooted at v , in case that v must be selected in the cover set. Note that, we are able to write the recurrence by using f only. But this auxiliary function g simplifies the recurrence for f .

To solve f (v ), if v is a leaf, then we simply set f (v ) = 0 because in the subtree there is no edge. If it’s not a leaf, we have two options. We either select v or don’t select v . In the first option, all edges connected to v are covered. Hence we only need to cover all subtrees rooted at every children of v . Hence we pay a cost of ϕ(v ) + ∑_u∈C(v) f(u). In the second option, we need to cover all edges connected to v via their another ends, i.e., the children of v . Then we could use the auxiliary function g. We pay a cost of ∑_u∈C(v) g(u).

To solve g(v ), we must select v according to the definition of g.

Then all edges (may be none, in case that v is a leaf) connected to v are covered. Hence we only need to cover all subtrees rooted at every children of v . Hence we pay a cost of ϕ(v ) + ∑_u∈C(v) f (u).

In the implementation, we may use DFS to search the tree starting from the root r. After we have computed the function f (u) and g(u) for all children u of parent v , we are able to compute f (v ) and g(v ).

For the correctness, it’s easy to see that by above recurrence, every edge must be covered by one of its two ends. In case that we don’t select the parent, then we must select the children. The optimality of the solution directly follows from the optimal substructure property of the dynamic programming.

For the run time, we visit each vertex for exactly once. The DFS costs O(n).

To solve the recurrence f (v ) and g(v ), we need to pay a cost of |C(v )

| operations because we use |C(v )| many values. However, in the tree structure, ∑_v |C(v )| = n − 1 because except the root r, every vertex has only one parent. Hence, the recurrence itself costs also O(n). In total, it costs O(n).

Question 4 算法和复杂性代写

更多代写：CSfinal exam代考  gre代考知乎  英国数学代考价格  dissertation代写  essay代写靠谱吗  代写读书报告

合作平台：essay代写 论文代写 写手招聘 英国留学生代写