数据结构和算法代写 DegreeAlgorithm代写

Data structure and algorithms

Assignment 5

数据结构和算法代写 A) DEGREEALGORITHMThis algorithm doesn’t always return the correct smallest edge cover set when there are a lot of vertices with the same degree.

Question 1   数据结构和算法代写

 

a) DegreeAlgorithm

This algorithm doesn’t always return the correct smallest edge cover set when there are a lot of vertices with the same degree. A counter example is given as below:

 

 

In the tree above, the nodes named v₁,v₂,…,v₆ are sorted already in the manner of:

deg（v₁）≥…≥deg（v₆）

Now if we run the DegreeAlgorithm, it will pick  S={v₁} to start, then it would pick v₂ ,v₃ ,v₄ sequentially because there is always a new edge that is not incident to S.

However, there is a smaller edge cover set S={ v₁,v₃ ,v₆ }with only 3 nodes, therefore the   DegreeAlgorithm is not correct.

 

 

b) BFSAlgorithm  数据结构和算法代写

This algorithm is correct.

For any edge e that is incident to two vertices, let a, b denote these two vertices. Because we iterate through the tree using a BFS algorithm, then a, b must be in different layers, and one of them is in odd layer, the other in even layer. The selection process ensured that one but only one vertex incident to edge e is chosen into the final edge cover.

Therefore, for every edge, there is always one vertex incident to it is chosen into S. The only two sets that suffice this property would be the even or odd sets in the intermediate result of the algorithm, and S is set to the smaller one. Therefore the algorithm is correct.

 

Question 2   数据结构和算法代写

 

a) Greedy algorithm

The proposed algorithm is described below:

• Sort all books in terms of deadline, by ascending order
• Let t = 0
• For each book in sorted order:

1. Let t = t + c_i*p_i
2. If t < b_i , then continue to next book
3. else return False

• return True

 

b) Correctness  数据结构和算法代写

Proof:

Without loss of generality, let’s assume that book b₁ , b₂ ,…, b_n have increasing deadline, then we are printing books with smallest deadline all the time. If the algorithm return true, then the printing arrangement must be able to meet all deadlines by following the sorting order indicated in the algorithm.

Now we assume by contradiction that 1) the algorithm returned false, and 2) there is in fact an arrangement that could meet all deadlines. Now if the arrangement exists, then there exist a pair of index i < j such that one copy of b_j would be printed before b_i , but ‘s deadline is earlier than b_j ’s.

Now if this arrangement can meet all deadline, then the b_j ’s printed date should be before the deadline for b_j , the b_i printed date should be before the deadline of b_i but after the printed date of b_j . Now we know that d_j > d_i , therefore, if we switch this two copies, the new arrangement should still meet all deadlines. If we repeat this process, then we should have the exactly arrangement as indicated in the algorithm. But the algorithm’s solution can’t meet all the deadlines. The contradiction suggests that the arrangement can’t exist.

Therefore our proposed algorithm is correct

 

c) Time complexity

The sorting process takes O(n log n) time, and the for loop takes O(n) time. So our algorithm runs in O(n log n) time.

 

 

Question 3  数据结构和算法代写

 

a) The algorithm

Our algorithm is given as below:

• step 1: Let left = 0, right = n/3, m = int((left+right)/2)
• step 2: if A[m] > A[m-1] and A[m] > A[m+1] then k = m

-else if A[m] < A[m-1] (the array is already decreasing), let right = m

-else if A[m] < A[m+1] (the array is still increasing), let left = m

• step 3: m = int((left+right)/2), and go back to step 2 until we find k.
• step 4: compare A[k] and A[n], pick the maximum of these two to be the maximum of the array.
• step 5: compare A[1] and A[k+2n/3], pick the minimum of these two to be the minimum of the array.

 

b) Correctness  数据结构和算法代写

Our algorithm first used binary search to locate k, then compare the possible positions for the maximum and minimum of the array.

Because the array is a concatenation of several ordered subarrays, we can deduct the maximum integer could only happen at the k-th place, or the last place in the array. The minimum can only occur at the fist index or the (2n/3 + k)-th place. So the task is reduced to finding the k value. Now the 1 to k-th items are sorted in increasing order, the (k+1) to (k+2n/3)-th items are sorted in decreasing order. Therefore we know A[k]>A[k-1], A[k] > A[k+1], and this pattern is used to locate k in a binary search manner. So our algorithm is correct.

 

c) Time complexity

The algorithm performed a binary search in an array of length N/3. Then it performed two comparisons. Therefore the time complexity is O(logN/3) + O(1) =O(logN) .

 

 

其他代写：program代写 project代写 essay作业代写 作业代写 作业加急 英国代写 北美作业代写 homework代写 java代写 matlab代写 finance代写 python代写 report代写 paper代写 assignment代写 加拿大代写

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