You are given a function foo() that represents a biased coin. When foo() is called, it...

Transcribed Image Text:

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 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

Answer rating: 100% (QA)

Lets address the questions 1 Probability of 01 and 10 in two runs of foo Probability of 01 P01 P0P1 ... View the full answer