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

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

IMPORTANT NOTES

If you are asked to design an algorithm, you need to describe it in plain English fifirst, say a paragraph, and then provide an unambiguous pseudo code,unless specifified otherwise. The description must include enough details to understand how the algorithm runs and what the complexity is roughly. All algorithm descriptions and pseudo codes required in this assignment are at most half a page in length. Worst-case complexity is assumed unless specifified otherwise.

Standard array operations such as sorting, linear search, binary search, sum,max/min elements, as well as algorithms discussed in the pre-recorded lectures can be used straight away (but make sure to include the input and output if you are using them as a library). However, if some modifification is needed, you have to provide a full description. If you are not clear whether certain algorithms/operations are standard or not, post it to Ed Discussion Forum or drop Hoang a Team message.

Marks are given based on correctness, conciseness (with page limits), and clarity of your answers. If the marker thinks that the answer is completely not understandable, a zero mark might be given. If correct, ambiguous solutions may still receive a deduction of 0.5 mark for the lack of clarity.

Page limits apply to ALL problems in this assignment. Over-length answers may attract mark deduction (0.5 per question). We do this to (1) make sure you develop a concise solution and (2) to keep the reading/marking time under control. Please do NOT include the problem statements in your submission because this may increase Turnitin’s similarity scores signifificantly.• This is an individual assignment. While you are encouraged to seek clarififications for questions on Ed Forum, please do NOT discuss solutions or post hints leading to solutions.

In the submission (your PDF fifile), you will be required to certify that the submitted solution represents your own work only by agreeing to the following statement:

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].