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.
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
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.
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
while k n do
ﬁll x with all zeros
if SearchPOWFixed(x,k,y) then
k k +1
1. [2 marks] Brogrammer Barry has written the following implementation of SearchPOWFixed.
//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
if SearchPOWFixed’(x, i +1,k,y) then return true
return SearchPOWFixed’(x, i +1,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)
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.