Algorithm practice
Algorithm代做 – 该题目是一个常规的Algorithm的练习题目代写, 是比较典型的Algorithm等代写方向
Problem 1 (a) Fisrt answer : 2, 3, 4 The provided Algorithm has a time complexity of(log)which does not meet the()time requirement. And it is wrong to say the time complexity is()when each step takes() and there are(log)steps. Second answer : 2, 3, 4 The provided algorithm has a time complexity of(log)which does not meet the()time requirement. Also, the time complexity of(log)is not equivalent to(). Third answer : 2, 3, 4 The sorting step takes(log)time, which dominates the time complexity of the algorithm. Fourth answer : 2, 3, 4 The time complexity is(log), which does not meet the()time requirement. However, whengets large, the difference between(log)and()is significant, which means that we cannot treat it as(). Fifth answer : 2, 4 In each step, dividing the array into halves cost(), and we have(log)steps. Thus the time complexity is(log).
Problem 2 (a) A greedy algorithm to solve this problem would be to sort the arraysandin non-decreasing order, and then allocate the ith element ofto the ith element of. In other words, we match the smallest element ofto the smallest element of, the second smallest element ofto the second smallest element of, and so on. (b) After sortingandin non-decreasing order, suppose there exists,( < ), and,( < ), such that[]matches[]and[]matches[]. Case 1:[][][][], we have|[] []|+|[] []|=|[] []|+ |[] []|. Case 2:[][][][], we have|[] []|+|[] []||[] []|+ |[] []|. Case 3:[][][][], we have|[] []|+|[] []||[] []|+ |[] []|. Case 4:[][][][], we have|[] []|+|[] []||[] []|+ |[] []|. Case 5:[][][][], we have|[] []|+|[] []||[] []|+ |[] []|. Case 6:[][][][], we have|[] []|+|[] []|=|[] []|+ |[] []|.
In summary,|[] []|+|[] []||[] []|+|[] []|, for any < , < . Thus, we can see that by re-matching[]with[]and re-matching[]with[], we will get a solution that is at least not worse, or even better. Given an optimal solution, by iteratively re-matching, we will get where the ith element ofmatches the ith element of, the same as our greedy solution. (c) Firstly we need sort the arraysand, which costs(log). Then, we can get the optimal allocation by iteratively matching the ith element ofwith the ith element of, costing(). In conclusion, the time complexity is(log). (d) Yes, it does. Proof: After sortingandin non-decreasing order, suppose there exists an allocation where mismax( )<mismax(). Without loss of generosity, let[][]. Let|([] [])|be the maximum mismatch, which means that mismax() =|([] [])|=[] []. From the suppose we know that mismax( )<mismax(), then||([] [
()])||mismax(
)<mismax() =[] [].
If
()> , then||([] [
()])||=[
()] []> [] [] =mismax(), leading to a
contradiction. Thus, we have
()< .
Since
is a one-to-to mapping, given >
(), there must existssuch that < and
().
Then, as we know[]< []< [][
()], we have||([] [
()])||=[
()]
[]> [] [] =mismax(), which means that mismax(
)>mismax(), leading to a
contradiction.
In summary, the assumption that there exists an allocation
where mismax(
)<mismax()
doesnt hold.
Thus, the greedy algorithm minimises the mismax.
Problem 3
(a)
= 2: The number of edges is 0.
= 3: The number of edges is 8.
= 4: The number of edges is 24.
(b)
The number of edges in the Pony Graph is4( 1)( 2).
(c)
||=^2 =(^2 ),||= 4( 1)( 2) =(^2 ). Thus,||+||=(^2 ).
(d)
Firstly, we begin at (1,1) in the first chessboard until arriving at (6,8) in the first chessboard.
Then, we move to (8,1) in the second chessboard, and after visiting other squares in the second
chessboard exactly once, we arrive at (7,3) in the second chessboard.
Afterwards, we move to (1,2) in the fourth chessboard, and after visiting other squares in the
fourth chessboard exactly once, we arrive at (3,1) in the fourth chessboard.
Then, we move to (1,8) in the third chessboard, and after visiting other squares in the third
chessboard exactly once, we arrive at (2,6) in the third chessboard.
Finally, we move to (8,7) in the first chessboard, and go on the remaining tour in the first
chessboard.
(e)
Base case: When= 8, return the tour trivially. Divide and conquer: Divide thechessboard into four 2 2 chessboards. Recursively find the tours in chessboards of size 2 2. Merge the four tours of four 2 2 chessboards into one tour ofchessboard by the method in (d). Return the merged tour. (f) Proof: Let= 2, 3 and. Base case:= 3, then= 8, the problem is trivial. Induction hypothesis: Assume that when=, our algorithm can solve the problem of size 2 2. Induction step: When=+ 1, our algorithm divide the problem of size 2 +1 2+1into four problems of size 2 2, which will be solved successfully by the induction hypothesis. Then, given 4 chessboards of size 2 2, each with a Friendly Pony Tour, we can combine them to get a Friendly Pony Tour on a chessboard of size 2 +1 2+1in O(1). In conclusion, our algorithm will solve the problem correctly. Time complexity: We divide the problem of sizeinto four problems of size 2 2 , recursively solve them, and combine them to get the solution to the problem of size. Thus, the recurrence equation is:() = 4( 2 ) +(1). By Master Theorem, we have() = (^2 ). (g) Since the size of the graph is||+||=(^2 ), which is equal to the time complexity of our algorithm, it is running in linear time.