A very important requirement in cryptography is the generation of pseudorandom sequences for various purposes such as (a) key generation (b) primality testing and other randomized algorithms. In practice, purely random sequences (i.i.d. and uniformly distributed over some alphabet, usually (0,1}) are an ideal that cannot be attained easily. We now consider some techniques to improve the quality of random sequences. Let us consider biased but i.i.d. bits. That is to say, we have a random binary sequence X[1], X[2]. .. such that Prob[X[i] = 1] = p, for all i=1,2,. (and thus Prob[X[i] = 0 ] = 1-p, for all i=1,2,..), with p not equal to 1/2. The great scientist Von Neumann came up with a technique to unbias a sequence of biased bits, which is described in the article I have handed out by Mitzenmacher. It essentially breaks up the bit sequence into 2-bit consecutive blocks and maps the bit sequence 01 to 0 and 10 to 1 while discarding 00 and 11. In all the following questions except 1(f) p is not equal to 1/2 but known. Question 1(a) What is the probability of a block of 01? 00? 10? 11? Question 1(b) In the long run, what fraction of bits are discarded by von Neumann's method? Explain fully. Question 1(c) Implement the multilevel strategy (2-level) described in Figure 1 by writing magma code (see next page for code hints and details on how to calculate p) which implements it on a given sequence or a pseudocode. Please document your code. Note: If you write pseudocode, you can do your processing by hand with full explanations. However, you will need to type the final output into your document in machine readable fashion [in microsoft word, say] so it can be checked. It might make sense then to write the pseudocode and the step by step processing by hand and scan it as an image. If your answer cannot be checked it won't be marked (everyone's sequence is different)