Answered step by step
Verified Expert Solution
Link Copied!

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%

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 ... blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Financial Accounting and Reporting a Global Perspective

Authors: Michel Lebas, Herve Stolowy, Yuan Ding

4th edition

978-1408066621, 1408066629, 1408076861, 978-1408076866

More Books

Students also viewed these Programming questions

Question

8. What kinds of people are most likely to develop sleep apnea?

Answered: 1 week ago