Coins. You work in a casino as a programmer. You have access to the
following API:
bool coinflip();
It is simply a wrapper around a physical device that randomly produces
0 or 1, each with probability 0.5.
(a) The manager asks you to create a function
int three_face_die();
that produces a random number in {0; 1; 2} with uniform prob-
ability. Of course you can use coinflip. How many calls to
coinflip does your program make?
(b) The physical device that coinflip uses just broke down. Now
coinflip produces 0 with probability p and 1 with probability
1 - p, but you don't know what p is. You can assume 0 < p < 1.
Write a function
bool fair_coinflip();
that works like coinflip used to work. Your function has to be
correct for all 0 < p < 1. Stated otherwise, how can you create
a non-biased coin from a biased one as subroutine (and without
knowing the bias p).