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 

}

1. (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 = ((n 1)/n)c

   Show the steps of your calculation.

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