• 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
• Marks are given based on correctness, conciseness (with page limits), and clar-
ity of your answers. If the marker thinks that the answer is completely not under-
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])
a) [2 marks] What does the algorithm compute? Justify your answer.
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.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: firstname.lastname@example.org 微信:itcsdx