ECON 3H03 – INTERNATIONAL MONETARY ECONOMICS MIDTERM EXAM 2 国际货币经济学代写 This midterm is individual and closed-book. For the multiple choice questions, choose the option that best answ...View details
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
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 Mx on input x where Mx is the x-th TM in the list. D(x) runs for at most 24n steps, and output the opposite result of Mx (x). If Mx (x) doesn’t terminate in 24n steps, D(x) output anything. The simulation costs at most 24n steps. Hence, D is in DTIME(24n). 算法和复杂性代写
We prove by contradiction. Assume that DTIME(2n ) = DTIME(24n). Then there exists M such that L(M) = L(D) and M runs in time O(2n). Let x be the string corresponding to the M, i.e., Mx = M. We consider D(x). By definition, if Mx(x) terminates in 24n steps, then D(x) must output the opposite result of Mx(x). Then can’t be equal. We know that Mx(x) terminates in O(2n) steps.
However, O(2n) steps may be more than 24n 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 Mx and D can’t be equal.
Thus, DTIME(2n) ≠ DTIME(24n).
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).