Here we wonder, can we simulate a fair die using a fair coin. That is, suppose your computer has a fair coin that can be flipped independently for an unbounded number of times. Can we design a procedure that samples a number uniformly random over{1,2, 3, 4,5,6]? This essentially means that we simulate a fair die. Similar to the lecture, you should consider the following cases with analysis (correctness, running time) . Design an algorithm that never fails and outputs the correct distribu- . Design an algorithm that might fail, but the output is the perfectly . Design an algorithm that does not fail and outputs almost correctly tion perfectly, but might not terminate correct under the condition that the algorithm does not fail. Suppose you can simulate a fair die using a fair coin (either perfectly or almost correctly). Argue that this implies you can generate random output over 1,2,3, 4,5 as well (perfectly or almost correctly, respectively). The argument should be simple, e.g., by using only one sentence. Here we wonder, can we simulate a fair die using a fair coin. That is, suppose your computer has a fair coin that can be flipped independently for an unbounded number of times. Can we design a procedure that samples a number uniformly random over{1,2, 3, 4,5,6]? This essentially means that we simulate a fair die. Similar to the lecture, you should consider the following cases with analysis (correctness, running time) . Design an algorithm that never fails and outputs the correct distribu- . Design an algorithm that might fail, but the output is the perfectly . Design an algorithm that does not fail and outputs almost correctly tion perfectly, but might not terminate correct under the condition that the algorithm does not fail. Suppose you can simulate a fair die using a fair coin (either perfectly or almost correctly). Argue that this implies you can generate random output over 1,2,3, 4,5 as well (perfectly or almost correctly, respectively). The argument should be simple, e.g., by using only one sentence