Computer Science > QUESTIONS & ANSWERS > Indiana University, Bloomington - CS 161161-homework-3-solutions PROBLEMS AND SOLUTIONS (All)

Indiana University, Bloomington - CS 161161-homework-3-solutions PROBLEMS AND SOLUTIONS

Document Content and Description Below

CS 161 Problem Set 3 with Solutions Spring 2017 Due: April 28, 2017, 3pm Please answer each of the following problems. Refer to the course webpage for the collaboration policy, as well as for helpful advice for how to write up your solutions. Note: For all problems, if you include pseudocode in your solution, please also include a brief English description of what the pseudocode does. 1. Suppose that p is an unknown value, 0 < p < 1. Suppose that you can call a function randP which returns true with probability p and returns false with probability 1 − p. Every call to randP is independent. You have no way to generate random numbers except through randP. (a) (2 pts) Describe an algorithm|using randP|that returns true with probability 1=2 and false with probability 1=2. Your algorithm should in expectation, use 1 p(1−p) calls to randP. Your algorithm does not have access to the value of p, and does not have access to any source of randomness other than calls to randP. [We are expecting pseudocode, and a short English description of what the algorithm does. Your pseudocode should be detailed enough that a CS106B student could implement it without much thought.] Hints: (i) Your algorithm does not have to compute p, or an approximation to it. (ii) Notice that in the worst case, your algorithm may use more calls to randP, possibly even infinitely many. (b) (1pts) Formally prove that your algorithm runs using expected 1 p(1−p) calls to randP. [We are expecting a mathematical calculation of the expected value of the total number of calls to randP.] (c) (1 pt) Informally argue that your algorithm returns true with probability 1=2 and false with probability 1=2. [We are expecting an informal justification of why the algorithm returns true with probability 1=2 and false with probability 1=2. Your argument should convince the reader that you are correct, but does not have to be a formal proof.] SOLUTION. (a) The pseudocode is as follows. while True: x1 = randP() x2 = randP() if x1 != x2: return x1 That is, the algorithm draws two samples from randP. If they are not equal, it returns the first one. Intuitively, no matter what p is, if x1 6= x2, then half the time it should be because x1 = 0 and x2 = 1, and half the time it should be the other way around.

[Show More]

Last updated: 3 years ago

Preview 1 out of 13 pages

Buy Now

Instant download