Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COSC 2123/1285
Assignment 2: Algorithm Design & Complexity Analysis
Assessment Type Individual Assignment. Submit online via Canvas → Assignments
→ Assignment 2. Clarifications/updates/FAQs can be
found in Canvas Announcements and Discussion → Assignment
2 Queries.
IMPORTANT NOTES
? If you are asked to develop/design an algorithm, you need to describe it in
plain English first, say a paragraph, and then provide an unambiguous pseudo
code, unless specified 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.
? 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 modification is needed, you have to
provide a full description.
? 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 significantly.
? All stories are fictitious and just for fun. Please do not take them seriously.
? In the submission (your PDF file), 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":
2
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[`... 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.
3
Transaction ti Size si Fee fi
1 1 4
2 3 9
3 2 6
4 4 11
5 5 13
Table 1: A toy example of five transactions with their corresponding sizes and fees.
Problem 2 (8 marks, 1 page). Profit maximisation in block mining - version 1.
As the Bitcoin price has quadrupled in the past one year (9/2020-9/2021), you have
made a decision of becoming a miner to earn some profit. You find out that in Bitcoin
blockchain and the like, miners are responsible for constructing blocks and if successful
(being the first to solve a puzzle), will receive not only a base reward but also transaction
fees included in the transactions in the block. While the base reward is fixed and out
of control of the miners, the transaction fees are not. You quickly figure out that one
way for the miners to maximise their profit is to select the set of transactions that sum
up to the highest fee.