代写COSC 2123程序、代写Java，Python编程

日期：2021-10-12 09:48

Algorithms and Analysis

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.

Due Date Week 12, 11:59pm, October 15, 2021

Marks 40

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. If you are not clear whether certain algorithms/operations

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 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. The problem formulation you come up with is: given n available

transactions, in which transaction ti has size si and pays fee fi

, 1 ≤ i ≤ n, the miner

should select a set I of transaction (indices) that has the maximum total fee P

i∈I

fi while

guaranteeing that the total size P

i∈I si does not exceed the block size limit b.

a) [4 marks, 1/2 page] Design a greedy algorithm for this problem (note that it does

NOT have to return the optimal solution): algorithm description (1 mark) + short

pseudocode (1 mark) + complexity analysis (1 mark). Run it on the toy example in

Table 1 with b = 8 and write down the list of transactions selected by the algorithm

in their corresponding order (1 mark).

b) [4 marks, 1/2 page] Design a dynamic programming algorithm of complexity O(nb)

that can find a set of transactions that maximises the profit: write down the recursion

formula (1 mark), build the dynamic programming table for the toy example

in Table 1 with b = 8 (2 marks), and identify the set of transactions output by the

algorithm together with the maximum profit (1 mark).

4

Problem 3. [10 marks, 3 pages] The oracle and the mysterious answer.

In the search for the meaning of life, you set off for a dangerous trip to visit a mysterious

oracle living in a temple at the heart of the Great Victoria Desert. Barely escaping

a terrible sand storm, you’ve finally found the oasis at a great cost: all the supplies have

been buried under the sand and the only camel has run away. To make it worse, there

is no sign of any source of water and all the plants surrounding the temple are dead.

Apparently the oasis has been drying up for quite some time.

Staggering into the temple, surprisingly, you find the oracle, who seems to be waiting

for you. “Speak, human! You can ask me one question.” What a hoarse and emotionless

voice! Is it because she has not had water for a long time? “Oracle, I... ”, You hesitate.

Before going, you had a list of all deep-meaning questions prepared. But now, what the

heck! Licking your chapped lips, you ask “Oracle... where can I find water?” The oracle

regards you for almost five seconds, and then asks “Computer scientist, yes?” “Y... yes,”

you reply, clearing your throat. She’s an oracle after all. But you suddenly have this

strange thought: what did the oracle do for a living before taking this... job? But surely

you cannot ask a second question. The oracle immediately pulls out a piece of paper and

a pen, writes something down and hands it to you eagerly as if she has been waiting to

do this for a long time. Although it is rather dim in the temple, you can still feel her

intense gaze under the veil. “The answer is in the solution,” said the oracle, still with

her emotionless voice. You turn toward the door to get some more light. It is a vaguely

familiar problem about a compression algorithm. Not again!!! You groan and turn back

to face the oracle, ready to shoot another question or at least, a complaint. But there is

nobody there... But the unbearable thirst reminds you that you should not worry about

the oracle’s whereabouts. The answer for where to find the water is in the solution, and

you need to crack the problem first. Is the oracle helpful? Or does she just want to play?

There’s only one way to find out...

Oracle’s problem. There are ten letters whose frequencies are given in Table 2.

Letter A B E 2 H N O T U Y

Frequency 27 9 12 10 1 11 5 7 16 2

Table 2: Frequencies of different letters for Problem 3.

a) [2 marks, 1 page] Construct a min-heap (tree) using the bottom-up heap construction

to represent the frequencies in Table 2 (using the given order). Please use

(label:frequency), for example, “H:1”, for nodes in the heap. Describe (draw) all the

steps required (use two-head arrows to indicate an exchange between two nodes).

Note that a min-heap is the same as a max-heap, except that the key stored at a

parent node is required to be smaller than the keys stored at its two children nodes.

b) [2 marks, 2/3 page] Illustrate (draw) the process of dequeuing the two letters of

smallest frequencies from the heap one by one (dequeue -> repair -> dequeue ->

repair).

c) [1 mark, 1/3 page] Illustrate (draw) the process of enqueuing the new element (i.e.

enqueue -> repair), which results from the combination of frequencies of the two

