算法作业代做 Dynamic Programming I:Memoization, Fibonacci

: Dynamic Programming I:
Memoization, Fibonacci, Shortest Paths, Guessing

算法作业代做 The case when the maximum element is in central column is straightforward as this element would be bigger than all 4 of its neighbors.

Question 1 算法作业代做

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):

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): 算法作业代做

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 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代写     统计代写   计量经济作业代做