# 算法代写｜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 n1, and an integer k. We assume that n is a power of 2.

Algorithm mystery(A[0,…,(n1)],` ,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,n1,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 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].