Determine the expected number of die rolls until a coin flip

Assignment Help Computer Engineering

Reference no: EM132141237

Suppose you are given a six-sided die, that might be biased in an unknown way.

Explain how to use die rolls to generate unbiased coin flips, and determine the expected number of die rolls until a coin flip is generated.

Now suppose you want to generate unbiased die rolls (from a six-sided die) given your potentially biased die.

Explain how to do this, and again determine the expected number of biased die rolls until an unbiased die roll is generated.

For both problems, you need not give the most efficient solution; however, your solution should be reasonable, and exceptional solutions will receive exceptional scores.

Reference no: EM132141237

Questions Cloud

How does the behavior of dbscan and k-means differ on : Suppose you are given two sets of 100 points that fall within the unit square. One set of points (a) is arranged so that the points are uniformly spaced.

Describe a linear time algorithm for this does di-graph g : Determine whether a given vertex can reach every other vertex in the graph (this is the 1-to-many reachability problem).

Find a shortest path from s to t : Design an algorithm that given any two vertices s and t of G, find a shortest path from s to t using O(|E|) time.

Write an algorithm to determine the two closest cities : Suppose you are given a set of cities (p number of cities) and there longitude and latitude coordinates. You need to determine the two closest cities.

Determine the expected number of die rolls until a coin flip : Explain how to use die rolls to generate unbiased coin flips, and determine the expected number of die rolls until a coin flip is generated.

Write an algorithm to transfer all elements : Write an algorithm to transfer all elements from S to T so that the top of S is the first to be inserted onto T, and the bottom of S ends up at the top of T.

What was the human reason for encoding this information : What kind of encoding would this be and what was the human reason for encoding this information?

What would the value of the field containing the parity bits : Suppose the information content of a packet is the ASCII (8-bit code) representation of "OK" and an even parity scheme is being used.

Describe a strategy you can use to decide whether m halts : Suppose you are given a Turing machine M (not necessarily a decider), a string w, and a (different) magic genie.

User Account

All Pages