Properties of randomized algorithms (Monte Carlo, Las Vegas)

I an now learning the Las Vegas and Monte Carlo algorithms myself,and have two questions may be simple but I can not 开发者_JAVA百科answer them,if someone can help me...Thanks in advance

1. Consider Monte Carlo algorithms A for a problem P whose expected running time is at most T(n) on any instance of size n that produces a correct solution with probability y(n). Suppose further that given a solution to P,we can verify its correctness in time t(n). Show how to obtain a Las Vegas algorithm that always gives a correct answer to P and runs in expected time at most (T(n)+t(n))/y(n).

2. Let 0<ε2<ε1<1. Consider a Monte Carlo algorithm that gives the correct solution to a problem with probability at least 1-ε1,regardless of the input. How many independent executions of this algorithm suffice to raise the probability of obtaining a correct solution at least 1-ε2, regardless of the input?

1. Just repeat running your algorithm and testing the result until you get a correct answer. Each run and check takes (T(n) + t(n)) units of time, and the number of runs is a geometric random variable with mean 1 / y(n).

2. What is the probability of failure for one run? For two runs? n runs? Set the probability of failure for n runs equal to e2 and solve for n.