算法takehome代写 Dynamic Programming II of IV takehome

Dynamic Programming II of IV takehome

算法takehome代写 Because each tree would take no more than  steps to decide, (note ). And there is T trees, so the total number of steps to verify

Question 1  算法takehome代写

To make the resulting graph acyclic, the remaining graph must be a tree after the selected edges removed. Since the total weight of the original graph is known, and the edge set to be removed must have a minimum weight, then the resulting tree would be the maximum spanning tree. Therefore we can modify the Prim’s algorithm in the following manner to find this tree first:

PrimMaxSpanTree(G=(V,E)):

Step 1: Pick any element v from V, set  and

Step 2: Find the edge  with maximum weight such that . Add  to .

Step 3: If , then return A.

Now to find the edge set to be removed, we can use the following routine:

FindRemoveEdges(G=(V,E)):

       Step 1: A = PrimMaxSpanTree(G)

Step 2: Let , for every edge e in E:

If , then add e to R

Step 3: return R

The Prim’s algorithm would run in  time. The final loop takes  time. Therefore the total time complexity is .

Question 2

• Note that the question only asked us to find “a hill” instead of “all hills”, we may use divide and conquer to quickly divide the whole task into smaller pieces to achieve sublinear time. Suppose we guess the middle element in the 1d array is the “hill”, if the two conditions were all tested correct, then we find a hill  and return it. If not, assume that the right neighbor is bigger (), we claim that there would always be a hill on the right half of the array, to see this:


• For any element from the middle of the array to the right end of the array to “not be a hill”, they must now all be smaller than their right neighbor.

Otherwise we will have a hill instantly.

• But the element on the rightmost position of the array has no right neighbor. Therefore it is the biggest element from middle element to the right end of the array.


• Then the rightmost element would be the hill.

So there would always be a hill on the right half of the array if the right neighbor is bigger. Similarly, if , then there will always be a hill in the left half of the array as well. The algorithm we designed is shown below:

findHill(A):  算法takehome代写

Let  rounded up if length of A is odd.

Test

If true, then:

Test

If true, then return  and its position

Else:

                      findHill()

Else:

        findHill()

Time complexity of the algorithm is , assume that the algorithm searched T times till a hill is found, we know that  because by each test of hill condition, the array was cut into two halves. So for an array with length n, we need to test  times.

• Using the recursion idea of findHill algorithm we built in Part (a), we can solve the 2d version of the question by splitting the matrix into n column arrays with length n. Starting from the middle column of the matrix, we can first find the maximum element of this column and its two neighboring column in
  
  
  
  • If the maximum element is in the middle column, then we find a hill, because it will be bigger than 4 of its neighbors.
  
  
  • If the maximum element is in the left column, then we can recursively perform the above procedure in the area of left half and the middle column.
  
  
  • Similarly, if the maximum element is in the right column, then we search recursively in the area of right half and middle column.
  
  
  
  

To further accelerate this process, note that we only care about the 3 middle columns in A. If A’s height is larger than width, then we can search the 3 middle rows to scan less element.

The algorithm can be expressed as:

findHill2D_Column(A): 算法takehome代写

Let  rounded up if width of A is odd.

find the maximum element e in the 3 columns:

If the maximum element e is in A[:, mid]:

Return e

Elseif e is in A[:, mid-1]:

findHill2D(A[:, 1:mid])

else:

findHill2D(A[:, mid:n])

findHill2D_Row(A):

Let  rounded up if height of A is odd.

find the maximum element e in the 3 columns:

If the maximum element e is in A[mid,:]:

Return e

Elseif e is in A[mid-1,:]:

findHill2D(A[1:mid, :])

else:

findHill2D(A[mid:n, :])

       findHill2D(A):

              If height(A) > width(A):

findHill2D_Row(A)

Else:

findHill2D_Column(A)

Correctness: The case when the maximum element is in central column is straightforward as this element would be bigger than all 4 of its neighbors.

If the maximum element is in the left column, then either it could be a hill, or there is another hill following the logic in part (a). And the path from this maximum element to the hill would not have to cross the central column. Therefore the search of next round could be limited to the left half.

Time Complexity: This algorithm runs in time complexity of . A starts as  matrix, with each iteration, A’s maximum dimension would be halved, then looped. So the total loop scanned:

Less than 6n elements. So the algorithm’s time complexity is

Question 3  算法takehome代写

To solve this question using dynamic programming, define the two functions below:

calculates the total distance from cities 1 to j to their relative closest fire station, with exactly i fire stations optimally placed between cities 1 to j. For example, f(1,4) calculates when there is only 1 fire station placed among city 1,2,3,4, the average distance from city 1,2,3,4 to this fire station.

calculates the total distance from cities a, a+1, …, b to the fire station placed among cities a, a+1, …,b when it is optimally placed. For example, g(10,20) would find the optimal location between cities 10 to cities 20, and calculates the average distance.

Note that since the total number of cities is fixed, optimizing for total distance is equivalent to optimizing for average distance.

Now obviously:

for x =1,2,…,d can be calculated easily:

And  function can be solved via a for loop in each candidate city.

can be calculated with the following recursion:

The scheme to serve city 1 to x with 2 stations is optimal when each station is optimally placed.

Similarly:

Therefore, the solution to serve n cities with k stations is:

If city x should be placed a station, then x should be a solution the subproblems in solving  recursively.

Now  takes  time to calculate. Then we have  for

To calculate  we would need to loop through all possible y’s. There are n candidates, and we need to evaluate g function n times. So it would take  to calculate using the cached  values.

Similarly, for , each of them would take an extra  time to calculate.

Total time complexity:

Question 4

• The Forest-Verify problem belongs to NP because it has a polynomial time verifier for every instance :

Verify(x):

       Calculate

Return true the sum is nonnegative. Returns false otherwise.

Because each tree would take no more than  steps to decide, (note ). And there is T trees, so the total number of steps to verify an instance  takes no more than  steps.  is a polynomial time verifier. So Forest-Verify problem belongs to NP.

• A 3-SAT clause could be turned into decision tree in the following manner. Suppose the 3-SAT clause is represented as:

Then the tree could be represented as below. If there is any variable being negated in the clause, we can switch the two branches under the node representing the variable. In both the original clause and the decision tree, at least one of the variables X, Y, Z must be true for both expression to be true. And if X=Y=Z=False, then both expressions return false.

• Given any 3-SAT problem with k clauses, let it denoted by:

For each clause, we can use the algorithm in part (b) to convert a 3-SAT clause into a decision tree. The conversion to a tree is done in constant time. So it takes  time to get k decision trees, each related to one of the clauses in 3-SAT problem.

Due to the equivalence between decision tree and the original 3-SAT clause, the problem to find a model that satisfy the 3-SAT clause now turns into the problem to find  that .

So the 3-SAT problem can be reduced to forest verify problem in polynomial time.

更多代写： HomeWork cs作业     金融代考    postgreSQL代写         IT assignment代写     统计代写 犯罪经济学代考