1. Formalize Merkle Tree algorithms (6 pt) Write down a formal pseudo-code (together with a brief explanation on how it works) and analyze the running time of the following three algorithms - Given m+1 data with index 0 to m, construct a Merkle tree. You can assume that blocks are sorted and m=2k1 for some integer k. - Given a complete sorted Merkle Tree, present a proof of membership for some data x. - Given a complete sorted Merkle Tree, present a proof of non-membership for some data x. In your solutions, you need to consider how to represent and traverse the tree data structure. For the second and third algorithm, your algorithm needs to return a set of values that are stored inside intermediate nodes in the Merkle tree that can jointly be used as a proof. You will lose points if your pseudo-code is not clear or not precise. If you don't know whether what you wrote is clear enough, use this criteria: any student who has taken CS1, CS2, L\&C should be able to implement it in their favorite language by reading your pseudo-code. If you're still not sure, feel free to check with me before the deadline. Feel free to use any solutions that you found online or produced by ChatGPT. However, you need to explain them in your own words