2 Part II: AdvancedProblem 4 (7 marks, 2 pages). Each Bitcoin transaction, in its simplest form, has oneinput coin and several output coins (see Fig. 3). The input coin is genuine in the sensethat it is spent by the transaction. This creates the issue of traceability for Bitcoin, thatis, the entire history of each coin can be traced, e.g., how it was created, split, spent, andby which users, etc., which can sometimes be too revealing and undesirable for the users.To make the cryptocurrency untraceable, it has been proposed that instead of using onlygenuine inputs, the cryptocurrency wallet should also include other fake inputs so thatan observer won’t know which input is the genuine one for that transaction. We willignore the fact how this can be done technically and only focus on the mixing part wheregenuine and fake inputs are mixed in the transactions to provide untraceability. Assumethat each coin can be used as a genuine input for exactly one transaction and that thenumber of coins is the same as the number of transactions in the system.Figure 3: Example of input and output coins in a Bitcoin transaction.Figure 4: Examples of mixing genuine and fake inputs for transactions to provideuntraceability. The mixing strategy in a) fails because an observer can determine aunique mapping M that matches genuine coins with transactions: M[1] =2, M[2] = 3,M[3] =4, and M[4] =1. The mixing in b) is not the best in disguising the actual mapping,but still confuses an observer as there are two possibilities to match the coins with thetransactions.The mixing strategy sometimes fails because not all mixings are done in a proper way.For example, in Fig. 4 a), an observer can determine which coin is the genuine input ofwhich transaction for ALL the coins. We refer to such a mixing as a bad mixing strategy.6Note that a mixing strategy can be described by a bipartite graph with the left-sidevertices corresponding to the coins and the right-side vertices corresponding to the trans-actions, and there is an edge between a coin Ci and a transaction T j if Ci is included inT j as an input (genuine or fake). Design an algorithm of time complexity O(n+m), wheren is the number of coins (or equivalently, the number of transactions) and m is the num-ber of edges in the bipartite graph, that determines if a particular mixing is bad, i.e.,a unique mapping M that maps ALL coins to their corresponding transactions could befound. The algorithm must output M if the mixing is bad.a) [3 marks] Describe the algorithm in plain English together with a short pseu-docode. The algorithm must be described in an unambiguous and concise wayand provides enough details so that another student can understand how it worksand why it solves the problem. The input of the algorithm is n, m, the (adjacency)lists of transactions Li (abbreviation for “Left”) that include the coin Ci as an in-put, i =1, 2, . . . , n, and the (adjacency) lists of coins R j (abbreviation for “Right”)that are inputs of Transaction T j, j =1, 2, . . . , n. The output of the algorithm is ei-ther the unique mapping M of coins and transactions or None, which indicates thatan unique mapping can’t be found, i.e., there are more than one valid mappings.c) [2 marks] Demonstrate your algorithm with an example, e.g., in Fig. 4 a).d) [2 marks] Show that the complexity is indeed in O(n +m), which means that thereare constants a and b such that the complexity is at most a×n+b×m, e.g. 3n+2m.7Problem 5 (7 marks). The n nodes of a rooted complete binary tree can be indexed by theset [0, n −1] ,{0, 1, . . . , n −1} in the natural order (top to bottom, left to right). A labellingor permutation p is a map that assigns to each vertex i ∈[0, n−1] a label p[i] ∈[0, n−1] sothat different nodes have different labels. A labelling p is called magical if it satisfiesthe following condition: if we assign to each edge (i, j) of the tree the label |p[i] −p[ j]|,i.e., the absolute value of the difference between the labels of Node i and Node j, thenall edge labels must all be distinct. We can also treat p as a permutation of the verticelabels. See Fig. 5 for an example of such labellings/permutations on trees of n =5 andn =8 nodes. In these cases, the labellings are p =[0, 4, 2, 1, 3] and p =[3, 0, 5, 7, 6, 4, 1, 2].Note that for the first labelling, p[0] =0, p[1] =4, p[2] =2, p[3] =1, p[4] =3.30 57 6 4 104 21 34 23 1237 6521 4Figure 5: Examples of magical labellings p =[0, 4, 2, 1, 3] and p =[3, 0, 5, 7, 6, 4, 1, 2] forcomplete binary trees of n =5 and n = 8 nodes, respectively. The edge labels (in red)are calculated by taking the absolute values of the differences between the labels of twoincident nodes, e.g., for the 5-node tree, the edge connecting the root and its left childhas label |p[0] −p[1]|=|0 −4|=4. Both labellings are magical because all edge labels aredistinct.a) [7 marks, 1.5 pages] Design an efficient algorithm (algorithm description, pseudocode, examples, Python code, and an estimated time complexity if possible) thatfinds a magical labelling p for every rooted complete binary tree of n nodes. Thealgorithm is deemed efficient if the submitted implementation in Python can findmagical labellings for ALL 1 ≤n ≤19 in less than 5 minutes on a laptop. All 19output magical labellings/permutations must be included in file permutations.txtsubmitted along the code. A Python code to test these permutations is available onAssignment 2: General Discussion (Ed Discussion Forum).b) [1 bonus mark, 2 pages] Provide a mathematical proof that the algorithm developedin Part a) can find a magical labelling for complete binary of n nodes for ALL n ≥1.Note that there are no partial marks given to this problem. You will receive marks forthe problem only if your submitted code can produce magical labellings for ALL n ≤19in less than 5 minutes AND your description of the algorithm is clear (with examples),correct, and understandable. More details on how to prepare the submission for Problem