Search the whole station

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

152

## 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 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).

### 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 ) + ∑uC(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 ∑uC(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).

### Related recommendations

• #### 时间序列分析代写 Time Series Analysis代写 Exam代写

321

STAD57 Time Series Analysis Final Examination 时间序列分析代写 Duration: 3hours Examination aids allowed: Non-programmable scientific calculator, open book/notes Instructions: • Read the...

View details
• #### 线性代数代写 数学代写 考试代写 EXAM代写

396

MAT224H5Y EXAM 线性代数代写 Question 1. (40 Marks) This question consists of 20 multiple choice questions. Answer each question and put your answer in the table below. Question 1. (40 Marks...

View details
• #### 金融工程考试代考 E4700代写 金融代写 Exam代写

191

E4700 Final Examination 170 points total 金融工程考试代考 You can make use only of your lecture notes but no other sources of information or help in completing this exam. You may use only a ...

View details
• #### 数学积分代写 Integral Calculus代写 MATH代写 Exam代写

355

Integral Calculus - MATH 9B Final Exam 数学积分代写 Instructions: (1) You have 160 minutes to solve this exam. (2) Uploading to Gradescope will be at the end. You will have 15 minutes to...

View details
1