本次澳洲代写是算法相关的一个assignment

**Objectives**

To improve your understanding of the time complexity of algorithms and recurrence relations. To develop

problem-solving and design skills. To improve written communication skills; in particular the ability to

present algorithms clearly, precisely and unambiguously.

**Scenario**

In this assignment we will consider the following scenario. Suppose you are writing algorithms that will

form part of the implementation for a cryptocurrency client for the ﬁctitious MugsCoin cryptocurrency

system.

Each user who participates in the MugsCoin system has a MugsCoin account that stores their funds.

The MugsCoin system maintains an accounts database that stores, for each user account in the system,

the balance of that account, i.e. the amount of MugsCoin that it holds.

Each user who participates in the MugsCoin system runs a program on their computer called the

MugsCoin client. This client allows the user to perform transactions, including moving MugsCoins to and

from their account, and transferring MugsCoins between their account and the accounts of other users.

As each transaction is performed the MugsCoin accounts database is updated.

Updating the accounts database requires solving a proof of work problem. This problem involves a

so-called hash function f, and requires ﬁnding an input x such that f(x)= y for a value y that is a

function of the information to be added to the database (see below).

In this assignment you will implement and analyse some alternative algorithms and designs for parts

of this system.

**Proof-of-Work**

As mentioned to modify the accounts database clients must solve a so-called proof-of-work problem.

MugsCoin’s proof-of-work uses a so-called hash function f as part of its proof-of-work scheme. To add

a new record r to the database, the client computes a target value y = g(r · h) by applying a separate

deterministic function to the record r and the database history h. The client must then ﬁnd an input

value x for the hash function such that f(x)= y.Theinputs x to the hash function f are just bitstrings

(arrays of bits) of arbitrary length. Its output is a bitstring of some ﬁxed length (the actual output length

is not important).

Suppose we are trying to write an algorithm to solve the MugsCoin proof-of-work problem for inputs

up to length n-bits. The desired algorithm takes as its input the ﬁxed output value y and searches

through all inputs up to length n-bits, trying to ﬁnd an input x such that f(x)= y. It returns a boolean

(true/false) indicating whether a solution can be found or not.

We might write this algorithm as follows. It makes use of an auxillary function SearchPOWFixed(x, k, y)

that takes a bitstring x whose length is at least k and is assumed to be ﬁlled with zeros, plus the target

value y. The job of SearchPOWFixed is to see whether there exists any bitstring x0

of length k such

that f(x0)= y. If this is the case it returns true and otherwise returns false.

function SearchPOW(n, y)

//n is the (positive) maximum bitstring length to search up to

//y is the ﬁxed output value

x allocate a bitstring of length n

//note: x can be considered a bitstring of length k for all 0 <k n

k 1

while k n do

ﬁll x with all zeros

if SearchPOWFixed(x,k,y) then

return true

k k +1

return false

1. [2 marks] Brogrammer Barry has written the following implementation of SearchPOWFixed.

function SearchPOWFixed’(x[·],i,k,y)

//x is a bitstring of length k

//i is an integer in the range [0,k] (i.e. 0 to k inclusive)

//y is the ﬁxed output value

//returns true if a solution is found; false otherwise

if i = k then

return (f(x)= y)

for j i to k # 1 do

x[j] 1

if SearchPOWFixed’(x, i +1,k,y) then return true

else

x[j] 0

return SearchPOWFixed’(x, i +1,k,y)

function SearchPOWFixed(x[·],k,y)

return SearchPOWFixed’(x, 0,k,y)

Here the basic operation is executing the hash function f. We can deﬁne the size of the input to the

auxiliary function SearchPOWFixed’(x, i, k, y) as k # i. Write down a recurrence relation H(n)

for the number of calls to the hash function f that SearchPOWFixed’ performs for an input of

size n. Use telescoping (aka back-substitution) to derive a closed form for H(n). From this state

a precise formula for the number of basic operations (calls to f) that SearchPOWFixed(x, k, y)

performs.

2. [3 marks] A brute-force implementation of SearchPOWFixed must, in the worst case, try 2k inputs x

to see if any hash to the target value y. Write a brute-force implementation of SearchPOWFixed.

Your SearchPOWFixed(x, k, y) implementation should have worst-case complexity ⇥(2k), where

the basic operation is executing the hash function f.

3. [2 marks] Calculate the worst-case complexity of the algorithm SearchPOW above, assuming it

uses the brute-force implementation of SearchPOWFixed (rather than Barry’s implementation).

The complexity of SearchPOW(n, y) should be expressed in terms of its input n,i.e. n measures

the size of the input. The basic operation is executing the hash function f. Show your working.