EECS 376: Foundations of Computer Science Homework 10

$30.00

Category: You will Instantly receive a download link for .zip solution file upon Payment || To Order Original Work Click Custom Order?

Description

5/5 - (1 vote)

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:

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.

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: