$5.$ Consider the following program

$//$ Given a biased coin $,$ use i t to g ene rat e an unbiased bit b

int x $,$ y:$=0,0$ ;

while $($ x$=$y $)\{$

x:$=0[$ p $]1$ ;

y:$=0[$ p $]1$ ; $//$flip biased bits until they are not equal

$\}$

b:$=$ x ;

$($a$)$ Is this a Monte Carlo algorithm or a Las Vegas algorithm? $($Write

one line.$)$

$($b$)$ Show that in a single iteration, the probability of setting x $=$

$0^$ y $=1$ is the same as the probability of setting x $=1^$ y $=0.$

Why does this observation imply that the probability of setting

b to $0$ will be unbiased?

$($c$)$ Justify that this program terminates with probability $1$ provided

that $0<$ p $<1.($Hint: use a probabilistic variant.$)$