算法代写｜Algorithms and Analysis COSC 2123/1285 Assignment 2: Algorithm Design & Complexity Analysis

这是一篇来自澳洲的关于算法设计和复杂性分析的算法代写

IMPORTANT NOTES

I certify that this is all my own original work. If I took any parts from elsewhere, then they were non-essential parts of the assignment, and they are clearly attributed in my submission. I will show that I agree to this honour code by typing “Yes”:

1 Part I: Fundamental

Problem 1 (8 marks, 1 page). Consider the algorithm mystery() whose input consists of an array A of n integers, two nonnegative integers ` ,u satisfying 0 ≤ ` ≤ u ≤ n−1, and an integer k. We assume that n is a power of 2.

Algorithm mystery(A[0,…,(n−1)],` ,u,k)

if ` == u then

if A[` ] == k then

return 1;

else

return 0;

end if

else

m = b(` + u −1)/2c ;

return mystery(A,` ,m,k)+mystery(A,m+1,u,k);

end if

a) [2 marks] What does mystery(A[0..(n −1)],0,n −1,k) compute (0.5 mark)? Justify your answer (1.5 marks).

b) [1 mark] What is the algorithmic paradigm that the algorithm belongs to?

c) [2 marks] Write the recurrence relation for C(n), the number of additions required by mystery(A,0,n−1,k).

d) [2 marks] Solve the above recurrence relation by the backward substitution method to obtain an explicit formula for C(n) in n.

e) [1 mark] Write the complexity class that C(n) belongs to using the Big-Θ

Problem 2 (8 marks, 1.5 pages). Let A be an array of n integers.

a) [2 marks] Describe a brute-force algorithm that fifinds the minimum difference between two distinct elements of the array, where the difference between a and b  is defifined to be |a − b| [1 mark]. Analyse the time complexity (worst-case) of the algorithm using the big-O notation [1 mark]. Pseudocode/example demonstration are NOT required. Example: A = [3,−6,1,−3,20,6,−9,−15], output is 2 = 3-1.

b) [2 marks] Design a transform-and-conquer algorithm that fifinds the minimum difference between two distinct elements of the array with worst-case time complexity O(nlog(n)): description [1 mark], complexity analysis [1 mark]. Pseudocode/example demonstration are NOT required. If your algorithm only has average-case complexity O(nlog(n)) then a 0.5 mark deduction applies.

c) [4 marks] Given that A is already sorted in a non-decreasing order, design an algorithm with worst-case time complexity O(n) that outputs the absolute values of the elements of A in an increasing order with no duplications: description and pseudocode [2 marks], complexity analysis [1 mark], example demonstration on the provided A [1 mark]. If your algorithm only has average-case complexity O(n) then 2 marks will be deducted. Example: for A = [3,−6,1,−3,20,6,−9,−15], the output is B = [1,3,6,9,15,20].