(a) Explain the similarities and differences between Monte Carlo algorithms and
ID: 3758859 • Letter: #
Question
(a) Explain the similarities and differences between Monte Carlo algorithms and Las Vegas algo- rithms. (2 marks)
(b) SupposethataMonteCarloalgorithmAforadecisionproblemXisyes-biased,runsinlinear time, and has false negative rate 1/2. Explain how to obtain a 0.999-correct algorithm for X that runs in linear time.
(c) Suppose that an unbiased Monte Carlo algorithm B for X is 0.7-correct. Explain in detail what this means.
(d) Explain how to obtain an unbiased Monte Carlo algorithm for X that is 0.78-correct, with asymptotic running time at most 3 times that of B.
(a) Explain the similarities and differences between Monte Carlo algorithms and Las Vegas algo- (2 marks) rithms. (b) Suppose that a Monte Carlo algorithm A for a decision problem X is yes-biased, runs in linear time, and has false negative rate 1/2. Explain how to obtain a 0.999-correct algorithm for X (3 marks) that runs in linear time. (c) Suppose that an unbiased Monte Carlo algorthm B for X is 0.7-correct. Explain in detail nte Carlo algorithm B for X is 0.7 (2 marks) (d) Explain how to obtain an unbiased Monte Carlo algorithm for X that is 0.78-correct, with (3 marks) what this means. asymptotic running time at most 3 times that of B.Explanation / Answer
a) monte carlo algorithms (MCRA) may produce incorrect results.
there are onre sided and two sided MCRA algorithms
Las Vegas algorithms always produce correct results
Las vegas algorithms are zero sided algorithm
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.