SOLVED EECS 376 Homework 10

  1. (a) A group of trees, all with distinct heights, have been planted uniformly randomly in a line. However, due to overcrowding, because some trees are taller than others, certain trees will struggle to receive sunlight. We will determine how many of the trees are expected to die due to this lack of sunlight. If any tree is shorter than both the trees directly in front and behind of it, then it does not receive enough sunlight to survive summer. The trees at the very front and back will die if they are shorter than their (only) neighbor. At the beginning of summer, there are n trees. Compute the expected number of trees that will die in one summer. Solution: (b) A group of n students, all of whom have distinct heights, line up in a single-file line uniformly at random. If a student has any students in front of them who is taller than them, then they cannot see. For this reason, every student files one complaint for each taller student who is in front of them since each one of these students would individually block the original student from seeing. For example, if there were 3 students, where the tallest student was in the front and the shortest student was in the back, there would be 2 complaints from the shortest student and 1 complaint from the middle student. Compute the expected number of complaints. Solution: 2. Let A be an array of length n of a random permutation of n distinct integers. Compute the expected number of increasing subarrays (i.e., contiguous subsequence) in A of length k, for k ≤ n. Solution: 1 EECS 376: Foundations of Computer Science  3. In order to generate random bits, operating systems often use real-world events as a source of randomness (e.g., mouse movements, atmospheric noise, thermal fluctuations, even the radioactive decay of certain isotopes). Unfortunately, these events may not be uniformly and independently random, so there is often bias in the bits we generate from them. This presents a problem since most randomized algorithms rely on access to unbiased, uniformly independent random bits. We explore various ways to generate these desired unbiased results. Hint: The geometric distribution gives the probability that the first occurrence of success requires k independent trials, each with success probability p. If the probability of success on each trial is p, then the probability that the k th trial (out of k trials) is the first success is Pr The k th trial is the first success = p(1 − p) k−1 Using this, we can find the expected number of trials until the first success, E[number of trials until the first success] = X∞ k=1 kp(1 − p) k−1 = 1 p (a) Let Get-Biased-Bit be a function that returns 1 with probability p (where p is an unknown real number between 0 and 1 exclusive) and returns 0 with probability 1 − p. Consider this randomized algorithm, Get-Unbiased-Bit, that returns 1 or 0 with equal (nonzero) probability, using calls to Get-Biased-Bit as a source of randomness. 1: function Get-Unbiased-Bit() 2: loop 3: b1 ← Get-Biased-Bit() 4: b2 ← Get-Biased-Bit() 5: if b1 = 0 and b2 = 1 then 6: return 0 7: else if b1 = 1 and b2 = 0 then 8: return 1 i. Prove that the probability that this algorithm returns 0 is equal to the probability that it returns 1. Solution: ii. How many calls does Get-Unbiased-Bit make to Get-Biased-Bit in expectation? Express your answer in terms of p. (Recall the hint from the beginning of the problem.) Solution: (b) Now let Get-Biased-Die be a function which simulates a biased 6-sided die by returning {1, 2, . . . , 6} with an unknown nonuniform probability distribution P = (p1, p2, . . . , p6), where P6 i pi = 1 and pi is the probability that the biased die returns i. i. Write a randomized algorithm, Get-Unbiased-Die, that returns an element from {1, 2, . . . , 6} uniformly at random (equal probability), using calls to Get-Biased-Die as a source of randomness. 2 EECS 376: Foundations of Computer Science  Homework 10 Due 8:00pm, Nov 21 (accepted until Nov 22 at 9:59 pm, no credit after) Solution: ii. Prove that your provided algorithm outputs each integer in {1, 2, 3, 4, 5, 6} with equal probability. Solution: iii. How many calls does Get-Unbiased-Die make to Get-Biased-Die in expectation? Express your answer in terms of the probability distribution of the six outcomes (p1, p2, . . . , p6). (Recall the hint from the beginning of the problem.) Solution: 4. As its name suggests, the Max-Independent-Set problem concerns finding the maximal independent set in a given graph G = (V, E). (Recall that an independent set S of G is a subset S ⊆ V , such that no two vertices share an edge. That is, it is a set of isolated vertices.) The following is a randomized 1 ∆+1 -approximation for the Max-Independent-Set problem (where ∆ is the maximum degree of any vertex in the graph). Note that this is not a constant factor approximation since ∆ depends on the graph. 1: function Find-Ind-Set(G = (V, E)) 2: S ← ∅ 3: for v ∈ V do 4: Randomly sample a random real rv ∈ [0, 1] 5: for v ∈ V do 6: if rv > rv 0 for every neighbour v 0 of v then 7: S ← S ∪ {v} 8: return S (a) Prove that the algorithm returns an independent set S. Solution: (b) Prove that it is a (1/(∆ + 1))-approximation in expectation. That is, if OPT is the size of the maximum independent set in G, prove that E |S| ≥ OPT ∆ + 1, meaning that the expected size of the output set S is within (1/(∆ + 1)) of OPT. Solution: 3