5

dequeued elements earlier. For example, if ‘H:1’ and ‘Y:2’ were dequeued, then the

new element ‘HY:3’ would be enqueued.

d) [4 marks, 1 page] Provide a complete construction of the Huffman tree (3 marks) together

with the codes for all letters (1 mark). Only the complete final tree needs to

be given. However, each intermediate node must be labelled with both frequencies,

e.g. “3”, and the step in which it is constructed, e.g. “Step 1”. When constructing

the trees, the following rule applies: for every node from the root, the frequency of

its left child must be smaller than or equal to that of its right child.

(Have you found out her answer? Does it help?)

6

2 Part II: Advanced

RMIT Classification: Trusted

Figure legends

Figure 1: A toy example of twelve transactions with their corresponding sizes (red) and

fees (green). For example, t3 has size s3 = 1 and fee f3 = 2. The dependency among

transactions is represented by arrows: tj → ti means that tj depends on ti

. For instance,

t7 depends on t3, which in turn depends on t1. The block size limit is b = 18.

Problem 4 (8 marks, 1.5 pages). Profit maximisation in block mining - version 2?

.

After executing your algorithms that select a set I of transactions from a pool of n unconfirmed

transactions (waiting to be included in a block) that has total size P

i∈I si ≤ b,

where b is the block size limit, while achieving maximum total fee P

i∈I

fi

, you discovered

a problem with this formulation. It dawned on you that the transactions are NOT

independent of each other. For instance, if Alice pays 1 bitcoin to Bob in Transaction

ti

, who in turn uses this coin to pay Carl in Transaction tj

, then tj will depend on ti

.

More specifically, in Bitcoin, tj depends on ti

if an output of ti

is used as an input of tj

(Figure 2). Hence, to include tj

in the current block, ti must be either already included

in an existing block or in the same block as tj

. This is the Dependency Rule. Note that ti

in its turn may depend on other transactions, which also need to be included, and so on.

RMIT Classification: Trusted

Figure 2: Dependency among Bitcoin transactions. Transaction j uses one output of

Transaction i as its input. In such a case, Transaction j depends on Transaction i.

Suppose that you have run a preprocessing algorithm that returns the dependency

list Lj that comprises of all i where tj depends on ti

, for each 1 ≤ j ≤ n. For instance, in

the toy example in Figure 1, L10 = {6,8} and L11 = {2,7}.

7

a) [5 marks, 1 page] Design an efficient algorithm (worst-case complexity O(n

2

)) that

takes as input the number of transactions n, the sizes si and fees fi

, the dependency

lists Li

, i = 1,...,n, and an index set J ? {1,2,...,n}, and returns the list TJ

(J ? TJ) of ALL the transactions (indices) that must be included if the transactions

{tj

: j ∈ J} are to be included in a block, so that the Dependency Rule is respected.

For example, when J = {4,7}, we have TJ = {1,2,3,4,7}. Note that TJ must contain

J as a subset. The solution must include:

– (2 marks) algorithm description,

– (1 mark) short pseudocode, and

– (1 mark) complexity analysis, and

– (1 mark) the list of transactions TJ output by the algorithm applied to the toy

example in Figure 1 with J = {5,10,11} and the corresponding total size & fee.

b) [3 marks, 1/2 page] Based on Part a), design an exhaustive search (algorithm) that

returns a set of transactions (indices) J

?

to form a block that respects the Dependency

Rule and has total size at most b while maximising the total transaction fee.

Input to the algorithm: n, b, si

, fi

, Li

, i = 1,...,n. The solution must include:

– (1 mark) algorithm description, and

– (2 marks) the set of transactions (indices) J

?

output by the exhaustive search,

its total size and its (maximum) total profit for the toy example in Figure 1.

8

Problem 5 (6 marks + 1 bonus mark, 2 pages). Perfect Binary Tree Partition??

.

A perfect binary tree is a rooted binary tree in which every non-leaf node has exactly

two children and all the leaves are at the same depth. Note that a binary tree

of height h will have exactly 2h

