Consider an algorithm A, which returns the correct result with the probability 1 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: AD // find and return a candidate solution x } VIX) { // check if x is a correct solution } Amplified AIC) { for i = 1 to M do call A to find a candidate solution X call to check if x is a correct solution end for } (a) 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)) C Show the steps of your calculation. (b) Would you consider algorithm A as Monte Carlo or Las Vegas? Why? Consider an algorithm A, which returns the correct result with the probability 1 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: AD // find and return a candidate solution x } VIX) { // check if x is a correct solution } Amplified AIC) { for i = 1 to M do call A to find a candidate solution X call to check if x is a correct solution end for } (a) 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)) C Show the steps of your calculation. (b) Would you consider algorithm A as Monte Carlo or Las Vegas? Why