# 算法设计代写 | COSC 2123/1285 Assignment 2: Algorithm Design & Complexity Analysis

IMPORTANT NOTES

• If you are asked to develop/design an algorithm, you need to describe it in
plain English ﬁrst, say a paragraph, and then provide an unambiguous pseudo
code, unless speciﬁed otherwise. The description must include enough details to
understand how the algorithm runs and what the complexity is roughly. All algo-
rithm descriptions and pseudo codes required in this assignment are at most half
a page in length.

• 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 modiﬁcation is needed, you have to
provide a full description. If you are not clear whether certain algorithms/opera-
tions are standard or not, post it to Canvas Discussion Forum or drop us an email
at sonhoang.dau@rmit.edu.au.

• Marks are given based on correctness, conciseness (with page limits), and clar-
standable, 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 signiﬁcantly.

• All stories are ﬁctitious and just for fun. Please do not take them seriously.

1 Part I: Fundamental

Problem 1 (8 marks, 1 page). Saving the niece.

One day, your niece comes to visit you with a worried look on her face. It turns out
that her teacher just gave a very tricky problem as part of their VCE Algorithmics Unit 3.
She has spent 3 days working on it without any success. As a loving (and very capable)
uncle/aunt, you must help her out. Here is the problem.

Consider the algorithm mystery() whose input is an integer array A of size n.

Algorithm mystery(A[0. . . (n¡1)])

return mysteryRecursive(A[0. . . (n¡1)]);

Algorithm mysteryRecursive(A[l. . . r])

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

c) [1 marks] Write the recurrence relation (formula + base condition) for C(n), which
counts the number of array elements comparisons.

d) [3 marks] Solve the 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-£ notation.

E-mail: itcsdx@outlook.com  微信:itcsdx