leaves. Given a perfect binary tree with height h, let

Sh = {2,3,...,2

h+1 ?1} denote the set of all 2h+1 ?2 nodes of the tree excluding the root.

Let S1,...,Sh be a partition of Sh, that is, Si ∩ Sj = ? for all i 6= j, and ∪1≤i≤hSi = Sh. A

partition is called unrelated if each set Si

in the partition doesn’t contain two nodes in

which one is an ancestor of the other (if u 6= v and u lies on the (unique) path from the

root to v then u is called an ancestor of v while v is called a descendant of u). We define

the balance index of a partition (S1,...,Sh) as the difference between the maximum size

and the minimum size of a set in the partition. More formally,

b(S1,...,Sh) , max

1≤i≤h

|Si

| ? min

1≤i≤h

|Si

|.

a) [5 marks, 1 page] Design an efficient algorithm (algorithm description, pseudo code,

and an estimated time complexity if possible) that finds an unrelated partition of

Sh that has minimum balance index. The algorithm is deemed efficient if the submitted

implementation (Java/Python) can find an unrelated partition with balance

index 0 or 1 for each h ≤ 10 in less than five seconds. Hint: iterative improvement.

b) [1 marks] Applicable if the algorithm can find an unrelated partitions with balance

index 1 for h = 14 in less than 10 hours.

c) [1 bonus mark, 1 page] Provide a mathematical proof that the algorithm developed in

Part a) can find an unrelated partition with balance index 0 or 1 for ALL h ≥ 2.

See the examples in Figure 3 for unrelated partitions of balance index 0/1 when h = 2,3.

There can be other partitions satisfying the requirement. More details on how to prepare

the solution for Problem 5 will be updated on Assignment 2 Queries (Discussion Forum).

RMIT Classification: Trusted

??1 (RED) 2, 6, 7

??2 (GREEN) 3, 4, 5

4 5 6 7

2 3

1

? = 2

??1 (RED) 2, 6, 14, 15

??2 (GREEN) 3, 8, 9, 10, 11

??3 (YELLOW) 4, 5, 7, 12, 13

4 5 6 7

2 3

1

8 9 10 11 12 13 14 15

? = 3

Figure 3: Unrelated partitions with balance index 0 for h = 2 and balance index 1 for

h = 3. Each set Si

in a partition consists of nodes with the same color.

9

3 Submission

The final submission (via Canvas) will consist of:

? Your solutions to all questions in a PDF file of font size 12pt and your agreement

to the honour code (see the first page). You may also submit the code in Problem 5.

Late Submission Penalty: Late submissions will incur a 10% penalty on the total

marks of the corresponding assessment task per day or part of day late, i.e, 4 marks per

day. Submissions that are late by 5 days or more are not accepted and will be awarded

zero, unless Special Consideration has been granted. Granted Special Considerations

with new due date set after the results have been released (typically 2 weeks after the

deadline) will automatically result in an equivalent assessment in the form of a

practical test, assessing the same knowledge and skills of the assignment (location and

time to be arranged by the coordinator). Please ensure your submission is correct and

up-to-date, re-submissions after the due date and time will be considered as late submissions.

The core teaching servers and Canvas can be slow, so please do double check

ensure you have your assignments done and submitted a little before the submission

deadline to avoid submitting late.

Assessment declaration: By submitting this assessment,

4 Plagiarism Policy

University Policy on Academic Honesty and Plagiarism: You are reminded that all submitted

work in this subject is to be the work of you alone. It should not be shared with

other students. Multiple automated similarity checking software will be used to compare

submissions. It is University policy that cheating by students in any form is not permitted,

and that work submitted for assessment purposes must be the independent work of

the student(s) concerned. Plagiarism of any form will result in zero marks being given

for this assessment, and can result in disciplinary action.

For more details,

5 Getting Help

There are multiple venues to get help. We will hold separate Q&A sessions exclusively

for Assignment 2. We encourage you to check and participate in the discussion forum on

Canvas, on which we have a pinned discussion thread for this assignment. Although we

encourage participation in the forums, please refrain from posting solutions or suggestions

leading to solutions.

10