Problem 2 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 Σi∈I fi while guaranteeing that the total size Σi∈I si does not exceed the block size limit b.

a) Design a greedy algorithm for this problem (note that it does NOT have to return the optimal solution): algorithm description + short pseudocode + complexity analysis. 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.

b) 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, build the dynamic programming table for the toy example in Table 1 with b = 8, and identify the set of transactions output by the algorithm together with the maximum profit.