CS 206 HW 6
Spring 2020
1. We conduct an experiment of counting the number of tosses of a fair coin until getting
three consecutive heads. We record the outcomes (for example, HTTTTHHH), until
we get three heads. Let’s define a geometric random variable X that represents the
number of tosses of a fair coin until we get three consecutive heads. Possible values for
X are positive integers, such as x ∈ {1, 2, 3, 4...}.
(a) Enumerate all possible records whose length is 3, 4, 5, and 6.
(b) These records give us a sample space Ω, and we can decompose Ω into four sets:
· A1 = {(H,H,H)}
· A2 = {(T, ∗, ∗, ..., ∗)} (all records starting with T )
· A3 = {(H,T, ∗, ∗, ..., ∗)}
· A4 = {(H,H, T, ∗, ∗, ..., ∗)}
Please compute P [A1], P [A2], P [A3], and P [A4].
(c) Please find E[X] using these four decompositions.
Hint: You could write an equation by using E[X], E[X+1], E[X+2], and E[X+3].
2. Suppose you design an algorithm to multiply two n-bit integers x and y. The general
multiplication technique takes T (n) = O(n2) time. For a more efficient algorithm, you
first split each of x and y into their left and right halves, which are n/2 bits long. For
example, if x = 100011012, then xL = 10002 and xR = 11012, and x = 24 · xL + xR.
Then the product of x and y can be re-written as the following:
x · y = 2n · (xL · yL) + 2n/2 · (xL · yR + xR · yL) + (xR · yR)
(a) Based on the rewritten multiplication formula, write a recurrence relation for
T (n), where all running time of summations/subtractions can be approximated
by O(n). By using the Master theorem, find the O(·) running time. Do you think
the splitting method is beneficial?
(b) A clever person remarks that the value of (xL · yR + xR · yL) is equal to (xL +
xR) · (yL + yR) − (xL · yL) − (xR · yR) and this can be used to improve your
recursion process. How does it change your recursion equation? Please write a
new recurrence and use the Master theorem to find the corresponding O(·).
3. Suppose a plant puts out a new shoot, and that shoot has to grow two months before
it is strong enough to support branching. If it branches every month after that at
the growing point, write a recursion equation to describe number of branches after n
months, B(n), and find its closed form, where B(1) = 1 and B(2) = 1.