Best代写-最专业靠谱代写IT | CS | 留学生作业 | 编程代写Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代写

算法代写 | Time Complexity of Algorithms And Recurrence Relations

算法代写 | Time Complexity of Algorithms And Recurrence Relations



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 fictitious 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 finding 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 find 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 fixed 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 fixed output value y and searches
through all inputs up to length n-bits, trying to find 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 filled 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 fixed 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
fill 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 fixed 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
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 define 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.