Answered step by step
Verified Expert Solution
Question
1 Approved Answer
You are given a function foo() that represents a biased coin. When foo() is called, it returns 0 with 60% probability, and 1 with
You are given a function foo() that represents a biased coin. When foo() is called, it returns 0 with 60% probability, and 1 with 40% probability. You have to write a new function, bar(), that returns 0 and 1 with a 50% probability each. Your function should use only foo(), no other library/built-in method. In other words, inside bar(), you can only use calls to foo() as well as loops and if conditions and any other basic operators (no other function calls). To help you in that regard, you must answer the following questions. foo(): //returns 0 with probability 0.6 and 1 with probability 0.4 //you cannot change this function bar() //you have to design this //should return 0 with probability 0.5 and 1 with probability 0.5 1. What is the probability that by running foo() twice we get output (0, 1)? How about (1,0)? In other words, what is the probability that two runs of foo() give us 0 followed by 1? What is the probability that two runs of foo() give us 1 followed by 0? 2. Given the answer to the previous question design bar(). Activate Windows 3. What is the expected running time of bar()? What is the worst-case running time of bar()? Settings to activate W
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Lets address the questions 1 Probability of 01 and 10 in two runs of foo Probability of 01 P01 P0P1 ...Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started