$($c$)$ In this problem, we will learn a classic use case of Hoeffding$$s inequality. Imagine we have an algorithm

for solving some decision problem $($e$.$g$.,$ Is there a cat in the picture?$).$ Suppose that the algorithm makes a

randomized decision and returns the correct answer with probability $1$

$2+\backslash$delta $,$ for some $\backslash$delta $>0($which is just a

bit better than a random guess$).$ To improve the performance, we run the algorithm N times and apply the

majority voting. Please show that, for any $$ in $(0,1),$ the answer is correct with probability at least $1\backslash$epsi $,$ as

long as N $>=(1/2)\backslash$delta

$2$

ln$(\backslash$epsi

$1$

$).($Hint: For each i$,$ define Xi to be a Bernoulli random variable for which Xi $=1$

when the algorithm return the correct answer at the i$-$th trial. Under majority voting, we know that if the final

answer is incorrect, then X$1+$ X$2++$ XN $<=$ N$/2.$ Use the negative part of Hoeffding$$s inequality. This

scheme is usually called $$boosting randomized algorithms.$)$