Question $4)[15$ points$]$ Consider an algorithm A$,$ which returns the correct result with the probability $1/$n for a problem of size n$.$ Suppose that we have a verifier algorithm V which we can use to check if the result returned by algorithm A is correct or not. Suppose that we develop the following algorithm to apply the amplification technique, where we use A to generate a candidate solution and use V to verify it repeatedly:

A$()\{$

$//$ find and return a candidate solution x

$...$

$\}$

V$($x$)\{$

$//$ check if x is a correct solution

$...$

$\}$

Amplified$\_$A$($c$)\{$

for i $=1$ to M do

call A to find a candidate solution x

call V to check if x is a correct solution

end for

$\}$

$($a$)(10$ points$)$ What should be the value of M used in the algorithm Amplified A so that the probability of failing to find the correct answer for Amplified A is at most

p $=$ p$(($n $1)/$n$)$c

Show the steps of your calculation.

$($b$)(5$ points$)$ Would you consider algorithm A as Monte Carlo or Las Vegas? Why?