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.
